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

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?)

  • 1. N. Aronszajn, Theory of reproducing kernels, Trans. Amer. Math. Soc., 68 (1950), 337-404. MR 14:479c
  • 2. N. S. Bakhvalov, On approximate computation of multiple integrals, Vestnik Moskov. Univ. Ser. Mat. Mekh. Astr. Fiz. Khim 1959, no. 4, 3-18 (Russian). MR 22:6077
  • 3. P. Bratley, B. L. Fox and H. Niederreiter, Implementation and tests of low discrepancy sequences, ACM Trans. Model. Comput. Simul., 2 (1992), 195-213.
  • 4. R. E. Caflisch, W. Morokoff and A. Owen, Valuation of mortgage backed securities using Brownian bridges to reduce effective dimension, J. Comp. Finance, 1 (1997), 27-46.
  • 5. H. Faure, Discrépance de suites associées à un système de numération (en dimension s), Acta Arith., 41(1982), 337-351. MR 84m:10050
  • 6. J. H. Halton, On the efficiency of certain quasi-random sequences of points in evaluating multi-dimensional integrals, Numer. Math., 2 (1960), 84-90. MR 22:12688
  • 7. F. J. Hickernell, A generalized discrepancy and quadrature error bound, Math. Comp., 67 (1998), 299-322. MR 98c:65032
  • 8. F. J. Hickernell and X. Wang, The error bounds and tractability of quasi-Monte Carlo algorithms in infinite dimension, Math. Comp., 71 (2002), 1641-1661.
  • 9. F. J. Hickernell and H. Wozniakowski, Integration and approximation in arbitrary dimension, Advances in Comput. Math., 12 (2000), 25-58. MR 2001d:65017
  • 10. R. Lidl and H. Niederreiter, Introduction to Finite Fields and Their Applications, Cambridge University Press, 1986. MR 88c:11073
  • 11. W. J. Morokoff and R. E. Caflisch, Quasi-random sequences and their discrepancies, SIAM J. Sci. Comput., 15 (1994), 1251-1279. MR 95e:65009
  • 12. H. Niederreiter, Low-discrepancy and low-dispersion sequences, J. Number Theory, 30 (1988), 51-70. MR 89k:11064
  • 13. H. Niederreiter, Random Number Generation and Quasi-Monte Carlo Methods, SIAM, Philadelphia, 1992. MR 93h:65008
  • 14. H. Niederreiter and C. Xing, Low-discrepancy sequences and global function fields with many rational places, Finite Field Appl., 2 (1996), 241-273. MR 97h:11080
  • 15. E. Novak and H. Wozniakowski, Intractability results for integration and discrepancy, J. Complexity, 17 (2001), 388-441.
  • 16. S. H. Paskov and J. F. Traub, Faster valuation of financial derivatives, J. Portfolio Management, 22 (1995), 113-120.
  • 17. I. H. Sloan and H. Wozniakowski, When are quasi-Monte Carlo algorithms efficient for high dimensional integrals? J. Complexity, 14 (1998), 1-33. MR 99d:65384
  • 18. I. H. Sloan and H. Wozniakowski, Tractability of multivariate integration for weighted Korobov classes, J. Complexity, 17 (2001), 697-721.
  • 19. I. M. Sobol, The distribution of points in a cube and the approximate evaluation of integrals, Zh. Vychisl. Mat. i Mat. Fiz., 7 (1967), 784-802. (Russian) MR 36:2321
  • 20. I. M. Sobol, Multidimensional Quadrature Formulas and Haar Functions, Izdat. Nauka, Moscow, 1969 (Russian). MR 54:10592
  • 21. J. F. Traub and A. G. Werschulz, Complexity and Information, Cambridge University Press, 1998. MR 2000m:65170
  • 22. G. W. Wasilkowski and H. Wozniakowski, Weighted tensor product algorithms for linear multivariate problems, J. Complexity, 15 (1999), 402-447. MR 2000h:65200
  • 23. H. Wozniakowski, Tractability and strong tractability of linear multivariate problems, J. Complexity, 10 (1994), 96-128. MR 95d:65117
  • 24. H. Wozniakowski, Efficiency of quasi-Monte Carlo algorithms for high dimensional integrals, in Monte Carlo and Quasi Monte Carlo Methods 1998 (H. Niederreiter and J. Spanier, eds.), Springer-Verlag, Berlin, 1999, 114-136.

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

American Mathematical Society