Volume 20, pp. 50-63, 2005.

On the use of larger bulges in the QR algorithm

Daniel Kressner


The role of larger bulges in the QR algorithm is controversial. Large bulges are infamous for having a strong, negative influence on the convergence of the implicitly shifted QR algorithm. This paper provides a new explanation of this shift blurring effect, by connecting the computation of the first column of the shift polynomial to the notoriously ill-conditioned pole placement problem. To avoid shift blurring, modern variants of the QR algorithm employ chains of tightly coupled tiny bulges instead of one large bulge. It turns out that larger bulges still play a positive role in these variants; a slight increase of the bulge sizes often results in considerable performance improvements.

Full Text (PDF) [383 KB], BibTeX

Key words

QR algorithm, bulges, shift blurring, pole placement

AMS subject classifications

65F15, 15A18

Links to the cited ETNA articles

[22]Vol. 4 (1996), pp. 89-105 Volker Mehrmann and Hongguo Xu: An analysis of the pole placement problem. I. The single-input case

< Back