QR algorithm with optimally packed chains of bulges
Summary
The QR algorithm is the method of choice for computing all eigenvalues of a dense nonsymmetric matrix A. After an initial reduction to Hessenberg form, a QR iteration can be viewed as chasing a small bulge from the top left to the bottom right corner along the subdiagonal of A. To increase data locality and create potential for parallelism, modern variants of the QR algorithm perform several iterations simultaneously, which amounts to chasing a chain of several bulges instead of a single bulge. To make effective use of level~3 BLAS, it is important to pack these bulges as tightly as possible within the chain. It turns out that the tightness of the packing in existing approaches is not optimal and can be increased. The software below realizes this idea, based on the current LAPACK implementation.
Software
newqr.tar.gz
Tar ball containing a modification of the LAPACK implementation of the QR algorithm.
Reference
- L. Karlsson, D. Kressner, and B. Lang. Optimally packed chains of bulges in multishift QR algorithms. 2013. (PDF)