Theoretical bounds for algebraic multigrid performance: Review and analysis

Scott P. Maclachlan, Luke N. Olson

Research output: Contribution to journalArticlepeer-review


Algebraic multigrid methods continue to grow in robustness as effective solvers for the large and sparse linear systems of equations that arise in many applications. Unlike geometric multigrid approaches, however, the theoretical analysis of algebraic multigrid is less predictive of true performance. Multigrid convergence factors naturally depend on the properties of the relaxation, interpolation, and coarse-grid correction routines used, yet without the tools of Fourier analysis, optimal and practical bounds for algebraic multigrid are not easily quantified. In this paper, we survey bounds from existing literature, with particular focus on the predictive capabilities of the theory, and provide new results relating existing bounds. We highlight the impact of these theoretical observations through several model problems and discuss the role of theoretical bounds on practical performance.

Original languageEnglish (US)
Pages (from-to)194-220
Number of pages27
JournalNumerical Linear Algebra with Applications
Issue number2
StatePublished - Mar 2014


  • Algebraic multigrid
  • Convergence bounds
  • Predictive theory

ASJC Scopus subject areas

  • Algebra and Number Theory
  • Applied Mathematics


Dive into the research topics of 'Theoretical bounds for algebraic multigrid performance: Review and analysis'. Together they form a unique fingerprint.

Cite this