A parallel QR algorithm for the nonsymmetric eigenvalue problem

This paper describes a prototype parallel algorithm for approximating eigenvalues of a dense nonsymmetric matrix on a linear, synchronous processor array. The algorithm is parallel implementation of the explicitly-shifted QR, employing n distributed-memory processors to deliver all eigenvalues in O(n²) time. The algorithm uses Givens rotations to generate a series of unitary similarity transformations. The rotations are passed between neibouring processors and applied, in pipeline fashion, to columns of the matrix. The rotations are also accumulated in a unitary transformation matrix, enabling the solution of eigenvectors via back-substitution and back-transformation. The algorithm involves only local communication, and confronts the problems of convergence, splitting and updating the shift in a pipelined scheme. The algorithm is implemented on a hypercube, using a ring of processors to simulate a systolic array. Experimental results on the NCUBE/seven hypercube show O(n) speedup over competing sequential codes, despite the overhead of interprocessor communication. Speedup and efficiency are estimated by comparing with EISPACK performance.