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 and every number of points, there exists a point-set whose *-weighted unanchored * * discrepancy* is bounded from above by independently of provided that the sequence has for some (even arbitrarily large) . Here is a positive number that could be chosen arbitrarily close to zero and depends on but not on or . This result yields strong tractability of the corresponding integration problems including approximation of weighted integrals over unbounded domains such as . It also supplements the results that provide an upper bound of the form when .

**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 ,*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**

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

Email:
fred@math.hkbu.edu.hk

**Ian H. Sloan**

Affiliation:
School of Mathematics, University of New South Wales, Sydney 2052, Australia

Email:
sloan@maths.unsw.edu.au

**Grzegorz W. Wasilkowski**

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

Email:
greg@cs.uky.edu

DOI:
http://dx.doi.org/10.1090/S0025-5718-04-01653-9

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