Some Results on the Complexity of Numerical Integration

DOI10.1007/978-3-319-33507-0_6zbMath1356.65085arXiv1409.6714OpenAlexW2357479853MaRDI QIDQ2957029

Erich Novak

Publication date: 20 January 2017

Published in: Springer Proceedings in Mathematics & Statistics (Search for Journal in Brave)

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

zbMATH Keywords

numerical integrationcurse of dimensionalityrandomized algorithmstractabilityoscillatory integralscomplexity of integration

Mathematics Subject Classification ID

Multidimensional problems (41A63) Approximate quadratures (41A55) Numerical quadrature and cubature formulas (65D32) Complexity and performance of numerical algorithms (65Y20)

Related Items

Deterministic constructions of high-dimensional sets with small dispersion, Optimal randomized quadrature for weighted Sobolev and Besov classes with the Jacobi weight on the ball, A Monte Carlo Method for Integration of Multivariate Smooth Functions, On the distance between random events on a network, Higher-Order Monte Carlo through Cubic Stratification, Risk bounds when learning infinitely many response functions by ordinary linear regression, Discrepancy-based inference for intractable generative models using quasi-Monte Carlo, An upper bound on the minimal dispersion, An Upper Bound of the Minimal Dispersion via Delta Covers, On the Wasserstein distance between classical sequences and the Lebesgue measure, Solvable integration problems and optimal sample size selection, On a Kantorovich-Rubinstein inequality, Monte Carlo integration with a growing number of control variates, Convergence analysis of deterministic kernel-based quadrature rules in misspecified settings, Integral estimation based on Markovian design, Incremental reasoning in probabilistic signal temporal logic, Stable high-order randomized cubature formulae in arbitrary dimension

Cites Work

