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

Dick, Josef

doi:10.1090/S0025-5718-07-01984-9

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