## Revisiting hypergraph models for sparse matrix partitioning

### Bora Uçar and Cevdet Aykanat

Abstract.
We provide an exposition of hypergraph models for parallelizing sparse
matrix-vector multiplies. Our aim is to emphasize the expressive power
of hypergraph models. First, we set forth an elementary hypergraph
model for parallel matrix-vector multiply based on one-dimensional
(1D) matrix partitioning. In the elementary model, the vertices
represent the data of a matrix-vector multiply, and the nets encode
dependencies among the data. We then apply a recently proposed
hypergraph transformation operation to devise models for 1D sparse
matrix partitioning. The resulting 1D partitioning models are
equivalent to the previously proposed computational hypergraph models
and are not meant to be replacements for them. Nevertheless, the new
models give us insights into the previous ones and help us explain a
subtle requirement, known as the consistency condition, of the
hypergraph partitioning models. Later, we demonstrate the flexibility
of the elementary model on a few 1D partitioning problems that are
hard to solve using the previously proposed models. We also discuss
extensions of the proposed elementary model to two-dimensional matrix
partitioning.

Key words. parallel computing, sparse matrix-vector multiply, hypergraph models