Title :
An asymptotically 100% efficient parallel implementation of the nonsymmetric QR algorithm
Author :
Hudson, Duncan G., III ; Van de Geijn, Robert A.
Author_Institution :
Dept. of Comput. Sci., Texas Univ., Austin, TX, USA
Abstract :
The QR algorithm has proven to be the most successful sequential algorithm for finding all eigenvalues of a dense nonsymmetric matrix. Recently, several parallel implementations of the QR algorithm have been proposed. These implementations have all been based on the column-wrapped storage scheme. While column-wrapped storage has been used to obtain asymptotically 100% efficiency for many algorithms for solving linear systems, eigenvalue algorithms using such storage have achieved, at best, asymptotically constant efficiency. The authors present a parallel implementation of the QR algorithm that makes use of an alternate storage scheme that allows them to achieve asymptotically 100% efficiency. They also present a technique, which they call bundling, that further improves the observed efficiency of the parallel implementation
Keywords :
eigenvalues and eigenfunctions; matrix algebra; parallel algorithms; storage management; block Hankel-wrapped storage; bundling; column-wrapped storage scheme; dense nonsymmetric matrix; eigenvalue algorithms; linear systems; nonsymmetric QR algorithm; Arithmetic; Concurrent computing; Distributed computing; Eigenvalues and eigenfunctions; Jacobian matrices; Linear systems; Parallel algorithms; Parallel architectures; Performance analysis; Timing;
Conference_Titel :
Parallel and Distributed Processing, 1990. Proceedings of the Second IEEE Symposium on
Conference_Location :
Dallas, TX
Print_ISBN :
0-8186-2087-0
DOI :
10.1109/SPDP.1990.143541
