Parallel multilevel graph partitioning

Authors:
  • GKG. Karypis
    G. Karypis
  • VKV. Kumar
    V. Kumar
Publisher website
Google Scholar
Abstract
In this paper we present a parallel formulation of a graph par - titioning and sparse matrix ordering algorithm that is based on a multilevel algorithm we developed recently Our parallel algo - rithm 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 parti - tioned 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 - 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 mul - tilevel algorithm that has been shown to substantially outperform both spectral partitioning and multiple minimum degree

This publication has 6 references indexed in Scilit: