Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Strong tractability of multivariate integration using quasi-Monte Carlo algorithms

Author: Xiaoqun Wang
Journal: Math. Comp. 72 (2003), 823-838
MSC (2000): Primary 65C05, 65D30, 68Q25
Published electronically: June 25, 2002
MathSciNet review: 1954970
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We study quasi-Monte Carlo algorithms based on low discrepancy sequences for multivariate integration. We consider the problem of how the minimal number of function evaluations needed to reduce the worst-case error from its initial error by a factor of $\varepsilon$depends on ${\varepsilon}^{-1}$ and the dimension $s$. Strong tractability means that it does not depend on $s$ and is bounded by a polynomial in ${\varepsilon}^{-1}$. The least possible value of the power of ${\varepsilon}^{-1}$ is called the $\varepsilon$-exponent of strong tractability. Sloan and Wozniakowski established a necessary and sufficient condition of strong tractability in weighted Sobolev spaces, and showed that the $\varepsilon$-exponent of strong tractability is between 1 and 2. However, their proof is not constructive.

In this paper we prove in a constructive way that multivariate integration in some weighted Sobolev spaces is strongly tractable with $\varepsilon$-exponent equal to 1, which is the best possible value under a stronger assumption than Sloan and Wozniakowski's assumption. We show that quasi-Monte Carlo algorithms using Niederreiter's $(t,s)$-sequences and Sobol sequences achieve the optimal convergence order $O(N^{-1+\delta})$for any $\delta>0$ independent of the dimension with a worst case deterministic guarantee (where $N$ is the number of function evaluations). This implies that strong tractability with the best $\varepsilon$-exponent can be achieved in appropriate weighted Sobolev spaces by using Niederreiter's $(t,s)$-sequences and Sobol sequences.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 65C05, 65D30, 68Q25

Retrieve articles in all journals with MSC (2000): 65C05, 65D30, 68Q25

Additional Information

Xiaoqun Wang
Affiliation: Department of Mathematical Sciences, Tsinghua University, Beijing 100084, China

Keywords: Quasi--Monte Carlo methods, low discrepancy sequences, tractability, strong tractability, multidimensional integration
Received by editor(s): March 7, 2001
Received by editor(s) in revised form: August 16, 2001
Published electronically: June 25, 2002
Additional Notes: Supported by the NSF of China Grants 79970120 and 10001021.
Article copyright: © Copyright 2002 American Mathematical Society