I keep forgetting to write this up, but it’s related to static pivoting for symmetric indefinite problems. Existing work forms a weighted matching on the log of a matrix’s elements as in Schenk and Gärtner, 2006 and Duff and Pralett, 2005.

Both report limited success, but they’re using the wrong weights and making the problem far too complicated.

Don’t use the matrix’s elements, use the potential pivots. In the symmetric indefinite case, that means replacing the off-diagonal elements by the 2x2 determinant of the respective submatrix. Element A(i, j) with i ≠ j is replaced by abs (det ([A(i,i), A(i,j); A(j,i), A(j,j)])). Element A(i,i) is replaced by abs (A(i,i)) and is treated as a self-loop. If a maximum-weight matching pairs i with itself, use a 1x1 pivot. Otherwise use the respective 2x2 pivot. No need to find cycles, break loops, etc.

I haven’t tested the idea thoroughly, but I can’t see how it possibly could be worse than the more contrived contraptions. This feels like the natural analog, and also could map perturbations of small pivots directly to original entries.