STFC Website

part of UK Research & Innovation

Version 1.1.4

1st November 2023

HSL_MC80: Sparse symmetric matrix: matching-based ordering and scaling

Given a sparse symmetric matrix \(A\), this routine uses a matching algorithm to compute an elimination order that is suitable for use with a sparse direct solver. Scaling factors for \(A\) may also be computed. The routine is recommended for computing an ordering and scaling for tough symmetric indefinite systems (which may be singular) since it aims to move the largest off-diagonal entries alongside the diagonal to provide good initial pivots when used with a sparse direct solver.

Note that this ordering may result in the analyse phase of the solver predicting more entries in the factors than for an ordering computed using nested dissection or minimum degree. However, if combined with the scaling of \(A\), the matching ordering can often be used by the direct solver without modification to compute a numerically stable factorization.