A parallel QR algorithm for the nonsymmetric eigenvalue problem

✍ Scribed by Daniel Boley; Robert Maier; Joung Kim

• Publisher: Elsevier Science
• Year: 1989
• Tongue: English
• Weight: 973 KB
• Volume: 53
• Category: Article
• ISSN: 0010-4655
• DOI: 10.1016/0010-4655(89)90148-3

✦ Synopsis

This paper describes a prototype parallel algorithm for approximating eigenvalues of a dense nonsymmetric matrix on a linear, synchronous processor array. The algorithm is a parallel implementation of the explicitly-shifted QR, employing n distributed-memory processors to deliver all eigenvalues in c9( n 2) time. The algorithm uses Givens rotations to generate a series of unitary similarity transformations. The rotations are passed between neighboring 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 t!2(n) speedup over competing sequential codes, despite the overhead of interprocessor communication. Speedup and efficiency are estimated by comparing with EISPACK performance.