Parallel multilevel graph partitioning

Research output: Contribution to journalConference articlepeer-review

49 Scopus citations


In this paper we present a parallel formulation of a graph partitioning and sparse matrix ordering algorithm that is based on a multilevel algorithm we developed recently. Our parallel algorithm achieves a speedup of up to 56 on a 128-processor Cray T3D for moderate size problems, further reducing its already moderate serial run time. Graphs with over 200,000 vertices can be partitioned in 128 parts, on a 128-processor Cray T3D in less than 3 seconds. This is at least an order of magnitude better than any previously reported run times on 128-processors for obtaining an 128-partition. This also makes it possible to use our parallel graph partitioning algorithm to partition meshes dynamically in adaptive computations. Furthermore, the quality of the produced partitions and orderings are comparable to those produced by the serial multilevel algorithm that has been shown to substantially outperform both spectral partitioning and multiple minimum degree.

Original languageEnglish (US)
Pages (from-to)314-319
Number of pages6
JournalIEEE Symposium on Parallel and Distributed Processing - Proceedings
StatePublished - 1996
EventProceedings of the 1996 10th International Parallel Processing Symposium - Honolulu, HI, USA
Duration: Apr 15 1996Apr 19 1996


Dive into the research topics of 'Parallel multilevel graph partitioning'. Together they form a unique fingerprint.

Cite this