on sparse matrix reordering for parallel factorization
To minimize the amount of computation and storage for parallel sparse factorization, sparse matrices have to be reordered prior to factorization. We show that none of the popular ordering heuristics proposed before, namely, mulitple minimum degree and nested dissection, perform consistently well over a range of matrices arising in diverse application domains. Spectral partitioning has been previously proposed as a means of generating small vertex separators for nested dissection of sparse matrices, so that the resulting ordering is amenable to efficient distributed parallel factorization with good load balance and low inter-processor communication. We show that nested dissection using spectral partitioning performs well for matrices arising from finite-element discretizations, but results in excessive fill compared to the minimum degree ordering for unstructured matrices such as power matrices and those arising from circuit simulation. The relative effectiveness of these two ordering schemes for parallel factorization is shown to vary widely for matrices arising from different application domains. We present an ordering strategy that performs consistently well for all matrix types. Its ordering is comparable or better than either minimum degree or nested dissection for all matrices evaluated. Performance results on the Intel iPSC/860 are reported.
matrix reordering parallel sparse factorization nested dissection spectral partitioning distributed memory machine