Systolic algorithm for the solution of dense linear equations

Abstract

For arbitrary n×n matrix A and n×m matrix B, a systolic algorithm to solve the linear systems AX=B is presented. The cmputational model used consists of n(n+1) PEs. The number of PEs used is independent of m. This algorithm requires 4n+m–2 time steps to solve the linear systems. Since the structure of PE is simple and the PE with same type executes the identical program, it is very suitable for VLSI implementation. Moreover, if m is a singular matrix, it can be detected during the execution of the systolic algorithm.

Keywords:

• Systolic array
• systolic algorithm
• communication link
• simultaneous linear equations
• Gauss-Jordan elimination

C.R. Categories:

• F.1
• F.2
• G.1