The construction of extensible polynomial lattice rules with small weighted star discrepancy
HTML articles powered by AMS MathViewer
- by Josef Dick PDF
- Math. Comp. 76 (2007), 2077-2085 Request permission
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
- Ronald Cools, Frances Y. Kuo, and Dirk Nuyens, Constructing embedded lattice rules for multivariable integration, SIAM J. Sci. Comput. 28 (2006), no. 6, 2162–2188. MR 2272256, DOI 10.1137/06065074X
- 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.
- J. Dick, F. Y. Kuo, F. Pillichshammer, and I. H. Sloan, Construction algorithms for polynomial lattice rules for multivariate integration, Math. Comp. 74 (2005), no. 252, 1895–1921. MR 2164102, DOI 10.1090/S0025-5718-05-01742-4
- Josef Dick, Gunther Leobacher, and Friedrich Pillichshammer, Construction algorithms for digital nets with low weighted star discrepancy, SIAM J. Numer. Anal. 43 (2005), no. 1, 76–95. MR 2177135, DOI 10.1137/040604662
- J. Dick, F. Pillichshammer and B.J. Waterhouse, A Sieve Algorithm for the construction of extensible lattice rules. To appear in Math. Comp. (2007).
- Fred J. Hickernell and Hee Sun Hong, Computing multivariate normal probabilities using rank-$1$ lattice sequences, Scientific computing (Hong Kong, 1997) Springer, Singapore, 1997, pp. 209–215. MR 1729661
- Fred J. Hickernell, Hee Sun Hong, Pierre L’Écuyer, and Christiane Lemieux, Extensible lattice sequences for quasi-Monte Carlo quadrature, SIAM J. Sci. Comput. 22 (2000), no. 3, 1117–1138. MR 1785348, DOI 10.1137/S1064827599356638
- Fred J. Hickernell and Harald Niederreiter, The existence of good extensible rank-1 lattices, J. Complexity 19 (2003), no. 3, 286–300. Numerical integration and its complexity (Oberwolfach, 2001). MR 1984115, DOI 10.1016/S0885-064X(02)00026-2
- Stephen 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, Springer, Berlin, 2004, pp. 293–298. MR 2076940
- Pierre L’Ecuyer, Polynomial integration lattices, Monte Carlo and quasi-Monte Carlo methods 2002, Springer, Berlin, 2004, pp. 73–98. MR 2076607
- Pierre L’Ecuyer and Christiane Lemieux, Recent advances in randomized quasi-Monte Carlo methods, Modeling uncertainty, Internat. Ser. Oper. Res. Management Sci., vol. 46, Kluwer Acad. Publ., Boston, MA, 2002, pp. 419–474. MR 1893290, DOI 10.1007/0-306-48102-2_{2}0
- Harald Niederreiter, Low-discrepancy point sets obtained by digital constructions over finite fields, Czechoslovak Math. J. 42(117) (1992), no. 1, 143–166. MR 1152177
- 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, DOI 10.1137/1.9781611970081
- Harald Niederreiter, The existence of good extensible polynomial lattice rules, Monatsh. Math. 139 (2003), no. 4, 295–307. MR 2001711, DOI 10.1007/s00605-002-0530-z
- I. H. Sloan and S. Joe, Lattice methods for multiple integration, Oxford Science Publications, The Clarendon Press, Oxford University Press, New York, 1994. MR 1442955
- I. H. Sloan, F. Y. Kuo, and S. Joe, Constructing randomly shifted lattice rules in weighted Sobolev spaces, SIAM J. Numer. Anal. 40 (2002), no. 5, 1650–1665. MR 1950616, DOI 10.1137/S0036142901393942
- I. H. Sloan and A. V. Reztsov, Component-by-component construction of good lattice rules, Math. Comp. 71 (2002), no. 237, 263–273. MR 1862999, DOI 10.1090/S0025-5718-01-01342-4
- 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, DOI 10.1006/jcom.1997.0463
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
- Email: j.dick@unswasia.edu.sg
- Received by editor(s): April 19, 2006
- Received by editor(s) in revised form: September 13, 2006
- Published electronically: May 9, 2007
- © Copyright 2007
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - Journal: Math. Comp. 76 (2007), 2077-2085
- MSC (2000): Primary 11K45, 65C05, 65D30
- DOI: https://doi.org/10.1090/S0025-5718-07-01984-9
- MathSciNet review: 2336283