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

Xu, Kuan, Austin, Anthony P., Wei, Ke (2017) A Fast Algorithm for the Convolution of Functions with Compact Support Using Fourier Extensions. SIAM Journal on Scientific Computing, 39 (6). A3089-A3106. ISSN 1064-8275. E-ISSN 1095-7197. (doi:10.1137/17M1114764) (KAR id:58502)

PDF Publisher pdf Language: English
Download this file (PDF/48kB)
Request a format suitable for use with assistive technology e.g. a screenreader
Official URL: https://doi.org/10.1137/17M1114764

Abstract

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.

Item Type:	Article
DOI/Identification number:	10.1137/17M1114764
Subjects:	Q Science > QA Mathematics (inc Computing science) > QA297 Numerical analysis
Divisions:	Divisions > Division of Computing, Engineering and Mathematical Sciences > School of Mathematics, Statistics and Actuarial Science
Depositing User:	Kuan Xu
Date Deposited:	09 Nov 2016 18:13 UTC
Last Modified:	05 Nov 2024 10:49 UTC
Resource URI:	https://kar.kent.ac.uk/id/eprint/58502 (The current URI for this page, for reference purposes)

University of Kent Author Information

Xu, Kuan.

Creator's ORCID:
CReDIT Contributor Roles:

Depositors only (login required):

Altmetric

Download Statistics

Total unique views for this document in KAR since July 2020. For more details click on the image.