×

Solving dense linear systems on systolic architectures. (English) Zbl 0763.65015

Algorithms and parallel VLSI architectures. Vol. A: Tutorials, Lect. Tutorials Int. Workshop, Pont-à-Mousson/Fr. 1990, 363-401 (1991).
[For the entire collection see Zbl 0746.00066.]
The paper gives a survey about the systolic arrays for the solution of dense linear systems using Gaussian elimination and Givens factorization. Implementations on two-dimensional arrays which include on-the-fly solution of the triangular system after the factorization are discussed. Then a space-time minimal systolic array for the Gaussian elimination is derived. Finally, efficient systolic algorithms for matrices over finite fields are presented.

MSC:

65F05 Direct numerical methods for linear systems and matrix inversion
65Y10 Numerical algorithms for specific classes of architectures
68Q80 Cellular automata (computational aspects)
15B33 Matrices over special rings (quaternions, finite fields, etc.)

Citations:

Zbl 0746.00066
PDFBibTeX XMLCite