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).


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.


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