Module matching 

MC64 weighted bipartite matching and symmetric scaling. MC64 weighted bipartite matching and symmetric scaling.

Implements the Duff & Koster (2001) Algorithm MPD — Dijkstra-based shortest augmenting path matching on a logarithmic cost graph — with the MC64SYM symmetric scaling from Duff & Pralet (2005).

MC64 preprocessing improves diagonal dominance of sparse symmetric indefinite matrices, reducing delayed pivots in subsequent APTP factorization. The algorithm produces:

• A matching permutation decomposing into singletons and 2-cycles
• Symmetric scaling factors such that the scaled matrix has unit matched diagonal and off-diagonal entries bounded by 1 in absolute value

Algorithm

1. Build a bipartite cost graph with c[i,j] = log(col_max_j) - log|a[i,j]|
2. Compute initial dual variables and greedy matching (~80% cardinality)
3. For each unmatched column, find shortest augmenting path via Dijkstra
4. Symmetrize scaling: s[i] = exp(-(u[i] + v[i]) / 2)

References

• Duff & Koster (2001), “On Algorithms for Permuting Large Entries to the Diagonal of a Sparse Matrix”, SIAM J. Matrix Anal. Appl. 22(4)
• Duff & Pralet (2005), “Strategies for Scaling and Pivoting for Sparse Symmetric Indefinite Problems”, RAL Technical Report

Structs

Mc64Result

Result of MC64 matching-based preprocessing.

Enums

Mc64Job

Optimization objective for the matching.

Functions

count_cycles

Count singletons, 2-cycles, and longer cycles in a matching permutation.

mc64_matching

Compute MC64 weighted bipartite matching and symmetric scaling for a sparse symmetric matrix.