Pole-Swapping Algorithms for Alternating and Palindromic Eigenvalue Problems

Pole-swappingalgorithmsaregeneralizationsofbulge-chasingalgorithms for the generalized eigenvalue problem. Structure-preserving pole-swapping algo- rithms for the palindromic and alternating eigenvalue problems, which arise in control theory, are derived. A refinement step that guarantees backward stability of the algorithms is included. This refinement can also be applied to bulge-chasing algorithms that had been introduced previously, thereby guaranteeing their back- ward stability in all cases.status: publishe