On the Design of an Integrated Systolic Array for Solving Simultaneous Linear Equations
F.-C. Lin · The Computer Journal · 1990
This paper introduces, in a stepwise refinement manner, a new systolic array for solving simultaneous linear equations AX = B, where A is an n × n matrix and B is an n × m matrix. Instead of using conventional matrix triangularisation, our design is based on a generalised Gauss–Jordan elimination procedure. First A is transformed into a permutation matrix P and B is transformed into a matrix Q. Then X is computed by multiplying PT and Q. These two stages of computation are tightly pipelines to form an integrated systolic array which is capable of solving the simultaneous linear equations in just 6n + m − 2 time steps. This systolic array achieves maximum data pipelining rate and its computation time, in a sense, is optimal.