Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



Construction algorithms for polynomial lattice rules for multivariate integration

Authors: J. Dick, F. Y. Kuo, F. Pillichshammer and I. H. Sloan
Journal: Math. Comp. 74 (2005), 1895-1921
MSC (2000): Primary 65C05, 65D30
Published electronically: May 5, 2005
MathSciNet review: 2164102
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We introduce a new construction algorithm for digital nets for integration in certain weighted tensor product Hilbert spaces. The first weighted Hilbert space we consider is based on Walsh functions. Dick and Pillichshammer calculated the worst-case error for integration using digital nets for this space. Here we extend this result to a special construction method for digital nets based on polynomials over finite fields. This result allows us to find polynomials which yield a small worst-case error by computer search. We prove an upper bound on the worst-case error for digital nets obtained by such a search algorithm which shows that the convergence rate is best possible and that strong tractability holds under some condition on the weights.

We extend the results for the weighted Hilbert space based on Walsh functions to weighted Sobolev spaces. In this case we use randomly digitally shifted digital nets. The construction principle is the same as before, only the worst-case error is slightly different. Again digital nets obtained from our search algorithm yield a worst-case error achieving the optimal rate of convergence and as before strong tractability holds under some condition on the weights. These results show that such a construction of digital nets yields the until now best known results of this kind and that our construction methods are comparable to the construction methods known for lattice rules.

We conclude the article with numerical results comparing the expected worst-case error for randomly digitally shifted digital nets with those for randomly shifted lattice rules.

