A Medium-Grain Method for Fast 2D Bipartitioning of Sparse Matrices

• Main Authors: Pelt, Daniel M., Bisseling, Rob H.
• Format: Conference Proceeding
• Language: English
• Subjects: Computational modeling; hypergraph; Iterative methods; Load modeling; Matrix converters; parallel computing; Solid modeling; Sparse matrices; sparse matrix-vector multiplication; Vectors
• ISSN: 1530-2075
• DOI: 10.1109/IPDPS.2014.62

We present a new hyper graph-based method, the medium-grain method, for solving the sparse matrix partitioning problem. This problem arises when distributing data for parallel sparse matrix-vector multiplication. In the medium-grain method, each matrix nonzero is assigned to either a row group or a column group, and these groups are represented by vertices of the hyper graph. For an m×n sparse matrix, the resulting hyper graph has m+n vertices and m+n hyper edges. Furthermore, we present an iterative refinement procedure for improvement of a given partitioning, based on the medium-grain method, which can be applied as a cheap but effective post processing step after any partitioning method. The medium-grain method is able to produce fully two-dimensional bipartitionings, but its computational complexity equals that of one-dimensional methods. Experimental results for a large set of sparse test matrices show that the medium-grain method with iterative refinement produces bipartitionings with lower communication volume compared to current state-of-the-art methods, and is faster at producing them.