Title: Hypergraph-Partitioning-Based Decomposition for Parallel Sparse-Matrix Vector Multiplication
Authors: Umit V. Catalyurek and Cevdet Aykanat
Status: Published in  IEEE Transactions on Parallel and Distributed Systems, vol. 10, n0. 7, pp. 673-693, 1999.

Abstract:

In this work, we show that the standard graph-partitioning based decomposition of sparse matrices does not reflect the actual communication
volume requirement for parallel matrix-vector multiplication. We propose two computational hypergraph models which avoid this crucial deficiency of the graph model. The proposed models reduce the decomposition problem to the well-known hypergraph partitioning problem.
The recently proposed successful multilevel framework is exploited to develop a multilevel hypergraph partitioning tool PaToH for the experimental verification of our proposed hypergraph models. Experimental results on a wide range of realistic sparse test matrices confirm the validity of the proposed hypergraph models. In the decomposition of the test matrices, the hypergraph models using PaToH and hMeTiS result in up to 63%less communication volume (30%--38% less on the average) than the graph model using MeTiS, while PaToH is only 1.3--2.3 times slower than MeTiS on the average.

Full paper