`Parallelizing the QR Algorithm for
the Unsymmetric Algebraic Eigenvalue Problem: Myths and Reality
- Greg Henry
- Intel SSD
- Intel Corporation
- 14924 N.W. Greenbrier Pkwy
- Beaverton, OR 97006
- henry@ssd.intel.com
- Robert A. van de Geijn
- Department of Computer Sciences
- University of Texas
- Austin, TX 78712
- rvdg@cs.utexas.edu
Abstract
Over the last few years, it has been suggested that
the popular QR algorithm for the unsymmetric eigenvalue
problem 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 a 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 Paragon (TM) system is reported.
Greg Henry and Robert van de Geijn, ``Parallelizing the QR Algorithm for
the Unsymmetric Algebraic Eigenvalue Problem: Myths and Reality,''
LAPACK Working Note 79 , University of Tennessee, Aug. 1994.
Submitted to SIAM Journal on Scientific Computing.