Fast Algorithms for Periodic Spline Wavelets on Sparse Grids

DOI10.1137/S1064827596309098MaRDI QIDQ4253057zbMATH OpenFDO

Authors Kai Bittner

Publication date 24 June 1999

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

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

zbMATH Keywords

Boolean sumsperiodic interpolationsparse gridssplineswavelets

Mathematics Subject Classification ID

Spline approximation (41A15) Multidimensional problems (41A63) Numerical interpolation (65D05) Numerical computation using splines (65D07) Complexity and performance of numerical algorithms (65Y20)

Review text

In the paper, new fast algorithms for decomposition, reconstruction and interpolation of functions on bivariate sparse grids are presented. These algorithms are based on fast algorithms in the univariate case using periodic spline wavelets with minimal support. In the bivariate case, the concept of Boolean sums and sparse grids (instead of tensor products) leads to sample spaces of dimension \(O(j2^j)\) (instead of \(O(2^{2j})\)), whereas the approximation order is only by a logarithmic factor lower then in the tensor product case. The new reconstruction and decomposition algorithms on sparse grids have an arithmetical complexity \(O(j2^j)\) only.

Recommendations

• Periodic interpolation and wavelets on sparse grids
• B-spline quasi-interpolation on sparse grids
• Algorithms of wavelet compression of linear spline spaces
• Fast algorithms for adaptive free knot spline approximation using nonuniform biorthogonal spline wavelets

Cited in

(16)

• Periodic interpolation and wavelets on sparse grids
• Adaptive wavelet methods using semiorthogonal spline wavelets: Sparse evaluation of nonlinear functions
• Fast Boolean approximation methods for solving integral equations in high dimensions
• Fast discrete algorithms for sparse Fourier expansions of high dimensional functions
• Sparse data structure design for wavelet-based methods
• Spline interpolation on sparse grids
• Fast computation of the multidimensional discrete Fourier transform and discrete backward Fourier transform on sparse grids
• Algorithm 847
• scientific article; zbMATH DE number 733428 (Why is no real title available?)
• scientific article; zbMATH DE number 1124591 (Why is no real title available?)
• Numerical operator calculus in higher dimensions
• Orthogonal polynomial expansions on sparse grids
• Fast algorithms for adaptive free knot spline approximation using nonuniform biorthogonal spline wavelets
• Fast discrete Fourier transform on generalized sparse grids
• B-spline quasi-interpolation on sparse grids
• Randomized sparse grid algorithms for multivariate integration on Haar wavelet spaces

This page was built for publication: Fast Algorithms for Periodic Spline Wavelets on Sparse Grids

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