Efficient function approximation on general bounded domains using splines on a Cartesian grid

DOI10.1007/S10444-022-09946-2MaRDI QIDQ2093701zbMATH OpenOpenAlexWikidataFDO

Authors Vincent Coppé, Daan Huybrechs

Publication date 27 October 2022

Published in Advances in Computational Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

function approximationirregular domainssplines

Mathematics Subject Classification ID

Numerical computation using splines (65D07) Algorithms for approximation of functions (65D15) Numerical solutions to overdetermined systems, pseudoinverses (65F20) Numerical methods for trigonometric approximation and interpolation (65T40)

Abstract: Functions on a bounded domain in scientific computing are often approximated using piecewise polynomial approximations on meshes that adapt to the shape of the geometry. We study the problem of function approximation using splines on a regular but oversampled grid that is defined on a bounding box. This approach allows the use of high order and highly structured splines as a basis for piecewise polynomials. The methodology is analogous to that of Fourier extensions, using Fourier series on a bounding box, which leads to spectral accuracy for smooth functions. However, Fourier extension approximations involve solving a highly ill-conditioned linear system, and this is an expensive step. The computational complexity of recent algorithms is $mathcalOleft(Nlo{g}^{2}left(Night)ight)$ in 1-D and $mathcalOleft(N^{2}lo{g}^{2}left(Night)ight)$ in 2-D. We show that, compared to Fourier extension, the compact support of B-splines enables improved complexity for multivariate approximations, namely $mathcalO(N)$ in 1-D, $mathcalOleft(N^{3/2}ight)$ in 2-D and more generally $mathcalOleft(N^{3(d-1)/d}ight)$ in $d$-D with $d>1$. By using a direct sparse QR solver for a related linear system, we also observe that the computational complexity can be nearly linear in practice. This comes at the cost of achieving only algebraic rates of convergence. Our statements are corroborated with numerical experiments and Julia code is available.

Recommendations

• Hierarchical extended B-splines for approximations on sparse grids
• Function approximation on arbitrary domains using Fourier extension frames
• APPROXIMATING SMOOTH, MULTIVARIATE FUNCTIONS ON IRREGULAR DOMAINS
• Approximation with diversified B-splines
• Near-optimal sampling strategies for multivariate function approximation on general domains

Cites work

• A fast algorithm for Fourier continuation
• A practical guide to splines
• Accurate, high-order representation of complex three-dimensional surfaces via Fourier continuation analysis
• B-spline signal processing. I. Theory
• B-spline signal processing. II. Efficiency design and applications
• Cardinal interpolation and spline functions
• Cardinal spline filters: Stability and convergence to the ideal sinc interpolator
• Computing the Minimum Fill-In is NP-Complete
• Fast algorithms for the computation of Fourier extensions of arbitrary length
• Finite cell method. \(h\)- and \(p\)-extension for embedded domain problems in solid mechanics
• Finite Element Methods with B-Splines
• 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}\)
• Frames and numerical approximation
• Frames and numerical approximation. II: Generalized sampling
• Function approximation on arbitrary domains using Fourier extension frames
• scientific article; zbMATH DE number 3650737 (Why is no real title available?)
• scientific article; zbMATH DE number 3703310 (Why is no real title available?)
• scientific article; zbMATH DE number 3486372 (Why is no real title available?)
• scientific article; zbMATH DE number 477682 (Why is no real title available?)
• Inverses of Band Matrices and Local Convergence of Spline Projections
• On the Fourier Extension of Nonperiodic Functions
• On the numerical stability of Fourier extensions
• On the Solution of Circulant Linear Systems
• Prolate Spheroidal Wave Functions, Fourier Analysis, and Uncertainty-V: The Discrete Case
• Spline and Spline Wavelet Methods with Applications to Signal and Image Processing
• Spline and spline wavelet methods with applications to signal and image processing. Volume II. Non-periodic splines
• The AZ algorithm for least squares systems with a known incomplete generalized inverse
• The finite cell method: a review in the context of higher-order structural analysis of CAD and image-based geometric models
• The Future Fast Fourier Transform?
• Weighted extended B-spline approximation of Dirichlet problems

Cited in

(7)

• BSPlineextension.jl
• Roadmap to spline-fitting potentials in high dimensions
• Computing with functions on domains with arbitrary shapes
• A mapped polynomial method for high-accuracy approximations on arbitrary grids
• Efficient least squares approximation and collocation methods using radial basis functions
• A low-rank matrix approach to compute polynomial approximations of smooth two-dimensional functions
• Efficient function approximation in enriched approximation spaces

Describes a project that uses

Uses Software

• LowRankApprox.jl
• Julia
• GitHub

This page was built for publication: Efficient function approximation on general bounded domains using splines on a Cartesian grid

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