Available in electronic format
Available in print format		 Mathematics of Computation
Journal of the American Mathematical Society
ISSN 1088-6842(e) ISSN 0025-5718(p)
Previous issue | Table of contents | Next issue
Articles in press | Recently posted articles | Most recent issue | All issues
Previous Article | Next Article
     

Good lattice rules based on the general weighted star discrepancy

Author(s): Vasile Sinescu; Stephen Joe.
Journal: Math. Comp. 76 (2007), 989-1004.
MSC (2000): Primary 65D30, 65D32; Secondary 11K38
Posted: December 12, 2006
Retrieve article in: PDF

Abstract | References | Similar articles | Additional information

Abstract: We study the problem of constructing rank-$ 1$ lattice rules which have good bounds on the ``weighted star discrepancy''. Here the non-negative weights are general weights rather than the product weights considered in most earlier works. In order to show the existence of such good lattice rules, we use an averaging argument, and a similar argument is used later to prove that these lattice rules may be obtained using a component-by-component (CBC) construction of the generating vector. Under appropriate conditions on the weights, these lattice rules satisfy strong tractability bounds on the weighted star discrepancy. Particular classes of weights known as ``order-dependent'' and ``finite-order'' weights are then considered and we show that the cost of the construction can be very much reduced for these two classes of weights.

References:

1.
R. Cools, F.Y. Kuo and D. Nuyens, Constructing embedded lattice rules for multivariate integration, SIAM J. Sci Comput., to appear.

2.
J. Dick, I.H. Sloan, X. Wang and H. Wozniakowski, Good lattice rules in weighted Korobov spaces with general weights, Numer. Math. 103, pp. 63-97, 2006. MR 2207615 (2006m:65014)

3.
F.J. Hickernell, A generalized discrepancy and quadrature error bound, Math. Comp. 67, pp. 299-322, 1998. MR 1433265 (98c:65032)

4.
F.J. Hickernell and H. Niederreiter, The existence of good extensible rank-$ 1$ lattices, J. Complexity 19, pp. 286-300, 2003. MR 1984115 (2004c:65015)

5.
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. 73, pp. 1885-1901, 2004. MR 2059741 (2005c:65018)

6.
F.J. Hickernell, I.H. Sloan and G.W. Wasilkowski, On strong tractability of weighted multivariate integration, Math. Comp. 73, pp. 1903-1911, 2004. MR 2059742 (2005c:65019)

7.
S. Joe and I.H. Sloan, On computing the lattice rule criterion $ R$, Math. Comp. 59, pp. 557-568, 1992. MR 1134733 (93b:65042)

8.
S. Joe, Component by component construction of rank-$ 1$ lattice rules having $ O(n^{-1}(\ln\,n)^d)$ star discrepancy, Monte Carlo and quasi-Monte Carlo methods 2002 (H. Niederreiter, ed.), pp. 293-298, Springer, 2004. MR 2076940

9.
S. Joe, Construction of good rank-$ 1$ lattice rules based on the weighted star discrepancy, Monte Carlo and quasi-Monte Carlo Methods 2004 (H. Niederreiter, D. Talay, eds), pp. 181-196, Springer, 2006. MR 2208709 (2006m:65048)

10.
G. Larcher, A best lower bound for good lattice points, Monatsh. Math. 104, pp. 45-51, 1987. MR 0903774 (89f:11103)

11.
D. Nuyens and R. Cools, Fast algorithms for component-by-component construction of rank-$ 1$ lattice rules in shift-invariant reproducing kernel Hilbert spaces, Math. Comp. 75, pp. 903-920, 2006. MR 2196999

12.
H. Niederreiter, Existence of good lattice points in the sense of Hlawka, Monatsh. Math. 86, pp. 203-219, 1978. MR 0517026 (80e:10039)

13.
H. Niederreiter, Random number generation and quasi-Monte Carlo methods, SIAM, Philadelphia, 1992. MR 1172997 (93h:65008)

14.
I.H. Sloan and S. Joe, Lattice methods for multiple integration, Clarendon Press, Oxford, 1994. MR 1442955 (98a:65026)

15.
I.H. Sloan, X. Wang and H. Wozniakowski, Finite-order weights imply tractability of multivariate integration, J. Complexity 20, pp. 46-74, 2004. MR 2031558 (2004j:65034)

16.
I.H. Sloan and H. Wozniakowski, When are quasi-Monte Carlo algorithms efficient for high dimensional integrals?, J. Complexity 14, pp. 1-33, 1998. MR 1617765 (99d:65384)

17.
X. Wang and I.H. Sloan, Why are high-dimensional finance problems often of low effective dimension?, SIAM J. Sci. Comput. 27, pp. 159-183, 2005 MR 2201179 (2006j:91171).

18.
S.K. Zaremba, Some applications of multidimensional integration by parts, Ann. Polon. Math. 21, pp. 85-96, 1968. MR 0235731 (38:4034)

Similar Articles:

Retrieve articles in Mathematics of Computation with MSC (2000): 65D30, 65D32, 11K38

Retrieve articles in all Journals with MSC (2000): 65D30, 65D32, 11K38

Additional Information:

Vasile Sinescu
Affiliation: Department of Mathematics, University of Waikato, Hamilton, New Zealand
Email: vs27@waikato.ac.nz

Stephen Joe
Affiliation: Department of Mathematics, University of Waikato, Hamilton, New Zealand
Email: stephenj@math.waikato.ac.nz

DOI: 10.1090/S0025-5718-06-01943-0
PII: S 0025-5718(06)01943-0
Keywords: Rank-$1$ lattice rules, weighted star discrepancy, component-by-component construction
Received by editor(s): August 23, 2005
Received by editor(s) in revised form: April 20, 2006
Posted: December 12, 2006
Copyright of article: Copyright 2006, American Mathematical Society
The copyright for this article reverts to public domain after 28 years from publication.

  AMS Website Logo Small Comments: webmaster@ams.org
© Copyright 2009, American Mathematical Society
Privacy Statement 		Search the AMSPowered by Google