A medium-grain method for fast 2D bipartitioning of sparse matrices

Daniël M. Pelt, Rob H. Bisseling

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

Abstract

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 x 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.

Original languageEnglish
Title of host publicationProceedings IEEE 28th International Parallel & Distributed Processing Symposium (IPDPS 2014)
Subtitle of host publication19–23 May 2014 Phoenix, Arizona
PublisherIEEE
Pages529-539
Number of pages11
ISBN (Print)9780769552071
DOIs
Publication statusPublished - 14 Aug 2014
Event28th IEEE International Parallel and Distributed Processing Symposium, IPDPS 2014 - Phoenix, AZ, United Kingdom
Duration: 19 May 201423 May 2014

Publication series

NameProceedings of the ... International Parallel and Distributed Processing Symposium
Volume28
ISSN (Print)1530-2075

Conference

Conference28th IEEE International Parallel and Distributed Processing Symposium, IPDPS 2014
Country/TerritoryUnited Kingdom
CityPhoenix, AZ
Period19/05/1423/05/14

Keywords

  • hypergraph
  • parallel computing
  • sparse matrix-vector multiplication

Fingerprint

Dive into the research topics of 'A medium-grain method for fast 2D bipartitioning of sparse matrices'. Together they form a unique fingerprint.

Cite this