The Spectral Decomposition of Nonsymmetric Matrices
on Distributed Memory Parallel Computers
Next: Introduction
=-131072sp
The Spectral Decomposition of Nonsymmetric Matrices
on Distributed Memory Parallel Computers
Z. Bai
,
J. Demmel,
J. Dongarra,
A. Petitet,
H. Robinson,
K. Stanley
Mon Jan 9 11:10:01 EST 1995
Abstract:
We study the implementation and performance of
a class of algorithms for finding eigenvalues of nonsymmetric matrices
on distributed memory parallel computers. The algorithms perform spectral divide and conquer,
i.e. they recursively divide the matrix into smaller submatrices, each of which has
a subset of the original eigenvalues as its own.
One algorithm uses the matrix sign function evaluated with Newton iteration.
The other algorithm avoids the matrix inverse required by Newton iteration,
and so is called the inverse free algorithm.
Both algorithms are simply constructed from
a small set of highly parallelizable matrix building blocks,
including matrix multiplication, QR decomposition and matrix inversion.
Efficient implementations of these building blocks are available on
many machines. The price paid for easy parallelization
of these algorithms is potential loss of stability compared to the
best serial algorithm in some ill-conditioned cases.
Fortunately, the program can detect and compensate for this loss of
stability.
In our implementation of the sign function algorithm on a 256 processor Intel
Touchstone Delta system, the algorithm reached 31% efficiency with
respect to the underlying PUMMA matrix multiplication
on 4000-by-4000 matrices,
and 82% efficiency with respect to the underlying ScaLAPACK 1.0 (beta version) matrix inversion.
On a 32 node Thinking Machines CM-5 with vector units, on 2048-by-2048 matrices
the algorithm reached
41% efficiency with respect to the matrix multiplication in CMSSL 3.2.
Our performance model predicts the performance reasonably accurately.
To take advantage of the geometric nature of the spectral decomposition
algorithm, we have also designed a graphical user interface to let the
user choose which eigenvalues to compute.
Next: Introduction
Jack Dongarra
Mon Jan 9 11:07:50 EST 1995