Digital inversive vectors can achieve polynomial tractability for the weighted star discrepancy and for multivariate integration

Dick, Josef; Gomez-Perez, Domingo; Pillichshammer, Friedrich; Winterhof, Arne

doi:10.1090/proc/13490

Digital inversive vectors can achieve polynomial tractability for the weighted star discrepancy and for multivariate integration
HTML articles powered by AMS MathViewer

by Josef Dick, Domingo Gomez-Perez, Friedrich Pillichshammer and Arne Winterhof PDF

Proc. Amer. Math. Soc. 145 (2017), 3297-3310 Request permission

Abstract:

We study high-dimensional numerical integration in the worst-case setting. The subject of tractability is concerned with the dependence of the worst-case integration error on the dimension. Roughly speaking, an integration problem is tractable if the worst-case error does not grow exponentially fast with the dimension. Many classical problems are known to be intractable. However, sometimes tractability can be shown. Often such proofs are based on randomly selected integration nodes. Of course, in applications, true random numbers are not available and hence one mimics them with pseudorandom number generators. This motivates us to propose the use of pseudorandom vectors as underlying integration nodes in order to achieve tractability. In particular, we consider digital inverse vectors and present two examples of problems, the weighted star discrepancy and integration of Hölder continuous, absolute convergent Fourier and cosine series, where the proposed method is successful.

References

Christoph Aistleitner, Covering numbers, dyadic chaining and discrepancy, J. Complexity 27 (2011), no. 6, 531–540. MR 2846704, DOI 10.1016/j.jco.2011.03.001
Christoph Aistleitner and Markus Hofer, Probabilistic discrepancy bound for Monte Carlo point sets, Math. Comp. 83 (2014), no. 287, 1373–1381. MR 3167462, DOI 10.1090/S0025-5718-2013-02773-1
Zhixiong Chen, Finite binary sequences constructed by explicit inversive methods, Finite Fields Appl. 14 (2008), no. 3, 579–592. MR 2435049, DOI 10.1016/j.ffa.2007.08.002
Josef Dick, Numerical integration of Hölder continuous, absolutely convergent Fourier, Fourier cosine, and Walsh series, J. Approx. Theory 183 (2014), 14–30. MR 3209579, DOI 10.1016/j.jat.2014.03.015
Josef Dick, Frances Y. Kuo, and Ian H. Sloan, High-dimensional integration: the quasi-Monte Carlo way, Acta Numer. 22 (2013), 133–288. MR 3038697, DOI 10.1017/S0962492913000044
Josef Dick and Friedrich Pillichshammer, Digital nets and sequences, Cambridge University Press, Cambridge, 2010. Discrepancy theory and quasi-Monte Carlo integration. MR 2683394, DOI 10.1017/CBO9780511761188
Josef Dick and Friedrich Pillichshammer, The inverse of the star-discrepancy problem and the generation of pseudo-random numbers, Sequences and their applications—SETA 2014, Lecture Notes in Comput. Sci., vol. 8865, Springer, Cham, 2014, pp. 173–184. MR 3297330, DOI 10.1007/978-3-319-12325-7_{1}5
Josef Dick and Friedrich Pillichshammer, The weighted star discrepancy of Korobov’s $p$-sets, Proc. Amer. Math. Soc. 143 (2015), no. 12, 5043–5057. MR 3411125, DOI 10.1090/proc/12636
A. Hinrichs, E. Novak, M. Ullrich, and H. Woźniakowski, The curse of dimensionality for numerical integration of smooth functions, Math. Comp. 83 (2014), no. 290, 2853–2863. MR 3246812, DOI 10.1090/S0025-5718-2014-02855-X
Aicke Hinrichs, Erich Novak, Mario Ullrich, and Henryk Woźniakowski, The curse of dimensionality for numerical integration of smooth functions II, J. Complexity 30 (2014), no. 2, 117–143. MR 3166524, DOI 10.1016/j.jco.2013.10.007
Aicke Hinrichs, Erich Novak, and Henryk Woźniakowski, The curse of dimensionality for the class of monotone functions and for the class of convex functions, J. Approx. Theory 163 (2011), no. 8, 955–965. MR 2832759, DOI 10.1016/j.jat.2011.02.009
Stefan Heinrich, Erich Novak, Grzegorz W. Wasilkowski, and Henryk Woźniakowski, The inverse of the star-discrepancy depends linearly on the dimension, Acta Arith. 96 (2001), no. 3, 279–302. MR 1814282, DOI 10.4064/aa96-3-7
Toshiya Itoh and Shigeo Tsujii, A fast algorithm for computing multiplicative inverses in $\textrm {GF}(2^m)$ using normal bases, Inform. and Comput. 78 (1988), no. 3, 171–177. MR 959807, DOI 10.1016/0890-5401(88)90024-7
Dieter Jungnickel, Finite fields, Bibliographisches Institut, Mannheim, 1993. Structure and arithmetics. MR 1238714
Gunther Leobacher and Friedrich Pillichshammer, Introduction to quasi-Monte Carlo integration and applications, Compact Textbooks in Mathematics, Birkhäuser/Springer, Cham, 2014. MR 3289176, DOI 10.1007/978-3-319-03425-6
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
Carlos J. Moreno and Oscar Moreno, Exponential sums and Goppa codes. I, Proc. Amer. Math. Soc. 111 (1991), no. 2, 523–531. MR 1028291, DOI 10.1090/S0002-9939-1991-1028291-1
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 and Arne Winterhof, Incomplete exponential sums over finite fields and their applications to new inversive pseudorandom number generators, Acta Arith. 93 (2000), no. 4, 387–399. MR 1759483, DOI 10.4064/aa-93-4-387-399
Erich Novak and Henryk Woźniakowski, Tractability of multivariate problems. Vol. 1: Linear information, EMS Tracts in Mathematics, vol. 6, European Mathematical Society (EMS), Zürich, 2008. MR 2455266, DOI 10.4171/026
Erich Novak and Henryk Woźniakowski, Tractability of multivariate problems. Volume II: Standard information for functionals, EMS Tracts in Mathematics, vol. 12, European Mathematical Society (EMS), Zürich, 2010. MR 2676032, DOI 10.4171/084
Erich Novak and Henryk Woźniakowski, Tractability of multivariate problems. Volume III: Standard information for operators, EMS Tracts in Mathematics, vol. 18, European Mathematical Society (EMS), Zürich, 2012. MR 2987170, DOI 10.4171/116
Wilfried Meidl and Arne Winterhof, On the linear complexity profile of some new explicit inversive pseudorandom numbers, J. Complexity 20 (2004), no. 2-3, 350–355. MR 2067436, DOI 10.1016/j.jco.2003.08.017
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
Elias M. Stein and Guido Weiss, Introduction to Fourier analysis on Euclidean spaces, Princeton Mathematical Series, No. 32, Princeton University Press, Princeton, N.J., 1971. MR 0304972
Arne Winterhof, On the distribution of some new explicit inversive pseudorandom numbers and vectors, Monte Carlo and quasi-Monte Carlo methods 2004, Springer, Berlin, 2006, pp. 487–499. MR 2208727, DOI 10.1007/3-540-31186-6_{3}0