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 (n²) to O (n). Numerical experiments also indicatethat the preconditioned systems exhibit favorable clustering of eigen-values Both the computation based on averaging of the coecients of the elliptic operator and the inversion using FFTs of the circulant
preconditioners are highly parallelizable.