Partitioning and Mapping Adaptive Multigrid Hierarchies on
Distributed Memory Computers

Johan De Keyser and Dirk Roose
Department of Computer Science
Katholieke Universiteit Leuven
Celestijnenlaan 200A
3001 Heverlee

Report TW166 (Februrary, 1992)


The full multigrid method uses a hierarchy of successively finer grids. In a solution-adaptive grid hierarchy each grid is obtained by adaptive refinement of the grid on the previous level. On a distributed memory multiprocessor, each grid level must be partitioned and mapped so as to minimize the multigrid cycle execution time. In this report several grid partitioning and load (re)mapping strategies that deal with this problem are compared. The performance of such parallel adaptive multigrid algorithms has been evaluated on an iPSC hypercube for an irregular finite volume discretization of a linear first-order hyperbolic partial differential equation on a two-dimensional domain.

Keywords : multigrid, finite volumes, data parallelism, load balancing, distributed memory computers

Contributed July 29, 1992.