Multigrid is one of the few optimal methods for solving systems of equations arising from the discretization of partial differential equations as well as a wide variety of related problems on graphs. In this tutorial we will introduce the key ingredients of the multigrid method (smoothing and coarse grid correction), explain their complementarity (they don't work well alone), and describe the most common cycling strategies. We will present the concepts and motivating analysis using a simple geometric approach to solving the linear system arising from the discretization of the diffusion equation on structured orthogonal grids. Then we will highlight the elements of the algorithm that have been advanced to provide robustness and flexibility for more general problems (e.g., operator dependent interpolation, galerkin coarse grid operators, and algebraic methods), noting that these topics will be covered in more detail in the subsequent tutorials. Finally, we'll touch on the popular and powerful use of multigrid as a preconditioner for Krylov methods such as the conjugate gradient method.

The focus of this tutorial is on algebraic multigrid (AMG). The tutorial will start with the basic principles of algebraic multigrid methods, followed by introducing two general methods: CF based algebraic multigrid and aggregation based algebraic multigrid. An overview of these methods, including common algorithms for their construction will be covered. The goal is to identify the key components of AMG. Advanced algebraic methods such as compatible relaxation, adaptive AMG, and element based AMG will also be briefly covered. In addition, an overview of some of the supporting theory will be given.

This tutorial will start with an introduction to parallel computing and cover the classical computer taxonomy, programming models, parallel performance metrics, and parallelizing PDE-based problems. The talk will then move on to parallel multigrid, including parallel algebraic multigrid and parallel multigrid software design. Finally, some current research topics will be touched on as well.

Developing effective multigrid methods for systems of PDEs generally requires somewhat different multigrid components than are typically used for scalar elliptic PDEs.  In this tutorial, we discuss common uses of multigrid for solving such systems and the components of effective multigrid methods for them.  We will discuss block factorization schemes, that apply multigrid methods to component blocks of the system, and monolithic multigrid methods, that apply specialized relaxation schemes to the coupled systems directly.