aqora

A New Quasi-Monte Carlo Algorithm for Numerical Integration of Smooth Functions

Emanouil I. Atanassov, Ivan Dimov, Mariya K. Durchova

Lecture notes in computer scienceJan 1, 20043 citations

The curse of dimensionality for numerical integration of smooth functions

A. Hinrichs, E. Novak, M. Ullrich +1 more

We prove the curse of dimensionality for multivariate integration of C r C^r functions: The number of needed function values to achieve an error ϵ \epsilon is larger than c r ( 1 + γ ) d c_r (1+\gamma )^d for ϵ ≤ ϵ 0 \epsilon \le \epsilon _0 , where c r , γ > 0 c_r,\gamma >0 . The proofs are based on volume estimates for r = 1 r=1 together with smoothing by convolution. This allows us to obtain smooth fooling functions for r > 1 r>1 .

arXiv:1211.0871Mathematics of ComputationJun 20, 201431 citations

On the Hardness of Approximate Multivariate Integration

Ioannis Koutis

Lecture notes in computer scienceJan 1, 20032 citations

High dimensional integration: New weapons fighting the curse of dimensionality

Peter Zinterhof

The approximate computation of the definite integral of a function of several variables is one of the basic problems of numerical analysis. The problem is hard because of the so called “curse of dimensionality”. This curse consists of the following: applying an integration rule with N nodes to an univariate function, you will get an integration error, say, ε> 0. Applying

Physics of Particles and Nuclei LettersMay 1, 20083 citations

Optimal confidence for Monte Carlo integration of smooth functions

Robert J. Kunsch, Daniel Rudolf

arXiv:1809.09890Advances in Computational MathematicsNov 29, 201914 citations

Complexity of multivariate Feynman-Kac path integration in randomized and quantum settings

Marek Kwas

The Feynman-Kac path integration problem was studied in the worst case setting by Plaskota et al. (J. Comp. Phys. 164 (2000) 335) for the univariate case and by Kwas and Li (J. Comp. 19 (2003) 730) for the multivariate case with d space variables. In this paper we consider the multivariate Feynman-Kac path integration problem in the randomized and quantum settings. For smooth multivariate functions, it was proven in Kwas and Li (2003) that the classical worst case complexity suffers from the curse of dimensionality in d. We show that in both the randomized and quantum settings the curse of dimensionality is vanquished, i.e., the number of function evaluations and/or quantum queries required to compute an e-approximation has a bound independent of d and depending polynomially on 1/e. The exponents of these polynomials are at most 2 in the randomized setting and at most 1 in the quantum setting. Hence we have exponential speedup over the classical worst case setting and quadratic speedup of the quantum setting over the randomized setting. However, both the randomized and quantum algorithms presented here still require extensive precomputing, similar to the algorithms of Plaskota et al. (2000) and Kwas and Li(2003).The Feynman-Kac path integration problem was studied in the worst case setting by Plaskota et al. (J. Comp. Phys. 164 (2000) 335) for the univariate case and by Kwas and Li (J. Comp. 19 (2003) 730) for the multivariate case with d space variables. In this paper we consider the multivariate Feynman-Kac path integration problem in the randomized and quantum settings. For smooth multivariate functions, it was proven in Kwas and Li (2003) that the classical worst case complexity suffers from the curse of dimensionality in d. We show that in both the randomized and quantum settings the curse of dimensionality is vanquished, i.e., the number of function evaluations and/or quantum queries required to compute an e-approximation has a bound independent of d and depending polynomially on 1/e. The exponents of these polynomials are at most 2 in the randomized setting and at most 1 in the quantum setting. Hence we have exponential speedup over the classical worst case setting and quadratic speedup of the quantum setting over the randomized setting. However, both the randomized and quantum algorithms presented here still require extensive precomputing, similar to the algorithms of Plaskota et al. (2000) and Kwas and Li(2003).

arXiv:quant-ph/0410134Oct 18, 20049 citations

The curse of dimensionality for numerical integration of smooth functions II

Related papers

The curse of dimensionality for numerical integration of smooth functions II

Related papers