Analysis of smoothed aggregation multigrid methods based on toeplitz matrices

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.