Abstract:
When performing sparse matrix factorization, the ordering of matrix rows and columns has a dramatic impact on the factorization time. This paper describes an approach to the reordering problem that produces significantly better orderings than existing methods. The algorithm is a hybrid of nested dissection and minimum degree ordering, and combines an assortment of different algorithmic advances. New or improved algorithms are described for graph compression, multilevel partitioning and vertex cover. When these techniques are combined, the resulting orderings average 35\% better than minimum degree over a suite of test matrices, while requiring roughly 2.7 times the runtime of Liu's Multiple Minimum Degree.