IBM T. J. Watson Research Center

Yorktown Heights, NY, USA and

Computer Science Department

Yale University

New Haven, CT, USA

Department of Mathematics

Purdue University

Mathematical Sciences Building

West Lafayette, IN 47907, USA

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.