Computational Mathematics and Scientific Computing Seminar

Core-Chasing Algorithms for Eigenvalue Computation

Speaker: David Watkins, Washington State University

Location: Warren Weaver Hall 1302

Date: Nov. 6, 2015, 10 a.m.


At the dawn of the electronic computing era nobody knew how to compute the eigenvalues of a general matrix in an efficient and stable way. This was one of the major problems for the infant field of numerical linear algebra. In 1959 young John Francis came up with an ingenious method that has turned out to be the winning algorithm so far. The method has seen modifications over the years, but it is still Francis's algorithm. No radically different competing method has come close to displacing it. One might think that after more than fifty years there would be nothing more to say about Francis's algorithm, but that turns out not to be the case. In this talk we will discuss a new way of implementing Francis's algorithm that has some advantages. In particular, it leads to the first fast and (proven) backward-stable algorithm for computing the eigenvalues of a companion matrix.