Multigrid With Overlapping Patches

                      M. Berndt, University of Colorado
                    K. Witsch, University of Duesseldorf 

                                  Abstract:

Solving boundary value problems with optimal efficiency requires adaptive
grids and multilevel techniques.  Both are combined by adding appropriate
refinement grids as fine levels in the multigrid process.  Often this is done
using block structured refinement regions.  We investigate the use of
overlapping patches.  In this case less patches are necessary compared to non
overlapping refinement patches.  With overlapping patches a Schwarz type
procedure is necessary in the solution phase.  We use Schwarz iteration as an
approximative solver or in the relaxation step of multigrid, both additively
and multiplicatively, latter with coloring to allow efficient parallelization.

These methods, FAC, AFAC and MLAT and different geometric situations are
compared.  In some cases this approach yields relatively bad convergence
rates.  We try to improve them.

The implementation in C++ is based on the A++/P++ package of Dan Quinlan and
Max Lemke.  Due to that we could use high level constructs and it was possible
to proceed from the serial version to a parallel one within a few days.