Numerical simulation of physical processes is often constrained by our ability to solve the complex linear systems at the core of the computation. Classical geometric and algebraic multigrid methods rely on (implicit) assumptions about the character of these matrices in order to develop appropriately complementary coarse-grid correction processes for a given relaxation scheme. The aim of the adaptive multigrid framework is to reduce the restrictions imposed by such assumptions, thus allowing for efficient black-box multigrid solution of a wider class of problems.

There are, however, many challenges in altogether removing the reliance on assumptions about the errors left after relaxation. In this talk, we discuss work to date on a fully adaptive AMG algorithm that chooses all components of the coarse-grid correction based on automated analysis of the performance of relaxation. Fundamental measures of the need for and quality of a coarse-grid correction will be discussed, along with related techniques for choosing coarse grids and interpolation operators. We will also discuss the (lack of) computability of these ideal measures, and suggest cost-efficient alternatives.

This research has been performed in collaboration with James Brannick, Marian Brezina, Tom Manteuffel, Steve McCormick, and John Ruge at CU-Boulder. It has been supported by an NSF SciDAC grant (TOPS), as well as Lawrence Livermore and Los Alamos National Laboratories.