Circulant preconditioners for convolution-like integral equations with higher-order quadrature rules

Abstract

In this paper, we consider solving matrix systems arising from the discretization of convolution-like integral equations by preconditioned conjugate gradient (PCG) methods. Circulant integral operators as preconditioners have been proposed and studied. However, the discretization of these circulant preconditioned equations by employing higher-order quadratures leads to matrix systems that cannot be solved efficiently by using fast Fourier transforms (FFTs). The aim of this paper is to propose "inverted" circulant preconditioners for convolution-like integral equations. The discretization of these preconditioned integral equations by higher-order quadratures leads to matrix systems that involve only Toeplitz, circulant and diagonal matrix-vector multiplications, and hence can be computed efficiently by FFTs in each iteration. Numerical examples are given to illustrate the fast convergence of the method and the improvement of the accuracy of the computed solutions with using higher-order quadratures. We also apply our method to solve the convolution-like equation arising from the linear least squares estimation in signal processing.