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

Craig C. Douglas
IBM T. J. Watson Research Center
Yorktown Heights, NY, USA and
Computer Science Department
Yale University
New Haven, CT, USA

Jim Douglas, Jr.
Department of Mathematics
Purdue University
Mathematical Sciences Building
West Lafayette, IN 47907, USA

David E. Fyfe
Naval Research Laboratory
Laboratory for Computational Physics and Fluid Dynamics
Code 6410
Washington, D.C. 20375, USA


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.

Contributed October 24, 1994.