Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



On strong tractability of weighted multivariate integration

Authors: Fred J. Hickernell, Ian H. Sloan and Grzegorz W. Wasilkowski
Journal: Math. Comp. 73 (2004), 1903-1911
MSC (2000): Primary 65D30, 65D32, 65Y20, 11K38
Published electronically: April 22, 2004
MathSciNet review: 2059742
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We prove that for every dimension $s$ and every number $n$ of points, there exists a point-set $\mathcal{P}_{n,s}$ whose $\boldsymbol \gamma$-weighted unanchored $L_{\infty}$ discrepancy is bounded from above by $C(b)/n^{1/2-b}$ independently of $s$ provided that the sequence $\boldsymbol\gamma=\{\gamma_k\}$ has $\sum_{k=1}^\infty\gamma_k^a<\infty$ for some (even arbitrarily large) $a$. Here $b$ is a positive number that could be chosen arbitrarily close to zero and $C(b)$ depends on $b$ but not on $s$ or $n$. This result yields strong tractability of the corresponding integration problems including approximation of weighted integrals $\int_Df(\mathbf{x})\,\rho(\mathbf{x})\,d\mathbf{x}$over unbounded domains such as $D=\mathbb{R}^s$. It also supplements the results that provide an upper bound of the form $C\sqrt{s/n}$ when $\gamma_k\equiv1$.

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

  • 1. Michael Drmota and Robert F. Tichy, Sequences, discrepancies and applications, Lecture Notes in Mathematics, vol. 1651, Springer-Verlag, Berlin, 1997. MR 1470456
  • 2. Stefan Heinrich, Erich Novak, Grzegorz W. Wasilkowski, and Henryk Woźniakowski, The inverse of the star-discrepancy depends linearly on the dimension, Acta Arith. 96 (2001), no. 3, 279–302. MR 1814282, 10.4064/aa96-3-7
  • 3. F.J.Hickernell, I.H.Sloan, and G.W.Wasilkowski, On tractability of weighted integration over bounded and unbounded regions in $\mathbb{R}^s$, Math. Comp., posted on January 5, 2004, PII S 0025-5718(04)01624-2 (to appear in print).
  • 4. F.J.Hickernell, I.H.Sloan, and G.W.Wasilkowski, On tractability of integration for certain Banach spaces of functions, ``Monte Carlo and Quasi-Monte Carlo Methods 2002'' (H. Niederreiter, ed.), Springer, 2004, pp. 51-71.
  • 5. Harald Niederreiter, Random number generation and quasi-Monte Carlo methods, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 63, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1992. MR 1172997
  • 6. Erich Novak, Deterministic and stochastic error bounds in numerical analysis, Lecture Notes in Mathematics, vol. 1349, Springer-Verlag, Berlin, 1988. MR 971255
  • 7. Erich Novak and H. Woźniakowski, Intractability results for integration and discrepancy, J. Complexity 17 (2001), no. 2, 388–441. 3rd Conference of the Foundations of Computational Mathematics (Oxford, 1999). MR 1843427, 10.1006/jcom.2000.0577
  • 8. David Pollard, Convergence of stochastic processes, Springer Series in Statistics, Springer-Verlag, New York, 1984. MR 762984
  • 9. Ian H. Sloan and Henryk Woźniakowski, When are quasi-Monte Carlo algorithms efficient for high-dimensional integrals?, J. Complexity 14 (1998), no. 1, 1–33. MR 1617765, 10.1006/jcom.1997.0463
  • 10. J. F. Traub, G. W. Wasilkowski, and H. Woźniakowski, Information-based complexity, Computer Science and Scientific Computing, Academic Press, Inc., Boston, MA, 1988. With contributions by A. G. Werschulz and T. Boult. MR 958691

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 65D30, 65D32, 65Y20, 11K38

Retrieve articles in all journals with MSC (2000): 65D30, 65D32, 65Y20, 11K38

Additional Information

Fred J. Hickernell
Affiliation: Department of Mathematics, Hong Kong Baptist University, Kowloon Tong, Hong Kong

Ian H. Sloan
Affiliation: School of Mathematics, University of New South Wales, Sydney 2052, Australia

Grzegorz W. Wasilkowski
Affiliation: Department of Computer Science, University of Kentucky, 773 Anderson Hall, Lexington, Kentucky 40506-0046

Keywords: Weighted integration, quasi--Monte Carlo methods, low discrepancy points, tractability
Received by editor(s): December 16, 2002
Received by editor(s) in revised form: April 30, 2003
Published electronically: April 22, 2004
Article copyright: © Copyright 2004 American Mathematical Society