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