An algebraic multigrid tutorial
Sunday, November 28, 2010 - 11:00am - 12:30pm
Multigrid methods are so-called optimal methods because they can solve a system of N unknowns with O(N) work. This optimality property is crucial for scaling up to huge high-resolution simulations on parallel computers. To achieve this, the multigrid components must be designed with the underlying system in mind, traditionally, the problem geometry. Algebraic multigrid, however, is a method for solving linear systems using multigrid principles, but requiring no explicit geometric information. Instead, AMG determines the essential multigrid ingredients based solely on the matrix entries. Since the method's introduction in the mid-eighties, researchers have developed numerous AMG algorithms with different robustness and efficiency properties that target a variety of problem classes. In this tutorial, we will introduce the AMG method, beginning with a description of the classical algorithm of Achi Brandt, Steve McCormick, John Ruge, and Klaus Stüben, and then move on to more recent advances and theoretical developments.