We discuss a multigrid technique for the solution of multilevel circulant linear systems whose coefficient matrix has eigenvalues of the form f(2pj/n) where f is polynomial and indipendent of n = (n1,¼,nd) with 2pj/n = (2pj1/n1,¼,2pjd/nd), 0 £ ji £ ni-1. The interest of the algorithm is in the multilevel (banded) context since the total cost is optimal i.e. O(N) arithmetic operations (ops), N = n1¼nd, instead of O(NlogN) ops arising from the use of FFTs. We recall 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 so that the overall cost is reduced from O(k(e,n) NlogN) to O(k(e,n)N) where k(e,n) is the number of PCG iterations to reach the solution within an accuracy of e. Finally, we discuss how these techniques can be translated in different settings including t, DCT-III and Hartley algebras and to the more difficult context of multilevel Toeplitz structures generated by polynomial symbols (so overcoming the ``negative'' PCG result by Serra Capizzano and Tyrtyshnikov).
1 Joint work with Stefano SERRA CAPIZZANO.