A Fourier extension based numerical integration scheme for fast and high-order approximation of convolutions with weakly singular kernels
This work provides a computationally efficient method for high-order convolution approximations, benefiting applications like integral equation solvers that require fast and accurate quadrature.
The paper presents an O(n log n) numerical integration scheme for high-order approximation of convolutions with weakly singular kernels, achieving fast convergence by using Fourier extensions to eliminate Gibbs oscillations. Numerical experiments demonstrate high-order accuracy.
Computationally efficient numerical methods for high-order approximations of convolution integrals involving weakly singular kernels find many practical applications including those in the development of fast quadrature methods for numerical solution of integral equations. Most fast techniques in this direction utilize uniform grid discretizations of the integral that facilitate the use of FFT for $O(n\log n)$ computations on a grid of size $n$. In general, however, the resulting error converges slowly with increasing $n$ when the integrand does not have a smooth periodic extension. Such extensions, in fact, are often discontinuous and, therefore, their approximations by truncated Fourier series suffer from Gibb's oscillations. In this paper, we present and analyze an $O(n\log n)$ scheme, based on a Fourier extension approach for removing such unwanted oscillations, that not only converges with high-order but is also relatively simple to implement. We include a theoretical error analysis as well as a wide variety of numerical experiments to demonstrate its efficacy.