Algebraic multigrid methods are efficient solvers for linear systems involving d-level circulant matrices. As long as the generating function is a d-variate trigonometric polynomial of fixed degree, they are optimal, i.e. O(N), and better suited than FFT-methods, which scale like O(N log N) and which are the common choice for such systems.

Traditionally, algebraic multigrid uses the Galerkin operator on the coarse grid. The use of the Galerkin operator is well-analyzed and works very good, but it has the disadvantage of growing stencils. To circumvent this problem, there exist approaches, which do not use the Galerkin operator on the coarse grid, but a collapsed stencil instead(e.g. Ashby's and Falgout's solver for structured grids [1]).

In this talk, stencil-collapsing is analyzed for the special case of d-level circulant matrices, as they arise in discretizing PDEs with constant coefficients and periodic boundary conditions. Structured grid AMG for d-level circulant matrices has been studied in detail in [2]. Instead of using the full Galerkin coarse grid operator, a spectrally equivalent operator using a collapsed stencil is used. Due to the collapsed stencil, the computational complexity of a cycle is reduced. Furthermore, if the stencil collapsing scheme is chosen properly, the use of two-color relaxation schemes is possible on the coarse grid, as well.

References
[1] S. F. Ashby and R. D. Falgout, A parallel multigrid preconditioned conjugate gradient algorithm for groundwater flow simulations, Nucl. Sci. Eng., 124 (1996), pp. 145-159.
[2] S. Serra-Capizzano and C. Tablino-Possio, Multigrid methods for multilevel circulant matrices, SIAM Journal on Scientific Computing, 26 (2004), pp. 55-85.