Numerically-aware orderings for sparse symmetric indefinite linear systems

Hogg, J., Scott, J. ORCID: https://orcid.org/0000-0003-2130-1091 and Thorne, S. (2017) Numerically-aware orderings for sparse symmetric indefinite linear systems. ACM Transactions on Mathematical Software (TOMS), 44 (2). pp. 1-22. ISSN 0098-3500 doi: 10.1145/3104991

Abstract/Summary

Sparse symmetric indefinite problems arise in a large number of important application areas; they are often solved through the use of an LDLT factorization via a sparse direct solver. Whilst for many problems, prescaling the system matrix A is sufficient to maintain stability of the factorization, for a small but important fraction of problems numerical pivoting is required. Pivoting often incurs a significant overhead and consequently a number of techniques have been proposed to try and limit the need for pivoting. In particular, numerically-aware ordering algorithms may be used, that is, orderings that depend not only on the sparsity pattern of A but also on the values of its (scaled) entries. Current approaches identify large entries of A and symmetrically permute them onto the subdiagonal where they can be used as part of a 2x2 pivot. This is numerically effective, but the fill in the factor L and hence the runtime of the factorization and subsequent triangular solves may be significantly increased over a standard ordering if no pivoting is required. We present a new algorithm that combines a matching-based approach with a numerically-aware nested dissection ordering. Numerical comparisons with current approaches for some tough symmetric indefinite problems are given.

Item Type	Article
URI	https://reading-clone.eprints-hosting.org/id/eprint/71797
Item Type	Article
Refereed	Yes
Divisions	Science > School of Mathematical, Physical and Computational Sciences > Department of Mathematics and Statistics
Publisher	ACM
Download/View statistics	View download statistics for this item