HSL_MC64
Sparse matrix scaling and ordering
HSL_MC64 is an powerful tool for preprocessing sparse matrices for direct or iterative methods. It uses a weighted bipartite graph matching to determine a high quality scaling for a matrix. This matching can be used in the unsymmetric case to permute large entries onto the diagonal; in the symmetric case large entries can be permuted next to the diagonal. This enhances the performance of the linear solver.
Functionality
- Implements a weighted bipartite matching algorithm to find a set of entries, no two of which are in the same row and column, so that their product or sum is maximized.
- Input matrix can be symmetric, unsymmetric, or rectangular.
- Row and column permutation vectors are returned so that large entries can be identified and, if desired, can be permuted to the diagonal.
- Can scale such that identified large entries have modulus one and all other entries have modulus less than or equal to one.
- Detects structural rank.
Performance
- Always finds a set of entries that minimizes the objective function.
- HSL_MC64 is generally fast compared to the time for solving the preprocessed system.
- Algorithm used in many of the market leading sparse direct codes including MA57, MUMPS, PARDISO, and SuperLU.
Availability
We offer both in-house usage and incorporation licences for HSL_MC64. It is freely available for academic use. Please see our website, or email us at hsl@stfc.ac.uk for further details.
[1] I. S. Duff and J. Koster (1997), The design and use of algorithms for permuting large entries to the diagonal of sparse matrices, SIAM J Matrix Analysis and Applications, 20, (4), 889-901.
[2] I. S. Duff and J. Koster (1999), On algorithms for permuting large entries to the diagonal of a sparse matrix, SIAM J Matrix Analysis and Applications, 22, (4), 973-996.