Accessibility navigation


Numerically-aware orderings for sparse symmetric indefinite linear systems

Hogg, J., Scott, J. 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

[img]
Preview
Text - Accepted Version
· Please see our End User Agreement before downloading.

421kB

It is advisable to refer to the publisher's version if you intend to cite from this work. See Guidance on citing.

To link to this item 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
Refereed:Yes
Divisions:Faculty of Science > School of Mathematical, Physical and Computational Sciences > Department of Mathematics and Statistics
ID Code:71797
Publisher:ACM

Downloads

Downloads per month over past year

University Staff: Request a correction | Centaur Editors: Update this record

Page navigation