Algorithms and complexity for functions on general domains

DOI10.1016/J.JCO.2020.101458zbMATH Open1460.65171arXiv1908.05943OpenAlexW3002829955WikidataQ126313889 ScholiaQ126313889MaRDI QIDQ1996873FDOQ1996873

Authors: Erich Novak 

Publication date: 26 February 2021

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

Abstract: Error bounds and complexity bounds in numerical analysis and information-based complexity are often proved for functions that are defined on very simple domains, such as a cube, a torus, or a sphere. We study optimal error bounds for the approximation or integration of functions defined on $D_{d}subset{R}^d$ and only assume that $D_d$ is a bounded Lipschitz domain. Some results are even more general. We study three different concepts to measure the complexity: order of convergence, asymptotic constant, and explicit uniform bounds, i.e., bounds that hold for all $n$ (number of pieces of information) and all (normalized) domains. It is known for many problems that the order of convergence of optimal algorithms does not depend on the domain $D_{d}subset{R}^d$. We present examples for which the following statements are true: 1) Also the asymptotic constant does not depend on the shape of $D_d$ or the imposed boundary values, it only depends on the volume of the domain. 2) There are explicit and uniform lower (or upper, respectively) bounds for the error that are only slightly smaller (or larger, respectively) than the asymptotic error bound.

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

Recommendations

• Average complexity for linear operators over bounded domains
• Worst case complexity of weighted approximation and integration over \(\mathbb{R}^d\)
• Product rules are optimal for numerical integration in classical smoothness spaces
• ``Curse of dimensionality for complexity of approximation for classes of functions satisfying Lipschitz condition
• Probabilistic complexity analysis for linear problems in bounded domains

zbMATH Keywords

error boundsbounded Lipschitz domaincomplexity analysisfunctions on general domains

Mathematics Subject Classification ID

Complexity and performance of numerical algorithms (65Y20) Numerical integration (65D30) Algorithms for approximation of functions (65D15)

Cites Work

• Approximation of mixed order Sobolev functions on the \(d\)-torus: asymptotics, preasymptotics, and \(d\)-dependence
• Title not available (Why is that?)
• Optimum quantization and its applications
• On the Schrödinger equation and the eigenvalue problem
• Deterministic and stochastic error bounds in numerical analysis
• Title not available (Why is that?)
• Tractability of multivariate problems. Volume III: Standard information for operators
• Tractability of multivariate problems. Volume I: Linear information
• Function spaces and wavelets on domains
• Tractability of multivariate problems. Volume II: Standard information for functionals.
• High dimensional polynomial interpolation on sparse grids
• On weak tractability of the Clenshaw-Curtis Smolyak algorithm
• Leading term in the asymptotic spectral formula for nonsmooth elliptic problems
• Bases in function spaces, sampling, discrepancy, numerical integration
• Approximation numbers of Sobolev embeddings-sharp constants and tractability
• Optimal approximation of multivariate periodic Sobolev functions in the sup-norm
• Widths of embeddings in function spaces
• Upper bounds for the Neumann eigenvalues on a bounded domain in Euclidean space
• Asymptotic behavior of the spectrum of differential equations
• A note on coverings
• Approximation of infinitely differentiable multivariate functions is intractable
• The curse of dimensionality for numerical integration of smooth functions
• Product rules are optimal for numerical integration in classical smoothness spaces
• Title not available (Why is that?)
• Sobolev bounds on functions with scattered zeros, with applications to radial basis function surface fitting
• Title not available (Why is that?)
• Optimal recovery of isotropic classes of twice-differentiable multivariate functions
• Tractability results for weighted Banach spaces of smooth functions
• Title not available (Why is that?)
• Optimal approximation of elliptic problems by linear and nonlinear mappings. I
• Degree-independent Sobolev extension on locally uniform domains
• Ausfüllung und Überdeckung konvexer Körper durch konvexe Körper
• The curse of dimensionality for numerical integration of smooth functions. II
• Function spaces in Lipschitz domains and optimal rates of convergence for sampling
• Randomized approximation of Sobolev embeddings. II
• Randomized approximation of Sobolev embeddings. III
• Optimal method of constructing best uniform approximations for functions of a certain class
• Sampling numbers and function spaces
• Weak and quasi-polynomial tractability of approximation of infinitely differentiable functions
• The curse of dimensionality for numerical integration on general domains
• Uniform recovery of high-dimensional \(C^r\)-functions
• On weak tractability of the Smolyak algorithm for approximation problems
• Tensor power sequences and the approximation of tensor product operators
• On the complexity of computing the \(L_q\) norm
• Sharp estimates for approximation numbers of non-periodic Sobolev embeddings
• Wavelet para-bases and sampling numbers in function spaces on domains
• Distribution of the eigenvalues for differential operators with constant coefficients

Cited In (6)

• How anisotropic mixed smoothness affects the decay of singular numbers for Sobolev embeddings
• Title not available (Why is that?)
• Optimal recovery and volume estimates
• Recovery of Sobolev functions restricted to iid sampling
• Lower bounds of cowidths and widths of multiplier operators
• Title not available (Why is that?)

This page was built for publication: Algorithms and complexity for functions on general domains

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