Stability analysis of a general Toeplitz system solver

143. A. W. Bojanczyk, R. P. Brent and F. R. de Hoog, Stability analysis of a general Toeplitz system solver, Numerical Algorithms 10 (1995), 225-244. MR 97e:65031.

A preliminary version appeared as A weakly stable algorithm for general Toeplitz systems, Technical Report TR-CS-93-15, Computer Sciences Laboratory, ANU, August 1993 (revised June 1994). arXiv:1005.0503v1

Some of the results were presented in an invited talk at the SIAM Conference on Linear Algebra in Signals, Systems and Control, Seattle, August 1993.

Abstract: dvi (3K), pdf (33K), ps (30K).

Paper: pdf (1036K).

Technical Report: dvi (35K), pdf (219K), ps (72K).

Transparencies (from SIAM Conference talk, Seattle, 1993): dvi (24K), pdf (210K), ps (80K).


We show that a fast algorithm for the QR factorization of a Toeplitz or Hankel matrix A is weakly stable in the sense that RTR is close to ATA. Thus, when the algorithm is used to solve the semi-normal equations RTRx = ATb, we obtain a weakly stable method for the solution of a nonsingular Toeplitz or Hankel linear system Ax = b. The algorithm also applies to the solution of the full-rank Toeplitz or Hankel least squares problem.


This paper appears to give the first weakly stable algorithm for the solution of Toeplitz or Hankel systems in worst case O(n2) operations. (This bound can not be guaranteed for most "lookahead" algorithms.) For later work see Brent [177] and the references given there.

At the time of writing this paper we were not aware of a paper by S. Cabay and R. Meleshko ["A weakly stable algorithm for Padé approximants and the inversion of Hankel matrices", SIAM J. Matrix Anal. Appl. 15 (1993), 735-765], which gives a different weakly stable algorithm for the inversion of Toeplitz/Hankel matrices, usually (but not always) in O(n2) operations.

Go to next publication

Return to Richard Brent's index page