A Unified Multigrid Theory for Non-Nested Grids and/or Quadrature

                          Craig C. Douglas (SPEAKER)

                            IBM Research Division,
                      Thomas J. Watson Research Center,
                                P. O. Box 218,
                       Yorktown Heights, NY 10598-0218,
                                     and
                       Department of Computer Science,
                               Yale University,
                              P. O. Box 208285,
                        New Haven, CT 06520-8285, USA
                          douglas-craig@cs.yale.edu

                                     and

                               Jim Douglas, Jr.

                              Purdue University,
                       Mathematical Sciences Building,
                        West Lafayette, IN 47907, USA
                           douglas@math.purdue.edu

                                     and

                                David E. Fyfe

                               Fluid Dynamics,
                          Naval Research Laboratory,
                          Washington, DC 20375, USA
                           fyfe@fozzie.nrl.navy.mil

                                   Abstract

In this paper, we extend some results from an earlier paper (SIAM J. Numer.
Anal., 30 (1993), pp. 136-158) of the first two authors.  We provide a
unified theory for multilevel and multigrid methods when the usual assumptions
are not present.  For example, we do not assume that the solution spaces or
the grids are nested.  Further, we do not assume that there is an algebraic
relationship between the linear algebra problems on different levels.

What we provide is a computationally useful theory for adaptively changing
levels.  Theory is provided for multilevel correction schemes, nested
iteration schemes, and one way (i.e., coarse to fine grid with no correction
iterations) schemes.  We include examples showing the applicability of this
theory:  finite element examples using quadrature in the matrix assembly and
finite volume examples with non-nested grids.  Our theory applies directly to
finite difference, wavelet, and collocation based multilevel examples as well.