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

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


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