Partitioning and Mapping Adaptive Multigrid Hierarchies on 
Distributed Memory Computers

Johan De Keyser and Dirk Roose
johandk@cs.kuleuven.ac.be

Feb 1992

Report TW166
Department of Computer Science
Katholieke Universiteit Leuven 
Celestijnenlaan 200A
3001 Heverlee
Belgium

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

Abstract :

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.