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

Compressed postscript file of the transparencies used in the lecture

Go to next lecture

Return to list of special lectures on algorithms