Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

 
 

 

The construction of good extensible rank-1 lattices


Authors: Josef Dick, Friedrich Pillichshammer and Benjamin J. Waterhouse
Journal: Math. Comp. 77 (2008), 2345-2373
MSC (2000): Primary 11K45, 65C05, 65D30
DOI: https://doi.org/10.1090/S0025-5718-08-02009-7
Published electronically: May 1, 2008
MathSciNet review: 2429889
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • 1. N. Aronszajn, Theory of reproducing kernels. Trans. Amer. Math. Soc., 68 (1950), 337-404. MR 0051437 (14:479c)
  • 2. R. Cools, F.Y. Kuo and D. Nuyens, Constructing embedded lattice rules for multivariate integration. SIAM J. Sci., 28 (2006), 2162-2188. Comput. MR 2272256 (2007m:68324)
  • 3. J. Dick, On the convergence rate of the component-by-component construction of good lattice rules. J. Complexity, 20 (2004), 493-522. MR 2068155 (2005h:65035)
  • 4. J. Dick, The construction of extensible polynomial lattice rules with small weighted star discrepancy. Math. Comp., 76 (2007), 2077-2085. MR 2336283
  • 5. J. Dick, I.H. Sloan, X. Wang and H. Woźniakowski, Liberating the weights. J. Complexity, 20 (2004), 593-623. MR 2086942 (2005h:65008)
  • 6. J. Dick, I.H. Sloan, X. Wang and H. Woźniakowski, Good lattice rules in weighted Korobov spaces with general weights. Numerische Mathematik, 103 (2006), 63-97. MR 2207615 (2006m:65014)
  • 7. J. Dick and X. Wang, A hybrid construction method for good lattice rules in weighted Korobov spaces. Preprint.
  • 8. G.H. Hardy and E.M. Wright, An Introduction to the Theory of Numbers, 5th Ed., Clarendon Press, Oxford, 1979. MR 568909 (81i:10002)
  • 9. F.J. Hickernell, A generalized discrepancy and quadrature error bound. Math. Comp., 67 (1998), 299-322. MR 1433265 (98c:65032)
  • 10. F.J. Hickernell, My dream quadrature rule. J. Complexity, 19 (2003), 420-427. MR 1984124 (2004e:41034)
  • 11. F.J. Hickernell and H.S. Hong, Computing multivariate normal probabilities using rank-$ 1$ lattice sequences. Scientific computing (Hong Kong, 1997), pp. 209-215, Springer, Singapore, 1997. MR 1729661
  • 12. F.J. Hickernell, H.S. Hong, P. L'Ecuyer and C. Lemieux, Extensible lattice sequences for quasi-Monte Carlo quadrature. SIAM J. Sci. Comput., 22 (2000), 1117-1138. MR 1785348 (2001h:65032)
  • 13. F.J. Hickernell and H. Niederreiter, The existence of good extensible rank-1 lattices. J. Complexity, 19 (2003), 286-300. MR 1984115 (2004c:65015)
  • 14. F.J. Hickernell and H. Woźniakowski, Tractability of multivariate integration for periodic functions. J. Complexity, 17 (2001), 660-682. MR 1881663 (2003g:65028)
  • 15. S. Joe, Construction of good rank-1 lattice rules based on the weighted star discrepancy. In: Monte Carlo and Quasi-Monte Carlo Methods 2004. (Niederreiter H. and Talay D., eds.), pp. 181-196, Springer, Berlin, Heidelberg, New York, 2006. MR 2208709 (2006m:65048)
  • 16. 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), 301-320. MR 1984116 (2004c:41066)
  • 17. F.Y. Kuo and S. Joe, Component-by-component construction of good lattice rules with composite number of points. J. Complexity, 18 (2002), 943-976. MR 1933697 (2003j:65016)
  • 18. G. Larcher, On the distribution of an analog to classical Kronecker-sequences. J. Number Theory, 52 (1995), 198-215. MR 1336745 (96g:11098)
  • 19. G. Larcher and H. Niederreiter, Generalized $ (t,s)$-sequences, Kronecker-type sequences, and Diophantine approximations of formal Laurent series. Trans. Amer. Math. Soc., 347 (1995), 2051-2073. MR 1290724 (95i:11086)
  • 20. H. Niederreiter, Quasi-Monte Carlo methods and pseudo-random numbers. Bull. Amer. Math. Soc., 84 (1978), 957-1041. MR 508447 (80d:65016)
  • 21. H. Niederreiter, Random Number Generation and Quasi-Monte Carlo Methods, CBMS-NSF Series in Applied Mathematics 63, SIAM, Philadelphia, 1992. MR 1172997 (93h:65008)
  • 22. H. Niederreiter, The existence of good extensible polynomial lattice rules. Monatsh. Math., 139 (2003), 295-307. MR 2001711 (2004j:11087)
  • 23. H. Niederreiter, Constructions of $ (t,m,s)$-nets and $ (t,s)$-sequences. Finite Fields and their Applications, 11 (2005), 578-600. MR 2158777 (2006c:11090)
  • 24. D. Nuyens and R. Cools, Fast algorithms for component-by-component construction of rank-1 lattice rules in shift-invariant reproducing kernel Hilbert spaces. Math. Comp., 75 (2006), 903-920. MR 2196999 (2007a:65032)
  • 25. D. Nuyens and R. Cools, Fast construction of rank-1 lattice rules with a non-prime number of points. J. Complexity, 22 (2006), 4-28. MR 2198499 (2006k:65063)
  • 26. I.F. Sharygin, A lower estimate for the error of quadrature formulas for certain classes of functions. Zh. Vychisl. Mat. i Mat. Fiz., 3 (1963), 370-376. MR 0150952 (27:938)
  • 27. 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.
  • 28. I.H. Sloan, S. Joe, Lattice Methods for Multiple Integration, Oxford University Press, Oxford, 1994. MR 1442955 (98a:65026)
  • 29. 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)
  • 30. I.H. Sloan and H. Woźniakowski, When are quasi-Monte Carlo algorithms efficient for high-dimensional integrals? J. Complexity, 14 (1998), 1-33. MR 1617765 (99d:65384)
  • 31. X. Wang, I.H. Sloan and J. Dick, On Korobov lattice rules in weighted spaces. SIAM J. Numer. Anal., 42 (2004), 1760-1779. MR 2114300 (2005j:65006)

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 and Statistics, University of New South Wales, Sydney 2052, Australia
Email: josi@maths.unsw.edu.au

Friedrich Pillichshammer
Affiliation: Institut für Finanzmathematik, Universität Linz, Altenbergstraße 69, A-4040 Linz, Austria
Email: friedrich.pillichshammer@jku.at

Benjamin J. Waterhouse
Affiliation: School of Mathematics and Statistics, University of New South Wales, Sydney 2052, Australia
Email: benjw@maths.unsw.edu.au

DOI: https://doi.org/10.1090/S0025-5718-08-02009-7
Keywords: Quasi-Monte Carlo, numerical integration, extensible lattice rule, component-by-component construction
Received by editor(s): June 13, 2006
Received by editor(s) in revised form: December 8, 2006
Published electronically: May 1, 2008
Additional Notes: This work was supported by the Austrian Research Foundation (FWF), Project S 9609, that is part of the Austrian Research Network “Analytic Combinatorics and Probabilistic Number Theory”.
The support of the Australian Research Council under its Centre of Excellence program is gratefully acknowledged.
Article copyright: © Copyright 2008 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society