Node selection strategies for bottom-up sparse matrix ordering

作     者：Rothberg, E Eisenstat, SC 

作者机构：ILOG Inc Mt View CA 94043 USA Silcon Graph Inc Mt View CA USA Yale Univ Dept Comp Sci New Haven CT 06520 USA 

出 版 物：《SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS》 (工业与应用数学会矩阵分析和应用杂志)

年 卷 期：1998年第19卷第3期

页      面：682-695页

核心收录：

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

主　　题：sparse matrices ordering algorithms minimum degree minimum local fill minimum deficiency graph algorithms 

摘      要：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.