Volume 45, pp. 146-159, 2016.

On AMG methods with F-smoothing based on Chebyshev polynomials and their relation to AMGr

Florian Gossler and Reinhard Nabben


MacLachlan, Manteuffel, and McCormick [Numer. Linear Algebra Appl., 13 (2006), pp. 599–620] introduced a new algebraic multigrid method, the so-called reduction-based algebraic multigrid method (AMGr). Different from typical multigrid methods, the smoother of the AMGr method is acting only on the fine-grid points. To analyze the AMGr method, different constants and parameters are used. Here, we further analyze the AMGr method. We show that the parameter used by MacLachlan et al. has another important property. We show that it is closely related to the root of a Chebyshev polynomial. This fact also explains the good performance of AMGr. By examining this relation with Chebyshev polynomials, we extend the concept of the AMGr method. We consider algebraic multigrid methods with fine-grid smoothers and AMG methods that are based on polynomial smoothing. We also establish bounds for the error propagation operator. The bound is minimal if Chebyshev polynomials are chosen. If more than one smoothing step is used, the error bound is smaller than the bound given for the AMGr method. For only one smoothing step, the polynomial-based AMG with Chebyshev polynomials coincides with the AMGr method. In this case, our convergence analysis gives some new explanation of the high performance of the AMGr method as well as the parameters used in the AMGr method.

Full Text (PDF) [295 KB]

Key words

AMG, AMGr, Chebyshev polynomials

AMS subject classifications

65F10, 65F20

Links to the cited ETNA articles

[3]Vol. 40 (2013), pp. 311-320 Michele Benzi and Verena Kuhlemann: Chebyshev acceleration of the GeneRank algorithm
[5]Vol. 37 (2010), pp. 276-295 J. Brannick, A. Frommer, K. Kahl, S. MacLachlan, and L. Zikatanov: Adaptive reduction-based multigrid for nearly singular and highly disordered physical systems
[15]Vol. 30 (2008), pp. 323-345 Christian Mense and Reinhard Nabben: On algebraic multilevel methods for non-symmetric systems - convergence results

< Back