Algebraic Multigrid Research at Lawrence Livermore National Laboratory:

where we are, how we got there, and where we’re going

Van Emden Henson

Center for Applied Scientific Computing

Lawrence Livermore National Laboratory

PO Box 808 L-560

Livermore CA 94551

Abstract

We attempt to weave a coherent picture of where research in algebraic multigrid (AMG) stands today, and put into context where it came from and where it is going. In particular, we focus on the research being conducted at Lawrence Livermore National Laboratory in conjunction with collaborators at the University of Colorado. As a unifying theme, we observe that in geometric multigrid the purpose of the coarse grid is to correct out the smooth error that remains after relaxation. Many AMG algorithms thus contain, implicitly or explicitly, some underlying assumption about what constitutes “smooth error.” Indeed, it is possible to classify AMG algorithms based largely on the nature of the assumptions they make about the algebraic nature of smoothness. For example, some AMG algorithms assume that smooth error is characterized by residuals much smaller than the error. Others may view smooth error as being characterized by small energy norm, while still others may assume that the smooth error is spanned by the eigenvectors of the operator associated with the smallest eigenvectors. There are other assumptions made in other AMG algorithms, as well, such as smoothness as illuminated by compatible relaxation. In many settings, these assumptions are equivalent, but the fact that one or another is viewed as primary can sometimes be considered to guide the algorithmic development.

We attempt here to unify these ideas, pointing out the assumptions in some of the major branches of AMG research, such as the “classical” AMG of Ruge and Stüben, the element-based AMGe family of algorithms, smoothed aggregation, and Achi Brandt's Bootstrap AMG family. We examine the characterizations of smoothness that underlie these branches, and point out how they differ from one another in philosophy, design, and development. We observe that the choice of characterization is often driven by features of the problem to be solved.

Finally, we note that a goal of much AMG research is to produce an extremely robust algorithm that has no hidden underlying assumptions about smooth error, and we describe some of the current research directions that are aimed at achieving this goal.

This work was performed under the auspices of the U.S. Department of Energy by University of California Lawrence Livermore National Laboratory under contract No. W-7405-Eng-48. UCRL-JC-146606 Abs