CLaN Research Group | CLaN
Seminar | WSU Colloquium | Department Home

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.