Construction algorithms for polynomial lattice rules for multivariate integration

Dick, J.; Kuo, F.; Pillichshammer, F.; Sloan, I.

doi:10.1090/S0025-5718-05-01742-4

Construction algorithms for polynomial lattice rules for multivariate integration
HTML articles powered by AMS MathViewer

by J. Dick, F. Y. Kuo, F. Pillichshammer and I. H. Sloan PDF

Math. Comp. 74 (2005), 1895-1921 Request permission

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

N. Aronszajn, Theory of reproducing kernels, Trans. Amer. Math. Soc. 68 (1950), 337–404. MR 51437, DOI 10.1090/S0002-9947-1950-0051437-7
H. E. Chrestenson, A class of generalized Walsh functions, Pacific J. Math. 5 (1955), 17–31. MR 68659
R. Cranley and T. N. L. Patterson, Randomization of number theoretic methods for multiple integration, SIAM J. Numer. Anal. 13 (1976), no. 6, 904–914. MR 494820, DOI 10.1137/0713071
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
Dick, J., Pillichshammer, F.: Multivariate integration in weighted Hilbert spaces based on Walsh functions and weighted Sobolev spaces. J. Complexity, 21: 149–195, 2005.
Dick, J., Sloan, I.H., Wang, X., and Woźniakowski, H.: Liberating the weights. J. Complexity, 20: 593–623, 2004.
Dick, J., Sloan, I.H., Wang, X. and Woźniakowski, H.: Good lattice rules in weighted Korobov spaces with general weights. Submitted.
Henri Faure, Discrépance de suites associées à un système de numération (en dimension $s$), Acta Arith. 41 (1982), no. 4, 337–351 (French). MR 677547, DOI 10.4064/aa-41-4-337-351
Fred J. Hickernell, Lattice rules: how well do they measure up?, Random and quasi-random point sets, Lect. Notes Stat., vol. 138, Springer, New York, 1998, pp. 109–166. MR 1662841, DOI 10.1007/978-1-4612-1702-2_{3}
N. M. Korobov, Approximate evaluation of repeated integrals, Dokl. Akad. Nauk SSSR 124 (1959), 1207–1210 (Russian). MR 0104086
N. M. Korobov, Properties and calculation of optimal coefficients, Soviet Math. Dokl. 1 (1960), 696–700. MR 0120768
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
Gerhard Larcher, Digital point sets: analysis and application, Random and quasi-random point sets, Lect. Notes Stat., vol. 138, Springer, New York, 1998, pp. 167–222. MR 1662842, DOI 10.1007/978-1-4612-1702-2_{4}
G. Larcher, A. Lauss, H. Niederreiter, and W. Ch. Schmid, Optimal polynomials for $(t,m,s)$-nets and numerical integration of multivariate Walsh series, SIAM J. Numer. Anal. 33 (1996), no. 6, 2239–2253. MR 1427461, DOI 10.1137/S0036142994264705
Gerhard Larcher, Harald Niederreiter, and Wolfgang Ch. Schmid, Digital nets and sequences constructed over finite rings and their application to quasi-Monte Carlo integration, Monatsh. Math. 121 (1996), no. 3, 231–253. MR 1383533, DOI 10.1007/BF01298952
Christiane Lemieux and Pierre L’Ecuyer, Randomized polynomial lattice rules for multivariate integration and simulation, SIAM J. Sci. Comput. 24 (2003), no. 5, 1768–1789. MR 1978160, DOI 10.1137/S1064827501393782
Rudolf Lidl and Harald Niederreiter, Introduction to finite fields and their applications, 1st ed., Cambridge University Press, Cambridge, 1994. MR 1294139, DOI 10.1017/CBO9781139172769
Klaus Niederdrenk, Die endliche Fourier- und Walsh-Transformation mit einer Einführung in die Bildverarbeitung, Friedr. Vieweg & Sohn, Braunschweig, 1982 (German). Eine anwendungsorientierte Darstellung mit FORTRAN 77-Programmen. [An applications-oriented treatment with FORTRAN 77 programs]. MR 735256, DOI 10.1007/978-3-663-14178-5
Harald Niederreiter, Point sets and sequences with small discrepancy, Monatsh. Math. 104 (1987), no. 4, 273–337. MR 918037, DOI 10.1007/BF01294651
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, Finite fields, pseudorandom numbers, and quasirandom points, Finite fields, coding theory, and advances in communications and computing (Las Vegas, NV, 1991) Lecture Notes in Pure and Appl. Math., vol. 141, Dekker, New York, 1993, pp. 375–394. MR 1199844
Harald Niederreiter, Constructions of $(t,m,s)$-nets, Monte Carlo and quasi-Monte Carlo methods 1998 (Claremont, CA), Springer, Berlin, 2000, pp. 70–85. MR 1849843
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
Pirsic, G.: Schnell konvergierende Walshreihen über Gruppen. Master’s Thesis, University of Salzburg, 1995. (Available at http://www.ricam.oeaw.ac.at/people/page/pirsic/)
Gottlieb Pirsic and Wolfgang Ch. Schmid, Calculation of the quality parameter of digital nets and application to their construction, J. Complexity 17 (2001), no. 4, 827–839. Complexity of multivariate problems (Kowloon, 1999). MR 1881672, DOI 10.1006/jcom.2001.0597
Joseph L. Walsh, Selected papers, Springer-Verlag, New York, 2000. With brief biographical sketches of Walsh by W. E. Sewell, D. V. Widder and Morris Marden and commentaries by Q. I. Rahman, P. M. Gauthier, Dieter Gaier, Walter Schempp and the editors; Edited by Theodore J. Rivlin and Edward B. Saff. MR 1757949, DOI 10.1007/978-1-4614-6301-6
Wolfgang Ch. Schmid, Improvements and extensions of the “Salzburg tables” by using irreducible polynomials, Monte Carlo and quasi-Monte Carlo methods 1998 (Claremont, CA), Springer, Berlin, 2000, pp. 436–447. MR 1849869
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, F. Y. Kuo, and S. Joe, 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 (2002), no. 240, 1609–1640. MR 1933047, DOI 10.1090/S0025-5718-02-01420-5
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
Ian H. Sloan and Henryk Woźniakowski, Tractability of multivariate integration for weighted Korobov classes, J. Complexity 17 (2001), no. 4, 697–721. Complexity of multivariate problems (Kowloon, 1999). MR 1881665, DOI 10.1006/jcom.2001.0599
I. M. Sobol′, Distribution of points in a cube and approximate evaluation of integrals, Ž. Vyčisl. Mat i Mat. Fiz. 7 (1967), 784–802 (Russian). MR 219238
Walsh, J.L.: A closed set of normal orthogonal functions. Amer. J. Math., 55: 5–24, 1923.
Wang, X. and Sloan, I.H.: Efficient weighted lattice rules with applications to finance. Submitted.
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.
Wang, X., Sloan, I.H. and Dick, J.: On Korobov lattice rules in weighted Korobov spaces. SIAM J. Numer. Anal. 42: 1760–1779, 2004.