## On two-dimensional sparse matrix partitioning: Models, methods, and a recipe

### Umit V. Çatalyürek, Cevdet Aykanat, and Bora Uçar

Abstract. We consider two-dimensional partitioning of general
sparse matrices for parallel sparse matrix-vector multiply
operation. We present three hypergraph-partitioning based methods,
each having unique advantages. The first one treats the nonzeros of
the matrix individually and hence produces fine-grain partitions. The
other two produce coarser partitions, where one of them imposes a
limit on the number of messages sent and received by a single
processor, and the other trades that limit for a lower communication
volume. We also present a thorough experimental evaluation of the
proposed two-dimensional partitioning methods together with the
hypergraph-based one-dimensional partitioning methods, using an
extensive set of public domain matrices. Furthermore, for the users of
these partitioning methods, we present a partitioning recipe that
chooses one of the partitioning methods according to some matrix
characteristics.

Key words.
Sparse matrix partitioning;
parallel matrix-vector multiplication;
hypergraph partitioning;
two-dimensional partitioning;
combinatorial scientific computing