Efficient systolic structures for LU decomposition and system of linear equations (Q1103323)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Efficient systolic structures for LU decomposition and system of linear equations |
scientific article |
Statements
Efficient systolic structures for LU decomposition and system of linear equations (English)
0 references
1988
0 references
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.
0 references
Systolic architecture
0 references
systolic structure
0 references
LU decomposition
0 references
hardware efficiency
0 references