The multishift QR algorithm. I: Maintaining well-focused shifts and level 3 performance (Q2784389)

Recall that the rate of convergence of iterations in a single shift \(QR\) algorithm is ultimately quadratic. To avoid complex arithmetic, which may occur in the double shift \(QR\) factorization, the authors present a small bulge multishift variation of the \(QR\) algorithm. The method replaces a large diagonal bulge in the multishift \(QR\) sweep with a chain of many small bulges. This approach takes advantage of the existing level 3 BLAS, Basic Linear Algebra Subprograms, which are fast matrix-matrix operations that make near optimal use of the cache memory in computers with advanced architecture. Hardware count of floating point instructions executed by DHSEQR, TTQR, large bulge and small bulge multishift \(QR\) algorithms are compared on 20 non Hermitian eigenvalue problems.NEWLINENEWLINENEWLINE[For part II see ibid. 23, No.~4, 948-973 (2002; reviewed below)].