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

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. M.Drmota and R.F.Tichy, Sequences, Discrepancies and Applications, Lecture Notes in Math. 1651, Springer, Berlin, 1997. MR 98j:11057
  • 2. S.Heinrich, E.Novak, G.W.Wasilkowski, and H.Wozniakowski, The inverse of the star-discrepancy depends linearly on the dimension, Acta Arithmetica XCVI.3, pp.279-302, 2001. MR 2002b:11103
  • 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. H.Niederreiter, Random Number Generation and quasi-Monte Carlo Methods, SIAM, Philadelphia, 1992. MR 93h:65008
  • 6. E.Novak, Deterministic and Stochastic Error Bounds in Numerical Analysis, Lecture Notes in Mathematics 1349, Springer, 1988. MR 90a:65004
  • 7. E.Novak and H.Wozniakowski, Intractability results for integration and discrepancy, J. of Complexity 17, pp.388-441, 2001. MR 2002f:65204
  • 8. D.Pollard, Convergence of Stochastic Processes, Springer-Verlag, Berlin, 1984. MR 86i:60074
  • 9. I.H.Sloan and H.Wozniakowski, When are quasi-Monte Carlo algorithms efficient for high dimensional integrals?, J. of Complexity 14, pp.1-33, 1998. MR 99d:65384
  • 10. J.F.Traub, G.W.Wasilkowski, and H.Wozniakowski, Information-Based Complexity, Academic Press, New York, 1988. MR 90f:68085

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

American Mathematical Society