QR factorization of Toeplitz matrices
92. A. W. Bojanczyk, R. P. Brent and F. R. de Hoog,
QR factorization of Toeplitz matrices,
Numerische Mathematik 49 (1986), 81-94.
MR 87k:65050.
Also appeared as
Report CMA-R07-85, Centre for Mathematical Analysis, ANU, May 1985.
Abstract:
dvi (3K),
pdf (87K),
ps (31K).
Paper:
pdf (981K).
Abstract
This paper presents a new algorithm for computing the QR factorization
of an m x n Toeplitz matrix in
O(mn) operations.
The algorithm exploits procedures for the rank-1 modification
of a Cholesky factorisation [95]
and the fact that both principal
(m-1) x (n-1)
submatrices of the Toeplitz matrix are identical.
An efficient parallel implementation of the algorithm is possible.
Comments
The algorithm described here is more stable
numerically than that of
Sweet [Numerische Mathematik 43 (1984), 1-21].
As noted in [111],
the factor R in the orthogonal
factorization T = QR
is computed about as well as would be
expected from a Cholesky factorization of TTT.
However, the computed Q is not necessarily close to orthogonal.
For related work, see
[93,
144,
177].
Go to next publication
Return to Richard Brent's index page