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.