Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
|
   
Mobile Device Pairing
Mathematics of Computation
Mathematics of Computation
ISSN 1088-6842(e) ISSN 0025-5718(p)

     

On strong tractability of weighted multivariate integration

Author(s): Fred J. Hickernell; Ian H. Sloan; Grzegorz W. Wasilkowski.
Journal: Math. Comp. 73 (2004), 1903-1911.
MSC (2000): Primary 65D30, 65D32, 65Y20, 11K38
Posted: April 22, 2004
MathSciNet review: 2059742
Retrieve article in: PDF
This article is available free of charge

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:

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
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: 10.1090/S0025-5718-04-01653-9
PII: S 0025-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
Posted: April 22, 2004
Copyright of article: Copyright 2004, American Mathematical Society




AMS and Social Media LinkedIn Facebook Podcasts Twitter YouTube RSS Feeds Blogs Wikipedia