Analysis of an algebraic Petrov-Galerkin smoothed aggregation multigrid method

We give a convergence estimate for a Petrov-Galerkin Algebraic Multigrid method. In this method, the prolongations are defined using the concept of smoothed aggregation while the restrictions are simple aggregation operators. The analysis is carried out by showing that these methods can be interpreted as variational Ritz-Galerkin ones using modified transfer and smoothing operators. The estimate depends only on a weak approximation property for the aggregation operators. For a scalar second order elliptic problem using linear elements, this assumption is shown to hold using simple geometrical arguments on the aggregates. (C) 2007 IMACS. Published by Elsevier B.V. All rights reserved.