Multilevel diffusion schemes for repartitioning of adaptive meshes

Kirk Schloegel, George Karypis, Vipin Kumar

Research output: Contribution to journalArticlepeer-review

102 Scopus citations


For a large class of irregular mesh applications, the structure of the mesh changes from one phase of the computation to the next. Eventually, as the mesh evolves, the adapted mesh has to be repartitioned to ensure good load balance. If this new graph is partitioned from scratch, it may lead to an excessive migration of data among processors. In this paper, we present schemes for computing repartitionings of adaptively refined meshes that perform diffusion of vertices in a multilevel framework. These schemes try to minimize vertex movement without significantly compromising the edge-cut. We present heuristics to control the tradeoff between edge-cut and vertex migration costs. We also show that multilevel diffusion produces results with improved edge-cuts over single-level diffusion, and is better able to make use of heuristics to control the tradeoff between edge-cut and vertex migration costs than single-level diffusion.

Original languageEnglish (US)
Pages (from-to)109-124
Number of pages16
JournalJournal of Parallel and Distributed Computing
Issue number2
StatePublished - Dec 15 1997

Bibliographical note

Funding Information:
1This work was supported by NSF CCR-9423082, by Army Research Office Contracts DA/DAAH04-95-1-0538 and DA/DAAH04-95-1-0244, by Army High Performance Computing Research Center Cooperative Agreement DAAH04-95-2-0003/Contract 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. Additional support was provided by the IBM Partnership Award and by the IBM SUR equipment grant. Access to computing facilities was provided by AHPCRC, Minnesota Supercomputer Institute. Related papers are available via WWW at URL:∼karypis. 2E-mail:,,


Dive into the research topics of 'Multilevel diffusion schemes for repartitioning of adaptive meshes'. Together they form a unique fingerprint.

Cite this