The use of weighted matchings is becoming increasingly standard in the
solution of sparse linear systems. While non-symmetric permutations based on these
matchings have been the state-of-the-art for
several years (especially for direct solvers), approaches for symmetric
matrices have only recently gained attention.
\\
In this talk we discuss results of our work on using weighted matchings in
the preconditioning of symmetric indefinite linear systems, following ideas
introduced by Duff and Gilbert. In order to maintain symmetry,
the weighted matching is symmetrized and the cycle structure of the
resulting matching is used to build reorderings that form small diagonal
blocks from the matched entries.
\\
For the preconditioning we investigated two approaches. One is an
incomplete $LDL^{T}$ preconditioning, that chooses 1x1 or 2x2 diagonal pivots
based on a simple tridiagonal pivoting criterion. The second approach
targets distributed computing, and is based on factorized sparse approximate
inverses, whose existence, in turn, is based on the existence of an $LDL^{T}$
factorization. Results for a number of comprehensive test sets are given,
including comparisons with sparse direct solvers and other preconditioning
approaches.