A systolic algorithm and architecture for solving sets of linear equations with multi-band coefficient matrix

A parallel block-iterative algorithm for solving sets of linear equations with a positive multiband coefficient matrix is presented. The parallel structure is obtained by decoupling the sets of equations into subsets instead of partitioning the coefficient matrix into a lower and upper (block) triangular matrix. An important feature of the algorithm is that the coefficient matrices of the decoupled subsets are inverted by a novel direct algorithm. The global algorithm iterates using a Gauss-Seidel-like method toward a solution. For this problem, a systolic algorithm/architecture is designed.<>