Issues in the Design of Scalable Out-of-Core Dense Symmetric Indefinite Factorization Algorithms

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.