Volume 52, pp. 480-508, 2020.

On pole-swapping algorithms for the eigenvalue problem

Daan Camps, Thomas Mach, Raf Vandebril, and David S. Watkins

Abstract

Pole-swapping algorithms, which are generalizations of the QZ algorithm for the generalized eigenvalue problem, are studied. A new modular (and therefore more flexible) convergence theory that applies to all pole-swapping algorithms is developed. A key component of all such algorithms is a procedure that swaps two adjacent eigenvalues in a triangular pencil. An improved swapping routine is developed, and its superiority over existing methods is demonstrated by a backward error analysis and numerical tests. The modularity of the new convergence theory and the generality of the pole-swapping approach shed new light on bi-directional chasing algorithms, optimally packed shifts, and bulge pencils, and allow the design of novel algorithms.

Full Text (PDF) [376 KB], BibTeX

Key words

eigenvalue, QZ algorithm, pole swapping, convergence

AMS subject classifications

65F15, 15A18

Links to the cited ETNA articles

[27]	Vol. 40 (2013), pp. 17-35 Raf Vandebril and David S. Watkins: An extension of the QZ algorithm beyond the Hessenberg-upper triangular pencil

< Back