Efficient systolic structures for LU decomposition and system of linear equations

DOI10.1007/BF01602101MaRDI QIDQ1103323zbMATH OpenFDO

Authors B. George

Publication date 1988

Published in Circuits, Systems, and Signal Processing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF01602101

zbMATH Keywords

hardware efficiencyLU decompositionSystolic architecturesystolic structure

Mathematics Subject Classification ID

Direct numerical methods for linear systems and matrix inversion (65F05) Parallel numerical computation (65Y05) Analysis of algorithms and problem complexity (68Q25)

Review text

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.

Recommendations

• A systolic array architecture for linear and inverse matrix systems
• A modular systolic linear array for gaussian elimination
• Part II A systolic array for numerical linear algebra
• On the direct parallel solution of systems of linear equations: New algorithms and systolic structures
• Solution of dense linear systems on an optimal systolic architecture

Cited in

(5)

• A systolic array architecture for linear and inverse matrix systems
• scientific article; zbMATH DE number 4192945 (Why is no real title available?)
• scientific article; zbMATH DE number 3958727 (Why is no real title available?)
• An efficient implementation of LU decomposition in C
• Part II A systolic array for numerical linear algebra

This page was built for publication: Efficient systolic structures for LU decomposition and system of linear equations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1103323)