Optimal interpolation and Compatible Relaxation in Classical Algebraic Multigrid
For practitioners of algebraic multigrid, this work provides a more efficient and theoretically grounded interpolation method that improves convergence for challenging diffusion problems.
The paper derives a new sharp measure for coarse grid quality using optimal interpolation and shows that a generalized bootstrap AMG with sparse interpolation outperforms the standard ideal interpolation for scalar diffusion problems with highly varying coefficients.
In this paper, we consider a classical form of optimal algebraic multigrid (AMG) interpolation that directly minimizes the two-grid convergence rate and compare it with the so-called ideal form that minimizes a certain weak approximation property of the coarse space. We study compatible relaxation type estimates for the quality of the coarse grid and derive a new sharp measure using optimal interpolation that provides a guaranteed lower bound on the convergence rate of the resulting two-grid method for a given grid. In addition, we design a generalized bootstrap algebraic multigrid setup algorithm that computes a sparse approximation to the optimal interpolation matrix. We demonstrate numerically that the BAMG method with sparse interpolation matrix (and spanning multiple levels) outperforms the two-grid method with the standard ideal interpolation (a dense matrix) for various scalar diffusion problems with highly varying diffusion coefficient.