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

Jainandunsing, K.; Deprettere, E. F.

SIAM J. Sci. Stat. Comput. 10, No. 5, 880-912 (1989).

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

MSC:

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

Keywords:

QR factorization with backsubstitution; Faddeev’s feed-forward method; Cholesky factorization; LU factorization; systolic arrays; Givens rotations