  We propose a fine-grained hypergraph model for sparse matrix-matrix
multiplication (SpGEMM), a key computational kernel in scientific computing and
data analysis whose performance is often communication bound. This model
correctly describes both the interprocessor communication volume along a
critical path in a parallel computation and also the volume of data moving
through the memory hierarchy in a sequential computation. We show that
identifying a communication-optimal algorithm for particular input matrices is
equivalent to solving a hypergraph partitioning problem. Our approach is
sparsity dependent, meaning that we seek the best algorithm for the given input
matrices.
  In addition to our (3D) fine-grained model, we also propose coarse-grained 1D
and 2D models that correspond to simpler SpGEMM algorithms. We explore the
relations between our models theoretically, and we study their performance
experimentally in the context of three applications that use SpGEMM as a key
computation. For each application, we find that at least one coarse-grained
model is as communication efficient as the fine-grained model. We also observe
that different applications have affinities for different algorithms.
  Our results demonstrate that hypergraphs are an accurate model for reasoning
about the communication costs of SpGEMM as well as a practical tool for
exploring the SpGEMM algorithm design space.
