An implementation of a reordering approach for increasing the product of diagonal entries in a sparse matrix

We present implementation details of a reordering strategy for permuting elements whose absolute value is large to the diagonal of a sparse matrix. This algorithm, based on work by Duff and Koster [9], is a critical component of the SPIKE-based preconditioner provided by the Spike::GPU library [2]. We discuss the four stages required to implement the equivalent bipartite graph matching problem and compare our implementation against the MC64 algorithm provided by the HSL library [1]. The performance of the reordering algorithm is evaluated in terms of efficiency as well as the quality of the resulting Spike::GPU preconditioner. Numerical experiments, performed on more than 100 matrices arising in various engineering and scientific applications, indicate that our implementation is more efficient than MC64 without any degradation in the quality of the resulting reordered matrix. The metric used in reaching this conclusion is the number of iterations required by the preconditioned sparse linear solver to approximate the solution within a prescribed tolerance.