New distributed-memory parallel algorithms for solving nonsymmetric eigenvalue problems
Liwei Wu, Eleanor Chu · PPSC · 1995
In this article we present new distributed-memory parallel algorithms for finding all eigenvalues of a general real matrix using Hessenberg reduction and implicit double-shift QR iterations. The parallel algorithm for Hessenberg reduction employs a two-dimensional {gamma}1 x {gamma}2 subcube-grid network. A two-dimensional data wrap-mapping scheme and the subcube-doubling communication technique are adopted. The advantages are: the communication volume can be minimized by appropriate choices of {gamma}1 and {gamma}2; furthermore, the lengths of the messages exchanged during the row transformation and the column transformation are decreasing as {gamma}1 and {gamma}2 increase, respectively. The second parallel algorithm finds the complete set of eigenvalues of an upper Hessenberg matrix by QR iterations. It uses a novel dynamic block-diagonal wrap-mapping scheme to allocate data to the processors on a ring communication network, which facilitates temporary data relocation to match the data access pattern in each double-shift QR iteration. The proposed dynamic data mapping/relocation strategy improves the workload balancing and reduces the processor idle time. This enhancement is shown to be effective in solving large-scale problems.