A two-grid SA-AMG convergence bound that improves when increasing the polynomial degree

Xiaozhe Hu, Panayot S. Vassilevski, Jinchao Xu

Research output: Contribution to journalArticlepeer-review

8 Scopus citations


In this paper, we consider the convergence rate of a smoothed aggregation algebraic multigrid method, which uses a simple polynomial (1 − t)ν or an optimal Chebyshev-like polynomial to construct the smoother and prolongation operator. The result is purely algebraic, whereas a required main weak approximation property of the tentative interpolation operator is verified for a spectral element agglomeration version of the method. More specifically, we prove that, for partial differential equations (PDEs), the two-grid method converges uniformly without any regularity assumptions. Moreover, the convergence rate improves uniformly when the degree of the polynomials used for the smoother and the prolongation increases. Such a result, as is well-known, would imply uniform convergence of the multilevel W-cycle version of the algorithm. Numerical results, for both PDE and non-PDE (graph Laplacian) problems are presented to illustrate the theoretical findings. Published 2016. This article is a U.S. Government work and is in the public domain in the USA.
Original languageEnglish (US)
Pages (from-to)746-771
Number of pages26
JournalNumerical Linear Algebra with Applications
Issue number4
StatePublished - Aug 1 2016
Externally publishedYes


Dive into the research topics of 'A two-grid SA-AMG convergence bound that improves when increasing the polynomial degree'. Together they form a unique fingerprint.

Cite this