LECTURE 3
Fast and numerically stable algorithms for structured matrices
In this lecture we
consider the numerical stability/instability of fast algorithms for solving
systems of linear equations or linear least squares problems with a low
displacement-rank structure. For example, the matrices involved may be
Toeplitz
or
Hankel.
In particular, we consider algorithms which incorporate
pivoting without destroying the structure, such as the
Gohberg-Kailath-Olshevsky
(GKO) algorithm, and
describe some recent results
on the stability of these algorithms.
We also compare these results with the corresponding stability
results for algorithms based on
the semi-normal equations and for the well known algorithms of
Schur/Bareiss
and
Levinson/Wiener/Kolmogorov.
Related lectures
Bibliography and links
-
A. W. Bojanczyk,
R. P. Brent and F. R. de Hoog,
QR factorization of Toeplitz matrices,
Numerische Mathematik 49 (1986), 81-94.
-
A. W. Bojanczyk, R. P. Brent and F. R. de Hoog,
Stability analysis of a general Toeplitz systems solver,
Numerical Algorithms 10 (1995), 225-244.
-
A. W. Bojanczyk, R. P. Brent, F. R. de Hoog and D. R. Sweet,
On the stability of the Bareiss and related Toeplitz factorization algorithms,
SIAM J. Matrix Anal. Appl. 16 (1995), 40-57.
-
R. P. Brent,
Stability of fast algorithms for structured linear systems,
Tech. Report TR TR-CS-97-18,
ANU, September 1997.
Revision in Fast Reliable Algorithms for Matrices with Structure
(editors,
Ali. H. Sayed
and
Thomas Kailath),
SIAM, Philadelphia, 1999, to appear.
-
R. P. Brent, F. G. Gustavson and D. Y. Y. Yun,
Fast solution of Toeplitz
systems of equations and computation of Padé
approximants,
J. Algorithms 1 (1980), 259-295.
-
D. R. Sweet and R. P. Brent,
Error analysis of a fast partial pivoting method for
structured matrices,
Tech. Report TR-CS-95-03, ANU, June 1995.
Revision in
Proceedings SPIE, Volume 2563, Advanced Signal Processing Algorithms,
SPIE, Bellingham, Washington, 1995, 266-280.
Compressed postscript file of the transparencies used in the lecture
Go to next lecture
Return to list of special lectures on algorithms