Premium
Preordering saddle‐point systems for sparse L D L T factorization without pivoting
Author(s) -
Lungten Sangye,
Schilders Wil H.A.,
Scott Jennifer A.
Publication year - 2018
Publication title -
numerical linear algebra with applications
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.02
H-Index - 53
eISSN - 1099-1506
pISSN - 1070-5325
DOI - 10.1002/nla.2173
Subject(s) - saddle point , solver , mathematics , saddle , factorization , combinatorics , sparse matrix , matrix (chemical analysis) , block (permutation group theory) , linear system , a priori and a posteriori , block structure , discrete mathematics , algorithm , mathematical analysis , mathematical optimization , geometry , physics , philosophy , materials science , epistemology , quantum mechanics , composite material , gaussian , statistics , estimator
Summary This paper focuses on efficiently solving large sparse symmetric indefinite systems of linear equations in saddle‐point form using a fill‐reducing ordering technique with a direct solver. Row and column permutations partition the saddle‐point matrix into a block structure constituting a priori pivots of order 1 and 2. The partitioned matrix is compressed by treating each nonzero block as a single entry, and a fill‐reducing ordering is applied to the corresponding compressed graph. It is shown that, provided the saddle‐point matrix satisfies certain criteria, a block L D L T factorization can be computed using the resulting pivot sequence without modification. Numerical results for a range of problems from practical applications using a modern sparse direct solver are presented to illustrate the effectiveness of the approach.