A parallel QR algorithm for the nonsymmetric eigenvalue problem

Daniel Boley, Robert Maier, Joung Kim

Research output: Contribution to journalArticlepeer-review

5 Scopus citations

Abstract

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(n2) 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.

Original languageEnglish (US)
Pages (from-to)61-70
Number of pages10
JournalComputer Physics Communications
Volume53
Issue number1-3
DOIs
StatePublished - May 1989

Bibliographical note

Funding Information:
* This research was partially supported by NSF grants DCR 8420935 and DCR-8519029 and by the Minnesota Super-computer Institute,

Fingerprint

Dive into the research topics of 'A parallel QR algorithm for the nonsymmetric eigenvalue problem'. Together they form a unique fingerprint.

Cite this