Multilevel Diffusion Schemes for Repartitioning of Adaptive Meshes

Kirk Schloegel, George Karypis, and Vipin Kumar
Journal of Parallel and Distributed Computing, Vol. 47, pp. 109 - 124, 1997
Download Paper
For a large class of irregular grid applications, the structure of the mesh changes from one phase
of the computation to the next. Eventually, as the graph evolves, the adapted mesh has to be repartitioned to ensure good load balance. If this new graph is partitioned from scratch, it will lead to an
excessive migration of data among processors. In this paper, we present two new schemes for computing
repartitionings of adaptively refined meshes. These schemes perform diffusion of vertices in a multilevel
framework and 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, is potentially much
faster than single-level diffusion in a parallel context, and is better able to make use of heuristics to
control the trade-off between edge-cut and vertex migration costs than single-level diffusion.
Research topics: Graph partitioning | Parallel processing | ParMETIS