QR FACTORIZATION OF TOEPLITZ MATRICES

A. W. BOJANCZYK, R. P. BRENT, AND F. R. DE HOOG

Abstract

This paper presents a new algorithm for computing the QR factorization of an m×n Toeplitz matrix in O(mn) operations. The algorithm exploits the procedure for the rank-1 modification and the fact that both principal (m−1)×(n−1) submatrices of the Toeplitz matrix are identical. An efficient parallel implementation of the algorithm is possible.

Comments

Only the Abstract is given here. The full paper appeared as [1]. For related work, see [2, 3, 4]. The algorithm described in [1] is more stable numerically than that of Sweet [4]. As noted

in [2], 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.

References

1. 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, CMA, ANU, May 1985; and as “Parallel QR factorization of Toeplitz matrices”, Proceedings SPIE, Volume 696, Advanced Algorithms and Architectures for Signal Processing, SPIE, Bellingham, Washington, 1986. rpb092.

2. R. P. Brent, “Parallel algorithms for Toeplitz systems”, Numerical Linear Algebra, Digital Signal Processing and Parallel Algorithms (edited by G. H. Golub and P. Van Dooren), Springer-Verlag, 1991, 75–92. rpb111.

3. A. W. Bojanczyk, R. P. Brent and F. R. de Hoog, Stability Analysis of Fast Toeplitz Linear System Solvers, Report CMA-MR17-91, Centre for Mathematical Analysis, ANU, August 1991, 23 pp. rpb126.

4. D. R. Sweet, “Fast Toeplitz orthogonalization”, Numerische Mathematik 43 (1984), 1–21.

Centre for Mathematical Analysis, Australian National University, Canberra

Computer Sciences Laboratory, Australian National University, Canberra

CSIRO Division of Mathematics and Statistics, GPO Box 1965, Canberra, ACT 2601

1991 Mathematics Subject Classification. Primary 65F25; Secondary 47B35, 65F05, 65F30, 65Y05, 65Y10.

Key words and phrases. Toeplitz matrix, orthogonal factorization, QR factorization, Cholesky factorization, semi-normal equations, rank-1 update, Sweet’s algorithm.

CR Categories. G1.3. Copyright \begin{matrix}c \\ ◯ \end{matrix} 1986, Springer-Verlag. Comments \begin{matrix}c \\ ◯ \end{matrix} 1993, R. P. Brent.

rpb092a typeset using AMS-L^{A}TEX