Hypergraph-partitioning-based decomposition for parallel sparse-matrix vector multiplication

In this work, we show that the standard graph-partitioning-based decomposit ion of sparse matrices does not reflect the actual communication volume req uirement for parallel matrix-vector multiplication. We propose two computat ional hypergraph models which avoid this crucial deficiency of the graph mo del. The proposed models reduce the decomposition problem to the well-known hypergraph partitioning problem. The recently proposed successful multilev el framework is exploited to develop a multilevel hypergraph partitioning t ool PaToH for the experimental verification of our proposed hypergraph mode ls. Experimental results on a wide range of realistic sparse test matrices confirm the validity of the proposed hypergraph models. In the decompositio n of the test matrices, the hypergraph models using PaToH and hMeTiS result in up to 63 percent less communication volume (30 to 38 percent less on th e average) than the graph model using MeTiS, while PaToH is only 1.3-2.3 ti mes slower than MeTiS on the average.