Volume 44, pp. 25-52, 2015.

Analysis of smoothed aggregation multigrid methods based on Toeplitz matrices

Matthias Bolten, Marco Donatelli, and Thomas Huckle


The aim of this paper is to analyze multigrid methods based on smoothed aggregation in the case of circulant and Toeplitz matrices. The analysis is based on the classical convergence theory for these types of matrices and yields optimal choices of the smoothing parameters for the grid transfer operators in order to guarantee optimality of the resulting multigrid method. The developed analysis allows a new understanding of smoothed aggregation and can also be applied to unstructured matrices. A detailed analysis of the multigrid convergence behavior is developed for the finite difference discretization of the 2D Laplacian with nine point stencils. The theoretical findings are backed up by numerical experiments.

Full Text (PDF) [473 KB]

Key words

multigrid methods, Toeplitz matrices, circulant matrices, smoothed aggregation-based multigrid

AMS subject classifications

15B05, 65F10, 65N22, 65N55

Links to the cited ETNA articles

[14]Vol. 13 (2002), pp. 81-105 Thomas Huckle and Jochen Staudacher: Multigrid preconditioning and Toeplitz matrices

< Back