Node Selection Strategies for Bottom-Up Sparse Matrix Ordering

The minimum degree and minimum local fill algorithms are two bottom-up heuristics for reordering a sparse matrix prior to factorization. Minimum degree chooses a node of least degree to eliminate next; minimum local fill chooses a n ode whose elimination creates the least fill. Contrary to popular belief, we find that minimum local fill produces significantly better orderings than minimum degree, albeit at a greatly increased runtime. We describe two simple modifications to this strategy that further improve ordering quality. We also describe a simple modification to minimum degree, which we term approximate minimum mean local fill, that reduces factorization work by roughly 25% with only a small increase in runtime.