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

DOI10.1137/17M1114764zbMath1379.65096OpenAlexW2779980829MaRDI QIDQ4600006

Ke Wei, Kuan Xu, Anthony P. Austin

Publication date: 5 January 2018

Published in: SIAM Journal on Scientific Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/17m1114764

zbMATH Keywords

complexityalgorithmconvolutionfast Fourier transformToeplitz matrixFourier extensionVolterra convolution integralFredholm convolution integral

Mathematics Subject Classification ID

Convolution as an integral transform (44A35) Numerical methods for discrete and fast Fourier transforms (65T50) Numerical methods for integral transforms (65R10) Integral equations of the convolution type (Abel, Picard, Toeplitz and Wiener-Hopf type) (45E10) Fredholm integral equations (45B05) Complexity and performance of numerical algorithms (65Y20) Volterra integral equations (45D05)

Related Items (3)

Spectral Approximation of Convolution Operators ⋮ A Sparse Spectral Method for Volterra Integral Equations Using Orthogonal Polynomials on the Triangle ⋮ A Fourier Extension Based Numerical Integration Scheme for Fast and High-Order Approximation of Convolutions with Weakly Singular Kernels

Uses Software

• Chebfun

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the numerical stability of Fourier extensions
• Parameter selection and numerical approximation properties of Fourier extensions from fixed data
• Bounds for polynomials with a unit discrete norm
• Divergence (Runge phenomenon) for least-squares polynomial approximation on an equispaced grid and mock-Chebyshev subset interpolation
• A comparison of numerical algorithms for Fourier extension of the first, second, and third kinds
• Accurate, high-order representation of complex three-dimensional surfaces via Fourier continuation analysis
• On the resolution power of Fourier extensions for oscillatory functions
• Fast Algorithms for the Computation of Fourier Extensions of Arbitrary Length
• An Algorithm for the Convolution of Legendre Series
• On the Fourier Extension of Nonperiodic Functions
• Impossibility of Fast Stable Approximation of Analytic Functions from Equispaced Samples
• A Fast Algorithm for Fourier Continuation
• The Numerical Solution of Integral Equations of the Second Kind
• Collocation Methods for Volterra Integral and Related Functional Differential Equations
• Frames and Numerical Approximation
• Optimal sampling rates for approximating analytic functions from pointwise samples

This page was built for publication: A Fast Algorithm for the Convolution of Functions with Compact Support Using Fourier Extensions