Volume 23, pp. 158-179, 2006.

On fast factorization pivoting methods for sparse symmetric indefinite systems

Olaf Schenk and Klaus Gärtner

Abstract

This paper discusses new pivoting factorization methods for solving sparse symmetric indefinite systems. As opposed to many existing pivoting methods, our Supernode–Bunch–Kaufman (SBK) pivoting method dynamically selects $1\times 1$ and $2\times 2$ pivots and may be supplemented by pivot perturbation techniques. We demonstrate the effectiveness and the numerical accuracy of this algorithm and also show that a high performance implementation is feasible. We will also show that symmetric maximum-weighted matching strategies add an additional level of reliability to SBK. These techniques can be seen as a complement to the alternative idea of using more complete pivoting techniques during the numerical factorization. Numerical experiments validate these conclusions.

Full Text (PDF) [822 KB], BibTeX

Key words

direct solver, pivoting, sparse matrices, graph algorithms, symmetric indefinite matrix, interior point optimization

AMS subject classifications

65F05, 65F50, 05C85

ETNA articles which cite this article

Vol. 26 (2007), pp. 285-298 Sabine Le Borne and Suely Oliveira: Joint domain-decomposition $\mathcal{H}$-LU preconditioners for saddle point problems

Vol. 37 (2010), pp. 173-188 Sabine Le Borne and Che Ngufor: An implicit approximate inverse preconditioner for saddle point problems

Vol. 54 (2021), pp. 370-391 Murat Manguoğlu and Volker Mehrmann: A two-level iterative scheme for general sparse linear systems based on approximate skew-symmetrizers