Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



The construction of extensible polynomial lattice rules with small weighted star discrepancy

Author: Josef Dick
Journal: Math. Comp. 76 (2007), 2077-2085
MSC (2000): Primary 11K45, 65C05, 65D30
Published electronically: May 9, 2007
MathSciNet review: 2336283
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: In this paper we introduce a construction algorithm for extensible polynomial lattice rules and we prove that the construction algorithm yields generating vectors of polynomials which are optimal for a range of moduli chosen in advance. The construction algorithm uses a sieve where the generating vectors are extended by one coefficient in each component at each step and where one keeps a certain number of good ones and discards the rest. We also show that the construction can be done component by component.

References [Enhancements On Off] (What's this?)

  • 1. R. Cools, F.Y. Kuo and D. Nuyens, Constructing embedded lattice rules for multivariate integration. SIAM J. Sci. Comp., 28 (2006), 2162-2188. MR 2272256
  • 2. J. Dick, P. Kritzer, G. Leobacher and F. Pillichshammer, Constructions of general polynomial lattice rules based on the weighted star discrepancy. To appear in Finite Fields and their Appl., 2007.
  • 3. J. Dick, F.Y. Kuo, F. Pillichshammer and I.H. Sloan, Construction algorithms for polynomial lattice rules for multivariate integration. Math. Comp., 74 (2005), 1895-1921. MR 2164102 (2006e:65049)
  • 4. J. Dick, G. Leobacher and F. Pillichshammer, Construction algorithms for digital nets with small weighted star discrepancy. SIAM J. Num. Anal., 43 (2005), 76-95. MR 2177135 (2006h:11090)
  • 5. J. Dick, F. Pillichshammer and B.J. Waterhouse, A Sieve Algorithm for the construction of extensible lattice rules. To appear in Math. Comp. (2007).
  • 6. F.J. Hickernell and H.S. Hong, Computing multivariate normal probabilities using rank-1 lattice sequences. In: Proceedings of the Workshop on Scientific Computing, Hong Kong, G. H. Golub, S. H. Lui, F. T. Luk, and R. J. Plemmons (Eds.), Springer, Singapore, 1997, 209-215. MR 1729661
  • 7. F.J. Hickernell, H.S. Hong, P. L'Écuyer and C. Lemieux, Extensible lattice sequences for quasi-Monte Carlo quadrature. SIAM J. Sci. Comput., 22 (2000), 1117-1138. MR 1785348 (2001h:65032)
  • 8. F.J. Hickernell and H. Niederreiter, The existence of good extensible rank-1 lattices. J. Complexity, 19 (2003), 286-300. MR 1984115 (2004c:65015)
  • 9. S. Joe, Component by component construction of rank-1 lattice rules having $ O(n\sp {-1}(\ln(n))\sp d)$ star discrepancy. In: Monte Carlo and quasi-Monte Carlo methods 2002, H. Niederreiter (Ed.), Springer, Berlin, 2004, 293-298. MR 2076940
  • 10. P. L'Ecuyer, Polynomial integration lattices. In: Monte Carlo and Quasi-Monte Carlo Methods 2002, H. Niederreiter (Ed.), Springer, Berlin, 2004, 73-98. MR 2076607
  • 11. P. L'Ecuyer and C. Lemieux, Recent advances in randomized quasi-Monte Carlo methods. In: Modeling Uncertainty: An Examination of Stochastic Theory, Methods and Applications, M. Dror, P. L'Ecuyer and F. Szidarovszky (Eds.), Kluwer, Boston, 2002, 419-474. MR 1893290
  • 12. H. Niederreiter, Low-discrepancy point sets obtained by digital constructions over finite fields. Czechoslovak Math. J., 42 (1992), 143-166. MR 1152177 (93c:11055)
  • 13. H. Niederreiter, Random Number Generation and Quasi-Monte Carlo Methods. CBMS-NSF Series in Applied Mathematics 63, SIAM, Philadelphia, 1992. MR 1172997 (93h:65008)
  • 14. H. Niederreiter, The existence of good extensible polynomial lattice rules. Monatsh. Math., 139 (2003), 295-307. MR 2001711 (2004j:11087)
  • 15. I.H. Sloan and S. Joe, Lattice Methods for Multiple Integration. Clarendon Press, Oxford, 1994. MR 1442955 (98a:65026)
  • 16. I.H. Sloan, F.Y. Kuo and S. Joe, Constructing randomly shifted lattice rules in weighted Sobolev spaces. SIAM J. Numer. Anal., 40 (2002), 1650-1665. MR 1950616 (2003m:65031)
  • 17. I.H. Sloan and A.V. Reztsov, Component-by-component construction of good lattice rules. Math. Comp., 71 (2002), 263-273. MR 1862999 (2002h:65028)
  • 18. I.H. Sloan and H. Wozniakowski, When are quasi-Monte Carlo algorithms efficient for high dimensional integrals? J. Complexity, 14 (1998), 1-33. MR 1617765 (99d:65384)

Similar Articles

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

Retrieve articles in all journals with MSC (2000): 11K45, 65C05, 65D30

Additional Information

Josef Dick
Affiliation: School of Mathematics, University of New South Wales, Sydney 2052, Australia
Address at time of publication: UNSW Asia, 1 Kay Siang Road, Singapore 248922

Received by editor(s): April 19, 2006
Received by editor(s) in revised form: September 13, 2006
Published electronically: May 9, 2007
Article copyright: © Copyright 2007 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society