Optimal interpolation and compatible relaxation in classical algebraic multigrid

James Brannick, Fei Cao, Karsten Kahl, Robert D. Falgout, Xiaozhe Hu

Research output: Contribution to journalArticlepeer-review

18 Scopus citations


In this paper, we consider a classical algebraic multigrid (AMG) form of optimal interpolation that directly minimizes the two-grid convergence rate and compare it with a so-called ideal interpolation that minimizes a 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 AMG setup algorithm that computes a sparse approximation to the optimal interpolation matrix. We demonstrate numerically that the bootstrap AMG method with sparse interpolation matrix (and spanning multiple levels) converges faster than the two-grid method with the standard ideal interpolation (a dense matrix) for various scalar diffusion problems with highly varying diffusion coefficient.

Original languageEnglish (US)
Pages (from-to)A1473-A1493
JournalSIAM Journal on Scientific Computing
Issue number3
StatePublished - 2018

All Science Journal Classification (ASJC) codes

  • Computational Mathematics
  • Applied Mathematics


Dive into the research topics of 'Optimal interpolation and compatible relaxation in classical algebraic multigrid'. Together they form a unique fingerprint.

Cite this