On the construction of AMG prolongation through energy minimization

Algebraic Multigrid (AMG) is a very popular iterative method used in several applications. This wide diffusion is due to its effectiveness in solving linear systems arising from PDEs discretization. The key feature of AMG is its optimality, i.e., the ability to guarantee a convergence rate independent of the mesh size for different problems. This is obtained through a good interplay between the smoother and the interpolation. Unfortunately, for difficult problems, such as those arising from structural mechanics or diffusion problems with large jumps in the coefficients, standard smoothers and interpolation techniques are not enough to ensure fast convergence. In these cases, an improved prolongation operator is required to enhance the AMG effectiveness. In this work, we present an updated prolongation according to an energy minimization criterion and show how this minimization can be seen as a constrained minimization problem. In detail, we have that the constraint is twofold: the prolongation must be sparse, and its range must represent the operator near-kernel. Even though energy minimization is well-known in the AMG community, it has little application due to both its cost and difficult implementation. Here, we would like to make energy minimization feasible through suitable preconditioned and effective implementation. In particular, to solve this problem, we propose two strategies: a restricted Krylov subspace iterative procedure and the null-space method. Both approaches can be preconditioned to speed up the setup time. Finally, thanks to some numerical experiments, we demonstrate how the convergence rate can be significantly increased at a reasonable setup cost.