IMPROVING THE RUN-TIME AND QUALITY OF NESTED DISSECTION ORDERING

When performing sparse matrix factorization, the ordering of matrix ro ws and columns has a dramatic impact on the factorization time. This p aper describes an approach to the reordering problem that produces sig nificantly better orderings than prior methods. The algorithm is a hyb rid of nested dissection and minimum degree ordering, and combines an assortment of different algorithmic advances. New or improved algorith ms are described for graph compression, multilevel partitioning, and s eparator improvement. When these techniques are combined, the resultin g orderings average 39% better than minimum degree over a suite of tes t matrices, while requiring roughly 2.7 times the run time of Liu's mu ltiple minimum degree.