The LDL^T decomposition of a real symmetric matrix where L is lower triangular with unit diagonal and D diagonal except for 2x2 blocks is a challenge when the matrix is sparse and indefinite. Even if the matrix is reordered to limit fill-in, a small diagonal or an ill-conditioned 2x2 block may occur during the factorization. In this case, that pivot must be delayed until it is improved by updating.

Hogg and Scott [1] reviewed several pivoting strategies for sparse indefinite linear systems as applied to a set of particularly difficult symmetric indefinite systems. They found that matching-based strategies experienced fewer delayed pivots. In these methods, larger off-diagonal matrix entries are matched with smaller diagonal entries and moved together in hopes that the pair will form a well-conditioned block during factorization. This work describes a nested dissection (ND) algorithm [2] in which each stage is modified. Large off-diagonals match with small diagonals to form well-conditioned diagonal blocks while staying within the structure of the ND ordering.

The new method was tested using several problems that were identified by Hogg and Scott [1] as particularly challenging. The performance was compared with four other methods: an ordering using only ND code, a basic matching-based ordering, and two versions of another matching-based method. As a gauge of backward error, a generated system was solved for each factorization and the residual was reduced by iterative refinement. The results show that this numerically aware ND method required significantly fewer delayed pivots and flops than the other methods.