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

DOI10.1007/S10444-022-09946-2zbMATH Open1504.65041arXiv1911.07894OpenAlexW4297225082WikidataQ117717422 ScholiaQ117717422MaRDI QIDQ2093701

Author name not available (Why is that?)

Publication date: 27 October 2022

Published in: (Search for Journal in Brave)

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.

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

zbMATH Keywords

No records found.

Mathematics Subject Classification ID

No records found.

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)