A fast rapidly convergent method for approximation of convolutions with applications to wave scattering and some other problems

Abstract

In this article, we discuss an O(N log N) rapidly convergent algorithm for the numerical approximation of the convolution integral with weakly singular kernels and compactly supported densities with possible jump discontinuities. To achieve the reduced computational complexity, we utilize the Fast Fourier Transform (FFT) on a uniform grid of size N for approximating the convolution. To facilitate this and maintain the accuracy, we primarily rely on a periodic Fourier extension of the density with a suitably large period depending on the support of the density. While the method's convergence rate improves with increasing smoothness of the periodic extension and, in fact, approximations exhibit super-algebraic convergence when the extension is infinitely differentiable, it converges only linearly when the density has jump discontinuities. In this context, we present two different procedures to enhance the convergence speed. Firstly, we utilize a certain Fourier smoothing technique to accelerate the convergence to achieve the quadratic rate in the overall approximation. Finally, to make the method truly high order, we augment the basic scheme by including a "thin" boundary grid and employing a specialized high-order boundary integrator. We validate its performance in terms of accuracy as well as computational efficiency through a variety of numerical experiments. In particular, to demonstrate the method's utility, we apply the integration scheme for the numerical solution of certain partial differential equations. Moreover, we also apply the quadrature to obtain a fast and high-order Nyström solver for the solution of the Lippmann-Schwinger integral equation.

Files

Additional details