On the Performance of the Minimum Degree Ordering for Gaussian Elimination
Piotr Berman, Georg Schnitger · SIAM Journal on Matrix Analysis and Applications · 1990
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.