Multigrid Methods for Elliptic Problems: A Review

Abstract

Multigrid methods solve a large class of problems very efficiently. They work by approximating a problem on multiple overlapping grids with widely varying mesh sizes and cycling between thew approximations, using relaxation to reduce the error on the scale of each grid. Problems solved by multigrid methods include general elliptic partial differential equations, nonlinear and eigenvalue problems, and systems of equations from fluid dynamics. The efficiency is optimal: the computational work is proportional to the number of unknowns. This paper reviews the basic concepts and techniques of multigrid methods, concentrating on their role as fast solvers for elliptic boundary-value problems. Analysis of simple relaxation schemes for the Poisson problem shows that their slow convergence is due to smooth error components; approximating these components on a coarser grid leads to a simple multigrid Poisson solver. We review the principal elements of multigrid methods for more general problems, including relaxation schemes, grids, grid transfers, and control algorithms, plus techniques for nonlinear problems and boundary conditions. Multigrid applications, current research, and available software are also discussed.