A systolic algorithm for solving dense linear systems

Abstract

For an arbitrary nxn matrix A and an nx1 column vector b, we present a systolic algorithm to solve the dense linear equations Ax=b. An important consideration is that the pivot row can be changed during the execution of our systolic algorithm. The computational model consists of n linear systolic arrays. For 1 less than or equal to i less than or equal to n, the i(th) linear array:is responsible to eliminate the i(th) unknown variable x(i) of x. This algorithm requires 4n time steps to solve the linear system. The elapsed time unit within a time step is independent of the problem size n. Since the structure of a PE is simple and the same type PE executes the identical instructions, it is very suitable for VLSI implementation. The design process and correctness proof are considered in detail. Moreover,this algorithm can detect whether A is singular or not.