At the beginning of the era of electronic computing there was a big effort to produce software to make the newly constructed hardware useful. In the area of scientific computing, one need that was recognized early on was for efficient and reliable methods to compute the eigenvalues of a matrix. This need was met around 1960 by the so-called QR algorithm, especially the implicitly-shifted variant due to John Francis. For the generalized eigenvalue problem, Moler and Stewart introduced a variant of Francis’s algorithm called the QZ algorithm. These algorithms, with various bells and whistles added over the years, are still the dominant algorithms today. These are bulge-chasing algorithms. They create bulges at one end of a (Hessenberg) matrix or pencil and chase them to the other end. A few years ago a new class of algorithms, pole-swapping algorithms, was introduced by Camps, Meerbergen, Vandebril, and others. It turns out that pole swapping is a generalization of bulge chasing. It might happen that new pole-swapping codes will supplant the current QR and QZ codes in the major software packages. Whether this turns out to be true or not, the pole-swapping viewpoint is extremely valuable for a detailed understanding of what makes this class of algorithms–both bulge-chasing and pole-swapping–work.
Refreshments will be served preceding the talk, beginning at 2:45.