A nested dissection partitioning method for parallel sparse matrix-vector multiplication

We consider how to map sparse matrices across processes to reduce communication costs in parallel sparse matrix-vector multiplication, an ubiquitous kernel in high performance computing. 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 that approximately solves this model. We have implemented our algorithm using hypergraph partitioning software to enable a fair comparison with existing methods. We present partitioning results for sparse structurally symmetric matrices from several application areas. Our new method is competitive with the best 2D algorithm (fine-grain hypergraph model) in terms of communication volume, but requires fewer messages. The nested dissection method is almost as fast to compute as 1D methods and the communication volume is significantly reduced (up to 97%) compared to 1D layout. Further improvements in quality may be possible by small modifications to existing nested dissection ordering software.