Lawrence Berkeley National Laboratory

A framework for constructing circulant and block circulant preconditioners ($C$) for a symmetric linear system $Ax=b$ arising from certain 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 its eigenvalues so that the condition number of $C^TAC$ can be reduced significantly. We illustrate how to construct the spectrum of $C$ in a way such that the smallest eigenvalues of $C^TAC$ overlaps with those of $A$ extremely well while the largest eigenvalues of $C^TAC$ are smaller than those of $A$ by several orders of magnitude. Numerical examples are provided to demonstrate the effectiveness of the preconditioner on accelerating the solution of linear systems arising from image reconstruction application.