Fast discrete algorithms for sparse Fourier expansions of high dimensional functions

DOI10.1016/j.jco.2009.10.001zbMath1184.65124OpenAlexW2027590575MaRDI QIDQ2655801

Ying Jiang, Yuesheng Xu

Publication date: 26 January 2010

Published in: Journal of Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jco.2009.10.001

zbMATH Keywords

numerical examplessparse gridFourier coefficientsfast algorithmquadrature schemeSobolev regularityhyperbolic crossmultivariate functionoptimal approximation ordermultiscale Lagrange interpolationsparse Fourier expansion

Mathematics Subject Classification ID

Numerical methods for trigonometric approximation and interpolation (65T40) Fourier series and coefficients in several variables (42B05)

Related Items (22)

Fast Fourier-Galerkin methods for first-kind logarithmic-kernel integral equations on open arcs ⋮ A fast Fourier-Galerkin method solving a system of integral equations for the biharmonic equation ⋮ Fast computation of the multidimensional discrete Fourier transform and discrete backward Fourier transform on sparse grids ⋮ Fast Fourier-Galerkin methods for nonlinear boundary integral equations ⋮ Grouped Transformations and Regularization in High-Dimensional Explainable ANOVA Approximation ⋮ A fast discrete spectral method for stochastic partial differential equations ⋮ A fully discrete high-order fast multiscale Galerkin method for solving boundary integral equations in a domain with corners ⋮ A fast solver for boundary integral equations of the modified Helmholtz equation ⋮ The numerical integration scheme for a fast Petrov-Galerkin method for solving the generalized airfoil equation ⋮ Computing the Newton potential in the boundary integral equation for the Dirichlet problem of the Poisson equation ⋮ Orthogonal polynomial expansions on sparse grids ⋮ A fast solver for the Hilbert-type singular integral equations based on the direct Fourier spectral method ⋮ Interpolation lattices for hyperbolic cross trigonometric polynomials ⋮ Fast sparse nonlinear Fourier expansions of high dimensional functions ⋮ A fast numerical solution for the first kind boundary integral equation for the Helmholtz equation ⋮ B-spline quasi-interpolation on sparse grids ⋮ Fast Fourier-Galerkin methods for solving singular boundary integral equations: Numerical integration and precondition ⋮ Approximation of high-dimensional kernel matrices by multilevel circulant matrices ⋮ A fully discrete fast Fourier-Galerkin method solving a boundary integral equation for the biharmonic equation ⋮ Fast Discrete Fourier Transform on Generalized Sparse Grids ⋮ Approximation of multivariate periodic functions by trigonometric polynomials based on sampling along rank-1 lattice with generating vector of Korobov form ⋮ Approximation of multivariate periodic functions by trigonometric polynomials based on rank-1 lattice sampling

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Hyperbolic cross and the complexity of the approximate solution of Fredholm integral equations of the second kind with differentiable kernels
• Fouriertransform on sparse grids with hierarchical bases
• A construction of refinable sets for interpolating wavelets
• Higher order sparse grid methods for elliptic partial differential equations with variable coefficients
• Optimized tensor-product approximation spaces
• Sparse approximation of singularity functions
• Information complexity of multivariate Fredholm integral equations in Sobolev classes
• High dimensional polynomial interpolation on sparse grids
• Fourier transform on sparse grids: Code design and the time dependent Schrödinger equation
• On quadrature methods for highly oscillatory integrals and their implementation
• Fast Boolean approximation methods for solving integral equations in high dimensions
• A Fast Fourier–Galerkin Method for Solving Singular Boundary Integral Equations
• Strang Splitting for the Time-Dependent Schrödinger Equation on Sparse Grids
• Lattice Methods for Multiple Integration: Theory, Error Analysis and Examples
• Procedures for Computing One- and Two-Dimensional Integrals of Functions with Rapid Irregular Oscillations
• Fast Algorithms for Periodic Spline Wavelets on Sparse Grids
• A construction of interpolating wavelets on invariant sets
• On the numerical quadrature of highly-oscillating integrals II: Irregular oscillators
• On the numerical quadrature of highly-oscillating integrals I: Fourier transforms
• Sparse grids
• An Algorithm for the Machine Calculation of Complex Fourier Series
• Efficient quadrature of highly oscillatory integrals using derivatives
• Two‐Scale Boolean Galerkin Discretizations for Fredholm Integral Equations of the Second Kind
• Fast Algorithms for Spherical Harmonic Expansions

This page was built for publication: Fast discrete algorithms for sparse Fourier expansions of high dimensional functions