References [Enhancements On Off] (What's this?)

  • 1. Aronszajn, N.: Theory of reproducing kernels. Trans. Amer. Math. Soc., 68: 337-404, 1950.MR 0051437 (14:479c)
  • 2. Chrestenson, H.E.: A class of generalized Walsh functions. Pacific J. Math., 5: 17-31, 1955.MR 0068659 (16:920c)
  • 3. Cranley, R. and Patterson, T.N.L.: Randomization of number theoretic methods for multiple integration. SIAM J. Numer. Anal., 13: 904-914, 1976. MR 0494820 (58:13605)
  • 4. Dick, J.: On the convergence rate of the component-by-component construction of good lattice rules. J. Complexity, 20: 493-522, 2004.MR 2068155
  • 5. Dick, J., Pillichshammer, F.: Multivariate integration in weighted Hilbert spaces based on Walsh functions and weighted Sobolev spaces. J. Complexity, 21: 149-195, 2005.
  • 6. Dick, J., Sloan, I.H., Wang, X., and Wozniakowski, H.: Liberating the weights. J. Complexity, 20: 593-623, 2004.
  • 7. Dick, J., Sloan, I.H., Wang, X. and Wozniakowski, H.: Good lattice rules in weighted Korobov spaces with general weights. Submitted.
  • 8. Faure, H.: Discrépance de suites associées à un système de numération (en dimension $s$). Acta Arith., 41: 337-351, 1982. MR 0677547 (84m:10050)
  • 9. Hickernell, F.J.: Lattice rules: how well do they measure up? In: Random and Quasi-Random Point Sets (P. Hellekalek and G. Larcher, eds.), pp. 109-166, Springer Lecture Notes in Statistics 138, 1998. MR 1662841 (2000b:65007)
  • 10. Korobov, N.M.: The approximate computation of multiple integrals. Dokl. Akad. Nauk SSSR, 124: 1207-1210, 1959. (In Russian) MR 0104086 (21:2848)
  • 11. Korobov, N.M.: Properties and calculation of optimal coefficients. Dokl. Akad. Nauk SSSR 132: 1009-1012, 1960. (In Russian) MR 0120768 (22:11517)
  • 12. Kuo, F.Y.: Component-by-component constructions achieve the optimal rate of convergence for multivariate integration in weighted Korobov and Sobolev spaces. J. Complexity, 19: 301-320, 2003.MR 1984116 (2004c:41066)
  • 13. Larcher, G.: Digital point sets: analysis and application. In: Random and Quasi-Random Point Sets (P. Hellekalek and G. Larcher, eds.), pp. 167-222, Springer Lecture Notes in Statistics 138, 1998.MR 1662842 (99m:11085)
  • 14. Larcher, G., Lauß, A., Niederreiter, H., and Schmid, W.Ch.:Optimal polynomials for $(t,m,s)$-nets and numerical integration of multivariate Walsh series. SIAM J. Numer. Anal., 33: 2239-2253, 1996. MR 1427461 (97m:65046)
  • 15. Larcher, G., Niederreiter, H., and Schmid, W.Ch.: Digital nets and sequences constructed over finite rings and their application to quasi-Monte Carlo integration. Monatsh. Math., 121: 231-253, 1996. MR 1383533 (97d:11119)
  • 16. Lemieux, Ch., L'Ecuyer, P.: Randomized polynomial lattice rules for multivariate integration and simulation, SIAM J. Sci. Comput. 24: 1768-1789, 2003. MR 1978160 (2004e:65009)
  • 17. Lidl, R., Niederreiter, H.: Introduction to Finite Fields and their Applications. Cambridge Univ. Press, Cambridge, 1994. MR 1294139 (95f:11098)
  • 18. Niederdrenk, K.: Die endliche Fourier- und Walshtransformation mit einer Einführung in die Bildverarbeitung. Vieweg, Braunschweig, 1982. MR 0735256 (85g:94001)
  • 19. Niederreiter, H.: Point sets and sequences with small discrepancy. Monatsh. Math., 104: 273-337, 1987. MR 0918037 (89c:11120)
  • 20. Niederreiter, H.: Low-discrepancy point sets obtained by digital constructions over finite fields. Czechoslovak Math. J., 42: 143-166, 1992. MR 1152177 (93c:11055)
  • 21. Niederreiter, H.: Random Number Generation and Quasi-Monte Carlo Methods. No. 63 in CBMS-NSF Series in Applied Mathematics. SIAM, Philadelphia, 1992. MR 1172997 (93h:65008)
  • 22. Niederreiter, H.: Finite fields, pseudorandom numbers, and quasirandom points. In: Finite Fields, Coding Theory, and Advances in Communications and Computing (Mullen, G.L., and Shiue, P.J.-S., eds.), pp. 375-394, Dekker, New York, 1992. MR 1199844 (94a:11121)
  • 23. Niederreiter, H.: Constructions of $(t,m,s)$-nets. In: Monte Carlo and Quasi-Monte Carlo Methods 1998 (Niederreiter, H., and Spanier, J., eds.), pp. 70-85, Springer, Berlin, 2000.MR 1849843 (2002e:65012)
  • 24. Niederreiter, H.: The existence of good extensible polynomial lattice rules. Monatsh. Math., 139: 295-307, 2003. MR 2001711 (2004j:11087)
  • 25. Pirsic, G.: Schnell konvergierende Walshreihen über Gruppen. Master's Thesis, University of Salzburg, 1995. (Available at
  • 26. Pirsic, G., Schmid, W.Ch.: Calculation of the quality parameter of digital nets and application to their construction. J. Complexity 17: 827-839, 2001. MR 1881672 (2002m:65004)
  • 27. Rivlin, T.J., Saff, E.B.: Joseph L. Walsh Selected Papers. Springer Verlag, New York, 2000.MR 1757949 (2001g:01052)
  • 28. Schmid, W.Ch.: Improvements and extensions of the ``Salzburg tables'' by using irreducible polynomials. In: Monte Carlo and quasi-Monte Carlo methods 1998 (Niederreiter, H., et al., eds.), pp. 436-447, Springer, Berlin, 2000. MR 1849869
  • 29. Sloan, I.H. and Joe, S.: Lattice methods for multiple integration. Oxford University Press, Oxford, 1994. MR 1442955 (98a:65026)
  • 30. Sloan, I.H., Kuo, F.Y., and Joe, S.: Constructing randomly shifted lattice rules in weighted Sobolev spaces. SIAM J. Numer. Anal., 40: 1650-1655, 2002. MR 1950616 (2003m:65031)
  • 31. Sloan, I.H., Kuo, F.Y., and Joe, S.: On the step-by-step construction of quasi-Monte Carlo integration rules that achieve strong tractability error bounds in weighted Sobolev spaces. Math. Comp., 71: 1609-1640, 2002. MR 1933047 (2003m:65030)
  • 32. Sloan, I.H. and Wozniakowski, H.: When are quasi-Monte Carlo algorithms efficient for high dimensional integrals? J. Complexity, 14: 1-33, 1998. MR 1617765 (99d:65384)
  • 33. Sloan, I.H., Wozniakowski, H.: Tractability of multivariate integration for weighted Korobov classes. J. Complexity, 17: 697-721, 2001. MR 1881665 (2003g:65030)
  • 34. Sobol$'$, I.M.: On the distribution of points in a cube and the approximate evaluation of integrals. U.S.S.R. Comput. Maths. Math. Phys., 7: 86-112, 1967. MR 0219238 (36:2321)
  • 35. Walsh, J.L.: A closed set of normal orthogonal functions. Amer. J. Math., 55: 5-24, 1923.
  • 36. Wang, X. and Sloan, I.H.: Efficient weighted lattice rules with applications to finance. Submitted.
  • 37. Wang, X. and Sloan, I.H.: Why are high-dimensional finance problems often of low effective dimension? To appear in SIAM J. Sci. Comput., 2005.
  • 38. Wang, X., Sloan, I.H. and Dick, J.: On Korobov lattice rules in weighted Korobov spaces. SIAM J. Numer. Anal. 42: 1760-1779, 2004.

Similar Articles

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

Retrieve articles in all journals with MSC (2000): 65C05, 65D30

Additional Information

J. Dick
Affiliation: School of Mathematics, The University of New South Wales, Sydney, New South Wales 2052, Australia

F. Y. Kuo
Affiliation: School of Mathematics, The University of New South Wales, Sydney, New South Wales 2052, Australia

F. Pillichshammer
Affiliation: Institut für Analysis, Universität Linz, Altenbergstraße 69, A-4040 Linz, Austria

I. H. Sloan
Affiliation: School of Mathematics, The University of New South Wales, Sydney, New South Wales 2052, Australia

Keywords: Quasi--Monte Carlo, numerical integration, polynomial lattice rules
Received by editor(s): January 9, 2004
Received by editor(s) in revised form: May 4, 2004
Published electronically: May 5, 2005
Article copyright: © Copyright 2005 American Mathematical Society

American Mathematical Society