In the last years theory for multigrid methods for Toeplitz matrices and circulant matrices has been developed, see e.g. [2,5,6]. This theory is based on the convergence results for classical AMG that can be found e.g. in [1]. The convergence analysis is based on knowledge about the zeros of the system matrices' generating symbols and appropriate construction of the interpolation operators.
For many applications, especially for unstructured grids and in parallel, algebraic multigrid methods based on aggregation [3] or smoothed aggregation [4] are used, rather than classical AMG methods. While the first make use of the fact that the constant is a near kernel component for elliptic PDEs, the latter automatically improve the interpolation operator by applying the smoother to the constant vector.
We took the ideas of aggregation and smoothed aggregation and transfered them to the cases of circulant matrices and Toeplitz matrices. Under certain assumptions the generated interpolation operators fulfill the requirements of the available convergence theory, while still generating the interpolation automatically.
In the talk we will present our results and give examples for different choices of (smoothed) interpolation operators.