The construction of good extensible rank-1 lattices

Dick, Josef; Pillichshammer, Friedrich; Waterhouse, Benjamin

doi:10.1090/S0025-5718-08-02009-7

The construction of good extensible rank-1 lattices
HTML articles powered by AMS MathViewer

by Josef Dick, Friedrich Pillichshammer and Benjamin J. Waterhouse PDF

Math. Comp. 77 (2008), 2345-2373 Request permission

Abstract:

It has been shown by Hickernell and Niederreiter that there exist generating vectors for integration lattices which yield small integration errors for $n = p, p^2, \ldots$ for all integers $p \ge 2$. This paper provides algorithms for the construction of generating vectors which are finitely extensible for $n = p, p^2, \ldots$ for all integers $p \ge 2$. The proofs which show that our algorithms yield good extensible rank-1 lattices are based on a sieve principle. Particularly fast algorithms are obtained by using the fast component-by-component construction of Nuyens and Cools. Analogous results are presented for generating vectors with small weighted star discrepancy.

References

N. Aronszajn, Theory of reproducing kernels, Trans. Amer. Math. Soc. 68 (1950), 337–404. MR 51437, DOI 10.1090/S0002-9947-1950-0051437-7
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
Josef Dick, On the convergence rate of the component-by-component construction of good lattice rules, J. Complexity 20 (2004), no. 4, 493–522. MR 2068155, DOI 10.1016/j.jco.2003.11.008
Josef Dick, The construction of extensible polynomial lattice rules with small weighted star discrepancy, Math. Comp. 76 (2007), no. 260, 2077–2085. MR 2336283, DOI 10.1090/S0025-5718-07-01984-9
Josef Dick, Ian H. Sloan, Xiaoqun Wang, and Henryk Woźniakowski, Liberating the weights, J. Complexity 20 (2004), no. 5, 593–623. MR 2086942, DOI 10.1016/j.jco.2003.06.002
Josef Dick, Ian H. Sloan, Xiaoqun Wang, and Henryk Woźniakowski, Good lattice rules in weighted Korobov spaces with general weights, Numer. Math. 103 (2006), no. 1, 63–97. MR 2207615, DOI 10.1007/s00211-005-0674-6
J. Dick and X. Wang, A hybrid construction method for good lattice rules in weighted Korobov spaces. Preprint.
G. H. Hardy and E. M. Wright, An introduction to the theory of numbers, 5th ed., The Clarendon Press, Oxford University Press, New York, 1979. MR 568909
Fred J. Hickernell, A generalized discrepancy and quadrature error bound, Math. Comp. 67 (1998), no. 221, 299–322. MR 1433265, DOI 10.1090/S0025-5718-98-00894-1
Fred J. Hickernell, My dream quadrature rule, J. Complexity 19 (2003), no. 3, 420–427. Numerical integration and its complexity (Oberwolfach, 2001). MR 1984124, DOI 10.1016/S0885-064X(02)00024-9
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
Fred J. Hickernell and Henryk Woźniakowski, Tractability of multivariate integration for periodic functions, J. Complexity 17 (2001), no. 4, 660–682. Complexity of multivariate problems (Kowloon, 1999). MR 1881663, DOI 10.1006/jcom.2001.0592
Stephen Joe, Construction of good rank-1 lattice rules based on the weighted star discrepancy, Monte Carlo and quasi-Monte Carlo methods 2004, Springer, Berlin, 2006, pp. 181–196. MR 2208709, DOI 10.1007/3-540-31186-6_{1}2
F. Y. Kuo, Component-by-component constructions achieve the optimal rate of convergence for multivariate integration in weighted Korobov and Sobolev spaces, J. Complexity 19 (2003), no. 3, 301–320. Numerical integration and its complexity (Oberwolfach, 2001). MR 1984116, DOI 10.1016/S0885-064X(03)00006-2
Frances Y. Kuo and Stephen Joe, Component-by-component construction of good lattice rules with a composite number of points, J. Complexity 18 (2002), no. 4, 943–976. MR 1933697, DOI 10.1006/jcom.2002.0650
Gerhard Larcher, On the distribution of an analog to classical Kronecker-sequences, J. Number Theory 52 (1995), no. 2, 198–215. MR 1336745, DOI 10.1006/jnth.1995.1065
Gerhard Larcher and Harald Niederreiter, Generalized $(t,s)$-sequences, Kronecker-type sequences, and Diophantine approximations of formal Laurent series, Trans. Amer. Math. Soc. 347 (1995), no. 6, 2051–2073. MR 1290724, DOI 10.1090/S0002-9947-1995-1290724-1
Harald Niederreiter, Quasi-Monte Carlo methods and pseudo-random numbers, Bull. Amer. Math. Soc. 84 (1978), no. 6, 957–1041. MR 508447, DOI 10.1090/S0002-9904-1978-14532-7
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
Harald Niederreiter, Constructions of $(t,m,s)$-nets and $(t,s)$-sequences, Finite Fields Appl. 11 (2005), no. 3, 578–600. MR 2158777, DOI 10.1016/j.ffa.2005.01.001
Dirk Nuyens and Ronald Cools, Fast algorithms for component-by-component construction of rank-1 lattice rules in shift-invariant reproducing kernel Hilbert spaces, Math. Comp. 75 (2006), no. 254, 903–920. MR 2196999, DOI 10.1090/S0025-5718-06-01785-6
Dirk Nuyens and Ronald Cools, Fast component-by-component construction of rank-1 lattice rules with a non-prime number of points, J. Complexity 22 (2006), no. 1, 4–28. MR 2198499, DOI 10.1016/j.jco.2005.07.002
I. F. Šarygin, Lower bounds for the error of quadrature formulas on classes of functions, Ž. Vyčisl. Mat i Mat. Fiz. 3 (1963), 370–376 (Russian). MR 150952
V. Sinescu and S. Joe, Good lattice rules with a composite number of points based on the product weighted star discrepancy. In Monte Carlo and Quasi-Monte Carlo Methods 2006 (A. Keller, S. Heinrich and H. Niederreiter, eds.), Springer-Verlag, Berlin, Heidelberg, pp. 645–658.
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
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
Xiaoqun Wang, Ian H. Sloan, and Josef Dick, On Korobov lattice rules in weighted spaces, SIAM J. Numer. Anal. 42 (2004), no. 4, 1760–1779. MR 2114300, DOI 10.1137/S0036142903425021