AbstractA 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 CT AC can be reduced significantly. We illustrate how to construct the spectrum of C in a way that allows the smallest eigenvalues of CT AC to overlap with those of A extremely well while making the largest eigenvalues of CT 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.