Skip to content

A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs

George Karypis, Vipin Kumar

SIAM Journal on Scientific Computing · 1998 · 5,991 citations

No retraction on record in OpenAlex.Check Crossref now

Cite this paper

Karypis, G., & Kumar, V. (1998). A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM Journal on Scientific Computing, 20(1), 359–392. https://doi.org/10.1137/s1064827595287997

In text: (Karypis & Kumar, 1998)

Ask a question about this research

One question, free, no account. Anchorcite finds the papers, checks each against Crossref and links every sentence of the answer to the passage it comes from.

Abstract

Recently, a number of researchers have investigated a class of graph partitioning algorithms that reduce the size of the graph by collapsing vertices and edges, partition the smaller graph, and then uncoarsen it to construct a partition for the original graph [Bui and Jones, Proc. of the 6th SIAM Conference on Parallel Processing for Scientific Computing, 1993, 445--452; Hendrickson and Leland, A Multilevel Algorithm for Partitioning Graphs, Tech. report SAND 93-1301, Sandia National Laboratories, Albuquerque, NM, 1993]. From the early work it was clear that multilevel techniques held great promise; however, it was not knownif they can be made to consistently produce high quality partitions for graphs arising in a wide range of application domains. We investigate the effectiveness of many different choices for all three phases: coarsening, partition of the coarsest graph, and refinement. In particular, we present a new coarsening heuristic (called heavy-edge heuristic) for which the size of the partition of the coarse graph is within a small factor of the size of the final partition obtained after multilevel refinement. We also present a much faster variation of the Kernighan--Lin (KL) algorithm for refining during uncoarsening. We test our scheme on a large number of graphs arising in various domains including finite element methods, linear programming, VLSI, and transportation. Our experiments show that our scheme produces partitions that are consistently better than those produced by spectral partitioning schemes in substantially smaller time. Also, when our scheme is used to compute fill-reducing orderings for sparse matrices, it produces orderings that have substantially smaller fill than the widely used multiple minimum degree algorithm.

  1. LINCS: A linear constraint solver for molecular simulations1997
  2. GMRES: A Generalized Minimal Residual Algorithm for Solving Nonsymmetric Linear Systems1986
  3. Methods of conjugate gradients for solving linear systems1952
  4. A Singular Value Thresholding Algorithm for Matrix Completion2010
  5. Introduction to Numerical Analysis.1981

Metadata from OpenAlex (CC0). Citations are generated from the published record.