On strong tractability of weighted multivariate integration
Fred J. Hickernell, Ian H. Sloan and Grzegorz W. Wasilkowski
Math. Comp. 73 (2004), 1903-1911
Primary 65D30, 65D32, 65Y20, 11K38
April 22, 2004
Full-text PDF Free Access
Similar Articles |
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 .
Drmota and Robert
F. Tichy, Sequences, discrepancies and applications, Lecture
Notes in Mathematics, vol. 1651, Springer-Verlag, Berlin, 1997. MR 1470456
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
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).
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.
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
Novak, Deterministic and stochastic error bounds in numerical
analysis, Lecture Notes in Mathematics, vol. 1349,
Springer-Verlag, Berlin, 1988. MR 971255
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
Pollard, Convergence of stochastic processes, Springer Series
in Statistics, Springer-Verlag, New York, 1984. MR 762984
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
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
- M.Drmota and R.F.Tichy, Sequences, Discrepancies and Applications, Lecture Notes in Math. 1651, Springer, Berlin, 1997. MR 98j:11057
- 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
- 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).
- 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.
- H.Niederreiter, Random Number Generation and quasi-Monte Carlo Methods, SIAM, Philadelphia, 1992. MR 93h:65008
- E.Novak, Deterministic and Stochastic Error Bounds in Numerical Analysis, Lecture Notes in Mathematics 1349, Springer, 1988. MR 90a:65004
- E.Novak and H.Wozniakowski, Intractability results for integration and discrepancy, J. of Complexity 17, pp.388-441, 2001. MR 2002f:65204
- D.Pollard, Convergence of Stochastic Processes, Springer-Verlag, Berlin, 1984. MR 86i:60074
- 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
- 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):
Retrieve articles in all journals
with MSC (2000):
Fred J. Hickernell
Department of Mathematics, Hong Kong Baptist University, Kowloon Tong, Hong Kong
Ian H. Sloan
School of Mathematics, University of New South Wales, Sydney 2052, Australia
Grzegorz W. Wasilkowski
Department of Computer Science, University of Kentucky, 773 Anderson Hall, Lexington, Kentucky 40506-0046
quasi--Monte Carlo methods,
low discrepancy points,
Received by editor(s):
December 16, 2002
Received by editor(s) in revised form:
April 30, 2003
April 22, 2004
© Copyright 2004 American Mathematical Society