A Parallel Algorithm for Multilevel Graph Partitioning and Sparse Matrix Ordering

Research output: Contribution to journalArticlepeer-review

264 Scopus citations

Abstract

In this paper we present a parallel formulation of the multilevel graph partitioning and sparse matrix ordering algorithm. A key feature of our parallel formulation (that distinguishes it from other proposed parallel formulations of multilevel algorithms) is that it partitions the vertices of the graph intopparts while distributing the overall adjacency matrix of the graph among allpprocessors. This mapping results in substantially smaller communication than one-dimensional distribution for graphs with relatively high degree, especially if the graph is randomly distributed among the processors. We also present a parallel algorithm for computing a minimal cover of a bipartite graph which is a key operation for obtaining a small vertex separator that is useful for computing the fill reducing ordering of sparse matrices. Our parallel algorithm achieves a speedup of up to 56 on 128 processors for moderate size problems, further reducing the already moderate serial run time of multilevel schemes. Furthermore, the quality of the produced partitions and orderings are comparable to those produced by the serial multilevel algorithm that has been shown to outperform both spectral partitioning and multiple minimum degree.

Original languageEnglish (US)
Pages (from-to)71-95
Number of pages25
JournalJournal of Parallel and Distributed Computing
Volume48
Issue number1
DOIs
StatePublished - Jan 10 1998

Bibliographical note

Funding Information:
1This work was supported by NSF CCR-9423082, by the Army Research Office Contract DA/DAAH04-95-1-0538, by the IBM Partnership Award, and by Army High Performance Computing Research Center under the auspices of the Department of the Army, Army Research Laboratory Cooperative Agreement Number DAAH04-95-2-0003/Contract DAAH04-95-C-0008, the content of which does not necessarily reflect the position or the policy of the government, and no official endorsement should be inferred. Access to computing facilities was provided by AHPCRC. Minnesota Supercomputer Institute, Cray Research Inc., and by the Pittsburgh Supercomputing Center. Related papers are available via WWW at URL: http://www.cs.umn.edu/∼karypis. 2E-mail: karypis@cs.umn.edu. 3E-mail: kumar@cs.umn.edu.

Keywords

  • Parallel graph partitioning; multilevel partitioning methods; fill reducing ordering; numerical linear algebra.

Fingerprint Dive into the research topics of 'A Parallel Algorithm for Multilevel Graph Partitioning and Sparse Matrix Ordering'. Together they form a unique fingerprint.

Cite this