  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.
