## 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\times1$ and $2\times2$ 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

 Vol. 26 (2007), pp. 285-298 Sabine Le Borne and Suely Oliveira: Joint domain-decomposition ${\cal 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