Math Seminar: "Core-Chasing Algorithms for Eigenvalue Computations"
4:10pm Neill 5W
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 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 algorithm, but that turns out not to be the case. In this talk we will discuss a new way of implementing Francis 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.