A framework for constructing a circulant preconditioner (C) for a symmetric linear system Ax=b arising from signal and image processing applications is presented. 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'AC can be reduced significantly. We illustrate how to construct the spectrum of C in a way that allows the smallest eigenvalues of C'AC to overlap with those of A extremely well while making the largest eigenvalues of C'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.
1 Joint work with Chao YANG and Pawel PENCZEK.