Uv. Catalyurek et C. Aykanat, Hypergraph-partitioning-based decomposition for parallel sparse-matrix vector multiplication, IEEE PARALL, 10(7), 1999, pp. 673-693
Citations number
40
Categorie Soggetti
Computer Science & Engineering
Journal title
IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS
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.