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

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

Published electronically:
April 22, 2004

MathSciNet review:
2059742

Full-text PDF

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

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:
https://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