Sparse matrix-vector multiplication on a systolic array

A systolic algorithm is presented which allows the parallel execution of iterative methods for solving systems of linear equations on a processor array. These methods are based on a repeated matrix-vector multiplication. In order to achieve an efficient realization on VLSI circuits special regard is given to the sparse property of the system matrix which is found in many applications. The arising transportation problem is solved by a two-dimensional systolic sorting procedure which determines the array structure and the time complexity of one matrix-vector multiplication. Therefore, the solution of a linear system with n equations requires n times the time complexity of the sorting algorithm and an area complexity of O(e) where e denotes the number of the nonzero elements in the system matrix