language: en

[A short version of this paper appears in]

[Supercomputing 1996]

[The serial algorithms described in this paper are implemented by the `METIS: Unstructured Graph Partitioning and Sparse Matrix Ordering System'. METIS is available on WWW at URL:]

Parallel Multilevel k -way Partitioning Scheme for Irregular Graphs

George Karypis and Vipin Kumar
University of Minnesota, Department of Computer Science
Minneapolis, MN 55455,
Technical Report: 96-036 fkarypis, kumarg@cs.umn.edu

[Last updated on October 24, 1996 at 9:02am]

Abstract In this paper we present a parallel formulation of a multilevel k-way graph partitioning algorithm. The multilevel k-way partitioning algorithm reduces the size of the graph by collapsing vertices and edges (coarsening phase), finds a k-way partitioning of the smaller graph, and then it constructs a k-way partitioning for the original graph by projecting and refining the partition to successively finer graphs (uncoarsening phase). A key innovative feature of our parallel formulation is that it utilizes graph coloring to effectively parallelize both the coarsening and the refinement during the uncoarsening phase. Our algorithm is able to achieve a high degree of concurrency, while maintaining the high quality partitions produced by the serial algorithm. We test our scheme on a large number of graphs from finite element methods, and transportation domains. For graphs with a million vertices, our parallel formulation produces high quality 128-way partitions on 128 processors in a little over two seconds, on Cray T3D. Thus our parallel algorithm makes it feasible to perform frequent dynamic graph partition in adaptive computations without compromising quality.

Keywords: Parallel Graph Partitioning, Multilevel Partitioning Methods, Spectral Partitioning Methods, Kernighan-Lin Heuristic, Parallel Sparse Matrix Algorithms.

[This work was supported by NSF CCR-9423082 and by Army Research Office contract DA/DAAH04-95-1-0538, 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 number 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]