On the Performance of the Minimum Degree Ordering for Gaussian Elimination

The minimum degree ordering for Gaussian elimination is considered. A way to resolve ties that results in a fill-in of θ (nlog ₃ 4 ) for n × n matrices whose zero/nonzero structure corresponds to a torus graph with an optimal fill-in of θ (nlog n) is exhibited. Experimental results suggest that random tie resolution yields a similar fill-in.