Fast algorithms for the computation of Fourier extensions of arbitrary length

DOI10.1137/15M1030923MaRDI QIDQ2797086zbMATH OpenFDO

Authors Roel Matthysen, Daan Huybrechs

Publication date 4 April 2016

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

Full work available at URL https://arxiv.org/abs/1509.00206

zbMATH Keywords

algorithmconvergenceFourier continuationFourier extensionFourier seriesGibbs phenomenonleast squares problemprolate spheroidal wave functions

Mathematics Subject Classification ID

Trigonometric approximation (42A10) Fourier coefficients, Fourier series of functions with special properties, special Fourier series (42A16) Numerical methods for trigonometric approximation and interpolation (65T40)

Abstract: Fourier series of smooth, non-periodic functions on $[-1,1]$ are known to exhibit the Gibbs phenomenon, and exhibit overall slow convergence. One way of overcoming these problems is by using a Fourier series on a larger domain, say $[-T,T]$ with $T>1$, a technique called Fourier extension or Fourier continuation. When constructed as the discrete least squares minimizer in equidistant points, the Fourier extension has been shown shown to converge geometrically in the truncation parameter $N$. A fast $mathcalO(Nlo{g}^{2}N)$ algorithm has been described to compute Fourier extensions for the case where $T=2$, compared to $mathcalO(N^3)$ for solving the dense discrete least squares problem. We present two $mathcalO(Nlo{g}^{2}N)$ algorithms for the computation of these approximations for the case of general $T$, made possible by exploiting the connection between Fourier extensions and Prolate Spheroidal Wave theory. The first algorithm is based on the explicit computation of so-called periodic discrete prolate spheroidal sequences, while the second algorithm is purely algebraic and only implicitly based on the theory.

Recommendations

• A fast algorithm for Fourier continuation
• On the Fourier Extension of Nonperiodic Functions
• On the numerical stability of Fourier extensions
• Pointwise and uniform convergence of Fourier extensions
• A comparison of numerical algorithms for Fourier extension of the first, second, and third kinds

Cites work

• A Class of Nonharmonic Fourier Series
• A comparison of numerical algorithms for Fourier extension of the first, second, and third kinds
• A fast algorithm for Fourier continuation
• A spectral FC solver for the compressible Navier-Stokes equations in general domains. I: Explicit time-stepping
• Accurate, high-order representation of complex three-dimensional surfaces via Fourier continuation analysis
• Approximation error in regularized SVD-based Fourier continuations
• Eigenvectors of a Toeplitz Matrix: Discrete Version of the Prolate Spheroidal Wave Functions
• Extrapolation algorithms for discrete signals with application in spectral estimation
• Fourier embedded domain methods: Extending a function defined on an irregular region to a rectangle so that the extension is spatially periodic and \(C^{\infty}\)
• High-order unconditionally stable FC-AD solvers for general smooth domains. I: Basic elements
• High-order unconditionally stable FC-AD solvers for general smooth domains. II: Elliptic, parabolic and hyperbolic PDEs; theoretical considerations
• scientific article; zbMATH DE number 3640828 (Why is no real title available?)
• scientific article; zbMATH DE number 2042292 (Why is no real title available?)
• scientific article; zbMATH DE number 1793704 (Why is no real title available?)
• scientific article; zbMATH DE number 829826 (Why is no real title available?)
• On the Fourier Extension of Nonperiodic Functions
• On the numerical stability of Fourier extensions
• On the Periodic Discrete Prolate Spheroidal Sequences
• On the resolution power of Fourier extensions for oscillatory functions
• Parameter selection and numerical approximation properties of Fourier extensions from fixed data
• Prolate Spheroidal Wave Functions, Fourier Analysis and Uncertainty - I
• Prolate Spheroidal Wave Functions, Fourier Analysis and Uncertainty - II
• Prolate Spheroidal Wave Functions, Fourier Analysis and Uncertainty - IV: Extensions to Many Dimensions; Generalized Prolate Spheroidal Functions
• Prolate Spheroidal Wave Functions, Fourier Analysis and Uncertainty-III: The Dimension of the Space of Essentially Time- and Band-Limited Signals
• Prolate Spheroidal Wave Functions, Fourier Analysis, and Uncertainty-V: The Discrete Case
• Some comments on Fourier analysis, uncertainty and modeling

Cited in

(39)

• A comparison of numerical algorithms for Fourier extension of the first, second, and third kinds
• Improved bounds for the eigenvalues of prolate spheroidal wave functions and discrete prolate spheroidal sequences
• Frame approximation with bounded coefficients
• Efficient function approximation on general bounded domains using splines on a Cartesian grid
• Two algorithms for periodic extension on uniform grids
• Frames and numerical approximation. II: Generalized sampling
• A high-order embedded domain method combining a predictor-corrector-Fourier-continuation-Gram method with an integral Fourier pseudospectral collocation method for solving linear partial differential equations in complex domains
• The fast Slepian transform
• Fast and stable approximation of analytic functions from equispaced samples via polynomial frames
• Discrete periodic extension using an approximate step function
• On the Fourier Extension of Nonperiodic Functions
• A fast algorithm for Fourier continuation
• scientific article; zbMATH DE number 3921936 (Why is no real title available?)
• On the numerical stability of Fourier extensions
• Function approximation on arbitrary domains using Fourier extension frames
• A fast algorithm for the convolution of functions with compact support using Fourier extensions
• Computing with functions on domains with arbitrary shapes
• Subperiodic trigonometric hyperinterpolation
• Upper and Lower Bounds on Time-Space Tradeoffs for Computations with Embedded Fast Fourier Transforms
• How exponentially ill-conditioned are contiguous submatrices of the Fourier matrix?
• Two-dimensional Fourier continuation and applications
• The AZ algorithm for least squares systems with a known incomplete generalized inverse
• A Fourier Extension Based Numerical Integration Scheme for Fast and High-Order Approximation of Convolutions with Weakly Singular Kernels
• Frames and numerical approximation
• On the computation of the SVD of Fourier submatrices
• Oversampled collocation approximation method of functions via Jacobi frames
• Local behaviors of Fourier expansions for functions of limited regularities
• Efficient least squares approximation and collocation methods using radial basis functions
• A local Fourier extension method for function approximation
• Physics-informed kernel learning
• Deflation techniques for finding multiple local minima of a nonlinear least squares problem
• Efficient function approximation in enriched approximation spaces
• A biharmonic solver based on Fourier extension with oversampling technique for arbitrary domain
• A modified FC-Gram approximation algorithm with provable error bounds
• Parameter selection and numerical approximation properties of Fourier extensions from fixed data
• Fast algorithms for Fourier extension based on boundary interval data
• An oversampled collocation approach of the wave based method for Helmholtz problems
• Pointwise and uniform convergence of Fourier extensions
• Asymptotic Fourier coefficients for a \(C^\infty\) bell (smoothed-``top-hat) \& the Fourier extension problem

This page was built for publication: Fast algorithms for the computation of Fourier extensions of arbitrary length

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2797086)