## 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 *T*^{T}*T*.
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