Publications

Brief announcement: Hypergraph partitioning for parallel sparse matrix-matrix multiplication

Ballard, Grey B.; Knight, Nicholas; Druinsky, Alex; Schwartz, Oded

The performance of parallel algorithms for sparse matrixmatrix multiplication is typically determined by the amount of interprocessor communication performed, which in turn depends on the nonzero structure of the input matrices. In this paper, we characterize the communication cost of a sparse matrix-matrix multiplication algorithm in terms of the size of a cut of an associated hypergraph that encodes the computation for a given input nonzero structure. Obtaining an optimal algorithm corresponds to solving a hypergraph partitioning problem. Our hypergraph model generalizes several existing models for sparse matrix-vector multiplication, and we can leverage hypergraph partitioners developed for that computation to improve applicationspecific algorithms for multiplying sparse matrices.