A new class of parallel algorithms for solving systems of linear equations. (English) Zbl 0677.65021

Comparing the QR factorization with backsubstitution to Faddeev’s feed- forward method, the Faddeev’s array computes the solution roughly twice faster than QR factorization and substitution. It serves as a motivation for describing efficient noval feed-forward algorithms. It is shown how the backsubstitution can be rephrased in terms of an updating or downdating of a Cholesky factorization, or in terms of an LU factorization. It is explained how an LU, QR or \(LL^ t\) factorization of coefficient matrix is combined with the above rephrasing by which new feed-forward algorithms for solving systems of linear equations could be formed.
The systolic arrays for these methods are simple and with complexity in the order of a QR factorization. One of the methods (using only Givens rotations) is a numerically stable and robust method for the complete class of nonsingular systems. Simple extensions for these methods are also presented for computing expressions of the form \((B^ tA^{-t}C^ t+D^ t)\).
Reviewer: I.Arany


65F05 Direct numerical methods for linear systems and matrix inversion
65Y05 Parallel numerical computation
15A23 Factorization of matrices
Full Text: DOI