PARALLELIZING THE QR ALGORITHM FOR THE UNSYMMETRIC ALGEBRAIC EIGENVALUE PROBLEM - MYTHS AND REALITY

Over the last few years, it has been suggested that the popular QR alg orithm for the unsymmetric Schur decomposition does not parallelize. I n this paper, we present both positive and negative results on this su bject. In theory, asymptotically perfect speedup can be obtained. In p ractice, reasonable speedup can be obtained on an MIMD distributed mem ory computer for a relatively small number of processors. However, we also show theoretically that it is impossible for the standard QR algo rithm to be scalable. performance of a parallel implementation of the LAPACK DLAHQR routine on the Intel Paragon(TM) system is reported.