Efficient systolic structures for LU decomposition and system of linear equations (Q1103323)

Systolic architecture is designed to take advantage of VLSI technology to perform parallel implementations of algorithms. A previously proposed systolic structure for LU decomposition [cf. \textit{H. T. Kung} and \textit{C. E. Leiserson} [Sparse Matrix Computations Proc. Symp., Knoxville 1978, 256-282 (1979; Zbl 0404.68037)] has hardware efficiency of 33 \%. This paper describes two more efficient systolic algorithms for this problem. The first assumes that elements of the matrix A are stationary and so must be stored in the structure; this process is 100 \% hardware efficient. The second overlaps the inputting of A with the computations; the cost of this benefit is a reduction to 50 \% hardware efficiency. Figures accompanying the text enable the reader to differentiate between the two methods. A third section describes an integrated systolic structure for solving a system of linear equations which is based on the first of the algorithms.