Your access to this SIAM content is provided through the subscription of University of Kent

SIAM Journal on Scientific Computing

Methods and Algorithms for Scientific Computing

A Fast Algorithm for the Convolution of Functions with Compact Support Using Fourier Extensions

Related Databases

Web of Science

You must be logged in with an active subscription to view this.

Article Data


Submitted: 3  February  2017
Accepted: 07 September 2017
Published online: 21 December 2017

Publication Data

ISSN (print): 1064-8275
ISSN (online): 1095-7197
CODEN: sjoce3

We present a new algorithm for computing the convolution of two compactly supported functions. The algorithm approximates the functions to be convolved using Fourier extensions and then uses the fast Fourier transform to efficiently compute Fourier extension approximations to the pieces of the result. The complexity of the algorithm is $\mathcal{O}\bigl(N (\log N)^2\bigr)$, where $N$ is the number of degrees of freedom used in each of the Fourier extensions.

© 2017, Society for Industrial and Applied Mathematics