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

## Abstract

We show that a fast algorithm for the
*QR* factorization of a Toeplitz or Hankel matrix
*A* is weakly stable in the
sense that *R*^{T}*R*
is close to *A*^{T}*A*.
Thus, when the algorithm is used
to solve the semi-normal equations
*R*^{T}*R**x* = *A*^{T}*b*,
we obtain a weakly stable method for the solution
of a nonsingular Toeplitz or Hankel linear system
*A**x* = *b*.
The algorithm also applies to the solution of the full-rank
Toeplitz or Hankel least squares problem.
## Comments

This paper appears to give the first weakly stable algorithm for the
solution of Toeplitz or Hankel systems in worst case
O(*n*^{2}) 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(*n*^{2}) operations.

Go to next publication

Return to Richard Brent's index page