Parallelizing the QR Algorithm for the Unsymmetric Algebraic Eigenvalue Problem: Myths and Reality
Greg Henry, Robert A. Geijn · SIAM Journal on Scientific Computing · 1996
Over the last few years, it has been suggested that the popular QR algorithm for the unsymmetric Schur decomposition does not parallelize. In this paper, we present both positive and negative results on this subject. In theory, asymptotically perfect speedup can be obtained. In practice, reasonable speedup can be obtained on an MIMD distributed memory computer for a relatively small number of processors. However, we also show theoretically that it is impossible for the standard QR algorithm to be scalable. Performance of a parallel implementation of the LAPACK DLAHQR routine on the Intel ${\text{Paragon}}^{{\text{TM}}} $ system is reported.