Numerical stability of some fast algorithms for structured matrices
173. R. P. Brent,
Numerical stability of some fast algorithms for structured matrices,
Proceedings of the of the Sixth Workshop on Scientific Computing
(Hong Kong, 10-12 March 1997), Springer-Verlag, 1998, 41-48.
(Workshop in celebration of Gene Golub's 65th birthday.)
Paper:
dvi (16K),
pdf (160K),
ps (61K).
Transparencies:
dvi (14K),
pdf (224K),
ps (121K).
Abstract
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
by Sweet and Brent [157],
Ming Gu, Michael Stewart and others
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.
Comments
The invited talk was dedicated to Gene Golub on the occasion of
his 65th birthday (counting one birthday per year, which is not
strictly correct since Gene was born on 29 February).
For an revised version of the paper,
see [177].
Go to next publication
Return to Richard Brent's index page