The Design of Scalable Out-of-core Dense Symmetric Indefinite Factorization Algorithms

Peter E. Strazdins, Issues in the Design of Scalable Out-of-core Dense Symmetric Indefinite Factorization Algorithms, Computational Science -- ICCS 2003, Lecture Notes in Computer Science 2659, III:715-724, Springer-Verlag, Melbourne, June 2003.

Contents

Abstract

In the factorization of indefinite symmetric linear systems, symmetric pivoting is required to maintain numerical stability, while attaining a reduced floating point operation count.

However, symmetric pivoting presents many challenges in the design of efficient algorithms, and especially in the context of a parallel out-of-core solver for dense systems. Here, the search for a candidate pivot in order to eliminate a single column potentially requires a large number of messages and accesses of disk blocks.

In this paper, we look at the problems of scalability in terms of number of processors and the ratio of data size relative to aggregate memory capacity for these solvers. We find that diagonal pivoting methods which exploit locality of pivots offer the best potential to meet these demands. A left-looking algorithm based on an exhaustive block-search strategy for dense matrices is described and analysed; its scalability in terms of parallel I/O is dependent on being able to find stable pivots near or within the current elimination block.

Keywords

dense linear algebra, block cyclic decomposition, parallel computing, symmetric indefinite factorization, ouot-of-core methods, LDLT decomposition.