The open archive for STFC research publications

Full Record Details

Persistent URL http://purl.org/net/epubs/work/24428477
Record Status Checked
Record Id 24428477
Title Numerically-aware orderings for sparse symmetric linear systems
Abstract 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 2 2 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.
Organisation STFC , SCI-COMP , SCI-COMP-CM
Keywords sparse symmetric matrices , sparse matrix ordering , nested dissection , sparse direct methods , numerically aware ordering
Funding Information EPSRC (EP/M025179/1)
Related Research Object(s): 25845401 , 35371260
Licence Information:
Language English (EN)
Type Details URI(s) Local file(s) Year
Preprint RAL Preprints RAL-P-2016-004, ACM Trans Math Software 2016. RAL-P-2016-004.pdf 2016