DOE OSTI · 947836
A nested dissection approach to sparse matrix partitioning for parallel computations.
Abstract
We consider how to distribute sparse matrices among processes to reduce communication costs in parallel sparse matrix computations, specifically, sparse matrix-vector multiplication. Our main contributions are: (i) an exact graph model for communication with general (two-dimensional) matrix distribution, and (ii) a recursive partitioning algorithm based on nested dissection (substructuring). We show that the communication volume is closely linked to vertex separators. We have implemented our algorithm using hypergraph partitioning software to enable a fair comparison with existing methods. We present numerical results for sparse matrices from several application areas, with up to 9 million nonzeros. The results show that our new approach is superior to traditional 1d partitioning and comparable to a current leading partitioning method, the finegrain hypergraph method, in terms of communication volume. Our nested dissection method has two advantages over the fine-grain method: it is faster to compute, and the resulting distribution requires fewer communication messages.
Explore related subjects
Keep this discovery
Explore connections, maps & timelines
Wolf, Michael M, Boman, Erik Gunnar. 2008-08-01. A nested dissection approach to sparse matrix partitioning for parallel computations.. https://searchnasa.com/record/osti%3A947836/a-nested-dissection-approach-to-sparse-matrix-partitioning-for-parallel-computations
Citations retain the original authors and DOI and include this site’s record URL. If this discovery service contributed to your research, you can also cite Search NASA by Indiciae: BibTeX · RIS.