Preliminary remarks on multigrid methods for circulant matrices

In this note we propose a multigrid approach to the solution of (multilevel) banded circulant linear system. In particular, we discuss how to define a "coarse-grid projector" such that the projected matrix at lower dimension preserves the circulant structure. This approach naturally leads to an optimal algorithm having Linear cost as the size N of the system and so improving the the classical one based on Fast Fourier Transforms (FFTs) that costs O(N log N) arithmetic operations (ops). It's worth mentioning that these banded circulants are used as preconditioners for elliptic and parabolic PDEs (with Dirichlet or periodic boundary conditions) and for some 2D image restoration problems where the point spread function (PSF) is numerically banded. Therefore the use of the proposed multigrid technique reduces the overall cost from O(k(epsilon,n)NlogN) to O(k(epsilon,n)N), where k(epsilon,n) is the number of Preconditioned Conjugate Gradient (PCG) iterations to reach the solution within a given accuracy of c. The full analysis of convergence and the related numerical experiments are reported in a forthcoming paper [18].