Matrix‐free constructions of circulant and block circulant preconditioners

A framework for constructing circulant and block circulant preconditioners ( C ) for a symmetric linear system Ax = b arising from signal and image processing applications is presented in this paper. The proposed scheme does not make explicit use of matrix elements of A . It is ideal for applications in which A only exists in the form of a matrix vector multiplication routine, and in which the process of extracting matrix elements of A is costly. The proposed algorithm takes advantage of the fact that for many linear systems arising from signal or image processing applications, eigenvectors of A can be well represented by a small number of Fourier modes. Therefore, the construction of C can be carried out in the frequency domain by carefully choosing the eigenvalues of C so that the condition number of C T AC can be reduced significantly. We illustrate how to construct the spectrum of C in a way that allows the smallest eigenvalues of C T AC to overlap with those of A extremely well while making the largest eigenvalues of C T AC several orders of magnitude smaller than those of A . Numerical examples are provided to demonstrate the effectiveness of the preconditioner on accelerating the solution of linear systems arising from image reconstruction applications. Copyright © 2004 John Wiley & Sons, Ltd.