Fast parallel algorithms for QR and triangular factorizations. (English) Zbl 0632.65023

Chun, J.; Kailath, T.; Lev-Ari, H.

SIAM J. Sci. Stat. Comput. 8, 899-913 (1987).

A fast QR type factorization algorithm for Toeplitz and Toeplitz-like matrices is proposed. The idea is that if A is Toeplitz or has a displacement rank form then \(A^ TA\) has again such a form, so that the triangular factor in the QR factorization can be obtained from the Cholesky factorization of \(A^ TA\) for which fast algorithms exist without forming \(A^ TA\) explicitly. The Q factor is then obtained by an appropriate downdating procedure applied to A. Unfortunately this latter procedure contains numerical instabilities due to the use of hyperbolic rotations rather than usual Givens rotation.

Reviewer: V.Mehrmann

MSC:

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

Keywords:

triangular factorization; displacement structure; Schur algorithm; Toeplitz matrix; QR factorization; Cholesky factorization; hyperbolic rotations; Givens rotation