New Estimates for Multilevel
Algorithms Including the V-Cycle

J. H. Bramble
Department of Mathematics
Cornell University
Ithaca, NY 14853

J. E. Pasciak
Applied Math Department
Brookhaven National Laboratory
Upton, NY 11973


The purpose of this paper is to provide new estimates for certain multilevel algorithms. In particular, we are concerned with the simple additive multilevel algorithm given in BPX and the standard V-cycle algorithm with one smoothing step per grid. We shall prove that these algorithms have a uniform reduction per iteration independent of the mesh sizes and number of levels even on non-convex domains which do not provide full elliptic regularity. For example, the theory applies to the standard multigrid V-cycle on the L-shaped domain or a domain with a crack and yields a uniform convergence rate. We also prove uniform convergence rates for the multigrid V-cycle for problems with nonuniformly refined meshes. Finally, we give a new multigrid approach for problems on domains with curved boundaries and prove a uniform rate of convergence for the corresponding multigrid V-cycle algorithms.

Contributed November 6, 1995.