Implementing abstract multigrid or multilevel methods

Craig C. Douglas

Department of Computer Science, Yale University,
P. O. Box 2158 Yale Station, New Haven, CT 06520-2158, USA


Multigrid can be formulated as an algorithm for an abstract problem that is independent of the partial differential equation, domain, and discretization method. In such an abstract setting, problems not arising from partial differential equations can be treated also (c.f. aggregation-disaggregation methods). Quite general theory exists for linear problems, e.g., Douglas$^2$, SINUM, 30 (1993), pp. 136--158.

The general theory in Douglas$^2$ was motivated by a series of abstract solvers (Madpack). The latest version (4) was motivated instead by the theory. Madpack now allows for a wide variety of iterative and direct solvers, preconditioners, and interpolation and projection schemes, including user callback ones. It allows for sparse, dense, and stencil matrices. Mildly nonlinear problems can be handled. Also, there is a fast, multigrid Poisson solver (two and three dimensions).

The type of solvers and design decisions (including language, data structures, external library support, and callbacks) are discussed here. Based on the author's experiences with two versions of Madpack, a better approach is proposed here. This is based on a mixed language formulation (C and Fortran+preprocessor). Reasons for not just using Fortran, C, or C++ are given. Implementing the proposed strategy is not difficult.