MULTIPLE COARSE GRID MULTIGRID METHODS FOR SOLVING ELLIPTIC PROBLEMS

                                Shengyou Xiao
                            Western Atlas Software
                                Houston, Texas

                                 David Young
                      The University of Texas at Austin
                                Austin, Texas

                                   Abstract

In this paper we describe some classes of multigrid methods for solving large
linear systems arising in the solution by finite difference methods of certain
boundary value problems involving Poisson's equation on rectangular regions.
If parallel computing systems are used, then with standard multigrid methods
many of the processors will be idle when one is working at the coarsest grid
levels.  We describe the use of multiple coarse grid multigrid (MCGMG)
methods.  Here one first constructs a periodic set of equations corresponding
to the given system.  One then constructs a set of coarse grids such that for
each grid corresponding to the grid size h there are four grids corresponding
to the grid size 2*h.  Multigrid operations such as restriction of residuals
and interpolation of corrections are done in parallel at each grid level.  For
suitable choices of the multigrid operators the MCGMG method is equivalent to
the parallel superconvergent multigrid (PSMG) method of Frederickson and
McBryan.  The convergence properties of MCGMG methods can be accurately
analyzed using spectral methods.