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