Stability of fast algorithms for structured linear systems
177. R. P. Brent,
Stability of fast algorithms for structured linear systems,
in Fast Reliable Algorithms for Matrices with Structure
(edited by Ali Sayed and Thomas Kailath),
SIAM, Philadelphia, 1999, 103-116.
Preliminary version available as Technical Report TR-CS-97-18,
CSL, ANU, September 1997, 13 pp.
We survey the numerical stability of some fast algorithms for solving
systems of linear equations and linear least squares problems with a low
displacement-rank structure. For example, the matrices involved may be
Toeplitz or Hankel. We consider algorithms which incorporate
pivoting without destroying the structure,
and describe some recent results
on the stability of these algorithms.
We also compare these results with the corresponding stability
results for the well known algorithms of Schur/Bareiss and Levinson,
and for algorithms based on the semi-normal equations.
The "low displacement rank" matrices considered here include
Toeplitz, Hankel and Cauchy matrices as special cases.
This survey is a revision of .
for some of the original papers.
Go to next publication
Return to Richard Brent's index page