# Algebraic Multigrid¶

Here we outline the basic principles behind the Algebraic Multigrid (AMG) method [BrMH85], [Stue99]. Consider a system of linear algebraic equations in the form

$Au = f$

where $$A$$ is an $$n \times n$$ matrix. Multigrid methods are based on the recursive use of two-grid scheme, which combines

• Relaxation, or smoothing iteration: a simple iterative method such as Jacobi or Gauss-Seidel; and
• Coarse grid correction: solving residual equation on a coarser grid. Transfer between grids is described with transfer operators $$P$$ (prolongation or interpolation) and $$R$$ (restriction).

A setup phase of a generic algebraic multigrid (AMG) algorithm may be described as follows:

• Start with a system matrix $$A_1 = A$$.
• While the matrix $$A_i$$ is too big to be solved directly:
1. Introduce prolongation operator $$P_i$$, and restriction operator $$R_i$$.
2. Construct coarse system using Galerkin operator: $$A_{i+1} = R_i A_i P_i$$.
• Construct a direct solver for the coarsest system $$A_L$$.

Note that in order to construct the next level in the AMG hierarchy, we only need to define transfer operators $$P$$ and $$R$$. Also, the restriction operator is often chosen to be a transpose of the prolongation operator: $$R=P^T$$.

Having constructed the AMG hierarchy, we can use it to solve the system as follows:

• Start at the finest level with initial approximation $$u_1 = u^0$$.
• Iterate until convergence (V-cycle):
• At each level of the grid hiearchy, finest-to-coarsest:
1. Apply a couple of smoothing iterations (pre-relaxation) to the current solution $$u_i = S_i(A_i, f_i, u_i)$$.
2. Find residual $$e_i = f_i - A_i u_i$$ and restrict it to the RHS on the coarser level: $$f_{i+1} = R_i e_i$$.
• Solve the corasest system directly: $$u_L = A_L^{-1} f_L$$.
• At each level of the grid hiearchy, coarsest-to-finest:
1. Update the current solution with the interpolated solution from the coarser level: $$u_i = u_i + P_i u_{i+1}$$.
2. Apply a couple of smoothing iterations (post-relaxation) to the updated solution: $$u_i = S_i(A_i, f_i, u_i)$$.

More often AMG is not used standalone, but as a preconditioner with an iterative Krylov subspace method. In this case single V-cycle is used as a preconditioning step.

So, in order to fully define an AMG method, we need to choose transfer operators $$P$$ and $$R$$, and smoother $$S$$.