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 $\theta (n^{\log _3 4} )$ for $n \times n$ matrices whose zero/nonzero structure corresponds to a torus graph with an optimal fill-in of $\theta (n\log n)$ is exhibited. Experimental results suggest that random tie resolution yields a similar fill-in.