A Parallel QR Algorithm for the Symmetrical Tridiagonal Eigenvalue Problem

The implicit QR algorithm is a serial iterative algorithm for determining all the eigenvalues of an n × n symmetric tridiagonal matrix A. About 3n iterations, each requiring the serial application of about n similarity planar transformations, are required to reduce A to diagonal form. In this paper we propose a parallel algorithm in which up to n/2 similarity transformations can be applied simultaneously. In contrast to the original algorithm, which cannot take advantage of the architectures of parallel or vector machines, each iteration of the new algorithm mainly involves synchronous, lock-step operations which can effectively use vector and concurrency capabilities of SIMD machines. In practice we have observed that the number of iterations of the parallel algorithm is about three times that of the serial algorithm, but because many of the operations can be done in parallel, the total computation time is less. On a two-processor Cray-XMP we often observe a factor of 3 speedup over the standard QR algorithm for problems with n = 800.