Washington State University
Combinatorics, Linear Algebra and Number Theory (CLaN) Seminar
Department of Mathematics
Neill Hall 5W
September 21, Monday, 4:10 - 5:00 PM
David S. Watkins
Department of Mathematics
Washington State University
Combinatorics, Linear Algebra and Number Theory (CLaN) Seminar
Department of Mathematics
Neill Hall 5W
September 21, Monday, 4:10 - 5:00 PM
David S. Watkins
Department of Mathematics
Washington State University
Title: Core-Chasing Algorithms for Eigenvalue Computation
Abstract: 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.
Abstract: 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.