An Efficient and Stable Method for Parallel Factorization of Dense
Symmetric Indefinite Matrices
P.E. Strazdins and J.G. Lewis,
An Efficient and Stable Method for Parallel Factorization of Dense
Symmetric Indefinite Matrices
,
The 5th International Conference and Exhibition on High
Performance Computing in the Asia-Pacific Region
(HPC Asia 2001), Gold Coast, Sep, 2001
Contents
Abstract
This paper investigates the efficient parallelization of algorithms with
strong stability guarantees to factor dense symmetric indefinite
matrices. It shows how the bounded Bunch-Kaufman algorithm may be
efficiently parallelized, and then how its performance can be enhanced
by using exhaustive block searching techniques, which is effective in
keeping most symmetric interchanges within the current elimination
block. This can avoid wasted computation and the communication normally
involved in parallel symmetric interchanges, but requires considerable
effort to reduce its introduced overheads. It has also
great potential for out-of-core algorithms.
Results on a 16 node Fujitsu AP3000 multicomputer showed the block
search increased performance over the (plain) bounded
Bunch-Kaufman algorithm by 5--14% on strongly indefinite matrices, and
in some cases out-performing the well-known Bunch-Kaufman algorithm
(which is without strong stability guarantees).
Keywords
dense linear algebra, block cyclic decomposition,
parallel computing, symmetric indefinite factorization,
LDLT decomposition.