A Parallel Algorithm for Multilevel Graph Partitioning and Sparse Matrix Ordering

George Karypis and Vipin Kumar
Journal of Parallel and Distributed Computing, Vol. 48, pp. 71 - 85, 1998
Download Paper
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 into pp parts
while distributing the overall adjacency matrix of the graph among all p processors.
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.
This is an expanded version of the IPPS 1996 paper with similar title.
Research topics: Graph partitioning | Parallel processing | ParMETIS