• Discrepancy Theory and Quasi-Monte Carlo Integration
• Calculation of Discrepancy Measures and Applications
• On tractability of path integration
• Sparse grids
• Multivariate integration of infinitely many times differentiable functions in weighted Korobov spaces
• Average case tractability of approximating ∞-variate functions
• Probabilistic discrepancy bound for Monte Carlo point sets
• Introduction to Quasi-Monte Carlo Integration and Applications
• High-dimensional integration: The quasi-Monte Carlo way
• On the optimality of linear methods for operator approximation in convex classes of functions
• On irregularities of distribution
• Quantum complexity of integration
• Intractability results for integration and discrepancy
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Optimal quasi-Monte Carlo rules on order 2 digital nets for the numerical integration of multivariate periodic functions
• Complexity of parametric integration in various smoothness classes
• Complexity of oscillatory integration for univariate Sobolev spaces
• Infinite-dimensional integration in weighted Hilbert spaces: anchored decompositions, optimal deterministic algorithms, and higher-order convergence
• Deterministic multi-level algorithms for infinite-dimensional integration on \(\mathbb R^{\mathbb N}\)
• Monte Carlo algorithms.
• Lower bounds for the complexity of linear functionals in the randomized setting
• Tractability of infinite-dimensional integration in the worst case and randomized settings
• Covering numbers, dyadic chaining and discrepancy
• Monte Carlo and quasi-Monte Carlo methods 2010. Selected papers based on the presentations at the 9th international conference on Monte Carlo and quasi Monte Carlo in scientific computing (MCQMC 2010), Warsaw, Poland, August 15--20, 2010.
• Efficient calculation of the worst-case error and (fast) component-by-component construction of higher order polynomial lattice rules
• Linear vs. nonlinear algorithms for linear problems
• Liberating the dimension
• Algorithmic construction of low-discrepancy point sets via dependent randomized rounding
• Tractability of multivariate problems. Volume III: Standard information for operators
• Infinite-dimensional quadrature and approximation of distributions
• Function spaces in Lipschitz domains and optimal rates of convergence for sampling
• Randomly shifted lattice rules for unbounded integrands
• Covering numbers, Vapnik-Červonenkis classes and bounds for the star-discrepancy
• Quadrature for self-affine distributions on \(\mathbb R^d\)
• Tractability of multivariate problems. Volume I: Linear information
• Optimal importance sampling for the approximation of integrals
• Bases in function spaces, sampling, discrepancy, numerical integration
• Tractability of multivariate problems. Volume II: Standard information for functionals.
• Multi-level Monte Carlo algorithms for infinite-dimensional integration on \(\mathbb R^{\mathbb N}\)
• A geometric inequality and the complexity of computing volume
• Lower bounds for the complexity of Monte Carlo function approximation
• Deterministic and stochastic error bounds in numerical analysis
• Asymptotically sharp bounds for the remainder for the best quadrature formulas for several classes of functions
• Faithful asymptotics of remainders optimal for some classes of functions with cubic weight formulas
• When are quasi-Monte Carlo algorithms efficient for high dimensional integrals?
• Explicit cost bounds of algorithms for multivariate tensor product problems
• Tractability of multivariate integration for periodic functions
• Tractability of tensor product linear operators
• Quantum integration in Sobolev classes
• Component-by-component constructions achieve the optimal rate of convergence for multivariate integration in weighted Korobov and Sobolev spaces
• Cubature formulas, discrepancy, and nonlinear approximation
• Quantum summation with an application to integration.
• Finite-order weights imply tractability of multivariate integration
• Liberating the weights
• The optimal error of Monte Carlo integration
• Weighted tensor product algorithms for linear multivariate problems
• Simple cubature formulas with high polynomial exactness
• Integration and approximation in arbitrary dimensions
• Optimal randomized changing dimension algorithms for infinite-dimensional integration on function spaces with ANOVA-type decomposition
• A lower bound for the discrepancy of a random point set
• The cost of deterministic, adaptive, automatic algorithms: cones, not balls
• On the approximate calculation of multiple integrals
• On approximate recovery of functions with bounded mixed derivative
• Change of variable in spaces of mixed smoothness and numerical integration of multivariate functions on the unit cube
• A universal algorithm for multivariate integration
• The power of adaptive algorithms for functions with singularities
• On weighted Hilbert spaces and integration of functions of infinitely many variables
• Weak and quasi-polynomial tractability of approximation of infinitely differentiable functions
• The curse of dimensionality for numerical integration of smooth functions. II
• Numerical integration of Hölder continuous, absolutely convergent Fourier, Fourier cosine, and Walsh series
• On weak tractability of the Clenshaw-Curtis Smolyak algorithm
• A note on the existence of sequences with small star discrepancy
• Sampling numbers and function spaces
• Fast component-by-component construction of rank-1 lattice rules with a non-prime number of points
• Good lattice rules in weighted Korobov spaces with general weights
• High dimensional integration of smooth functions over cubes
• On the power of adaption
• Component-by-component construction of good lattice rules
• Explicit constructions in the classical mean squares problem in irregularities of point distribution
• The Role of Frolov's Cubature Formula for Functions with Bounded Mixed Derivative
• Infinite-dimensional integration on weighted Hilbert spaces
• Explicit error bounds for Markov chain Monte Carlo
• Discrepancy, Integration and Tractability
• Complexity of Banach Space Valued and Parametric Integration
• Lower Error Bounds for Randomized Multilevel and Changing Dimension Algorithms
• On “Upper Error Bounds for Quadrature Formulas on Function Classes” by K.K. Frolov
• Spline interpolation on sparse grids
• On the step-by-step construction of quasi--Monte Carlo integration rules that achieve strong tractability error bounds in weighted Sobolev spaces
• Exponential convergence and tractability of multivariate integration for Korobov spaces
• The curse of dimensionality for numerical integration of smooth functions
• Fast algorithms for component-by-component construction of rank-1 lattice rules in shift-invariant reproducing kernel Hilbert spaces
• The weighted star discrepancy of Korobov’s $p$-sets
• Tractability of multivariate analytic problems
• Component-by-component construction of low-discrepancy point sets of small size
• On the Optimal Solution of Large Linear Systems
• APPROXIMATE RECOVERY OF PERIODIC FUNCTIONS OF SEVERAL VARIABLES
• On irregularities of distribution, IV
• Cubature formulae for Besov classes
• The inverse of the star-discrepancy depends linearly on the dimension
• On strong tractability of weighted multivariate integration
• Lower bounds for the integration error for multivariate functions with mixed smoothness and optimal Fibonacci cubature for functions on the square
• Optimal Randomized Multilevel Algorithms for Infinite-Dimensional Integration on Function Spaces with ANOVA-Type Decomposition
• Computation of Expectations by Markov Chain Monte Carlo Methods