The Multi-Shift QR-Algorithm: Aggressive Deflation, Maintaining Well Focused Shifts, and Level 3 Performance

This paper presents two modifications to the multi-shift QR algorithm that significantly increase its effectiveness and efficiency. The first is to replace the large diagonal bulge in the multi-shift QR sweep with a chain of many small bulges. This avoids shift blurring that retards convergence and limits the number of simultaneous shifts. The small-bulge multishift QR sweep admits nearly any number of simultaneous shifts---even hundreds---without adverse effect on the convergence rate. With enough simultaneous shifts, the small-bulge multi-shift QR algorithm takes full advantage of the level 3 BLAS. This is a special advantage for computers with advanced architectures. The second modification is an aggressive early deflation strategy that identifies and deflates converged eigenvalues before the classical smallsubdiagonal strategy would. The new deflation strategy improves the performance of all QR algorithms (not just our implementation). Often, the small-bulge multi-shift QR sweep i..