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


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.


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