Mathematics of Computation

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

Author(s): Josef Dick.
Journal: Math. Comp. 76 (2007), 2077-2085.
MSC (2000): Primary 11K45, 65C05, 65D30
Posted: May 9, 2007
Retrieve article in: PDF DVI PostScript

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.

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)

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

			Journals Home Search Author Info Subscribe Tech Support Help
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


	Comments: webmaster@ams.org © Copyright 2008, American Mathematical Society Privacy Statement		Search the AMS