Circulant preconditioners for elliptic problems

We propose and analyze the use of circulant preconditioners for the solution of elliptic problems via preconditioned iterative methods such as the conjugate gradient method. Part of our motivation is to exploit the fast inversion of circulant systems via the Fast Fourier Transform (FFT). We prove that circulant preconditioners can be chosen so that the condition number of the preconditioned system can be reduced from O(n2) to O(n). Numerical experiments also indicate that the preconditioned systems exhibit favorable clustering of eigen values. Both the computation (based on averaging of the coefficients of the elliptic operator) and the inversion using (FFT's) of the circulant preconditioners are highly parallelizable.