Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

 
 

 

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


Authors: Josef Dick, Domingo Gomez-Perez, Friedrich Pillichshammer and Arne Winterhof
Journal: Proc. Amer. Math. Soc. 145 (2017), 3297-3310
MSC (2010): Primary 11K38, 11K45, 11T23, 65C05, 65C10
DOI: https://doi.org/10.1090/proc/13490
Published electronically: January 27, 2017
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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

  • [1] Christoph Aistleitner, Covering numbers, dyadic chaining and discrepancy, J. Complexity 27 (2011), no. 6, 531-540. MR 2846704, https://doi.org/10.1016/j.jco.2011.03.001
  • [2] Christoph Aistleitner and Markus Hofer, Probabilistic discrepancy bound for Monte Carlo point sets, Math. Comp. 83 (2014), no. 287, 1373-1381. MR 3167462, https://doi.org/10.1090/S0025-5718-2013-02773-1
  • [3] Zhixiong Chen, Finite binary sequences constructed by explicit inversive methods, Finite Fields Appl. 14 (2008), no. 3, 579-592. MR 2435049, https://doi.org/10.1016/j.ffa.2007.08.002
  • [4] 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, https://doi.org/10.1016/j.jat.2014.03.015
  • [5] 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
  • [6] Josef Dick and Friedrich Pillichshammer, Digital nets and sequences, Cambridge University Press, Cambridge, 2010. Discrepancy theory and quasi-Monte Carlo integration. MR 2683394
  • [7] 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, https://doi.org/10.1007/978-3-319-12325-7_15
  • [8] 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, https://doi.org/10.1090/proc/12636
  • [9] 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, https://doi.org/10.1090/S0025-5718-2014-02855-X
  • [10] 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, https://doi.org/10.1016/j.jco.2013.10.007
  • [11] 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, https://doi.org/10.1016/j.jat.2011.02.009
  • [12] 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, https://doi.org/10.4064/aa96-3-7
  • [13] Toshiya Itoh and Shigeo Tsujii, A fast algorithm for computing multiplicative inverses in $ {\rm GF}(2^m)$ using normal bases, Inform. and Comput. 78 (1988), no. 3, 171-177. MR 959807, https://doi.org/10.1016/0890-5401(88)90024-7
  • [14] Dieter Jungnickel, Finite fields, Bibliographisches Institut, Mannheim, 1993. Structure and arithmetics. MR 1238714
  • [15] Gunther Leobacher and Friedrich Pillichshammer, Introduction to quasi-Monte Carlo integration and applications, Compact Textbook in Mathematics, Birkhäuser/Springer, Cham, 2014. MR 3289176
  • [16] Rudolf Lidl and Harald Niederreiter, Introduction to finite fields and their applications, 1st ed., Cambridge University Press, Cambridge, 1994. MR 1294139
  • [17] Carlos J. Moreno and Oscar Moreno, Exponential sums and Goppa codes. I, Proc. Amer. Math. Soc. 111 (1991), no. 2, 523-531. MR 1028291, https://doi.org/10.2307/2048345
  • [18] 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
  • [19] 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
  • [20] 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
  • [21] 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
  • [22] 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
  • [23] 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, https://doi.org/10.1016/j.jco.2003.08.017
  • [24] 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, https://doi.org/10.1006/jcom.1997.0463
  • [25] Elias M. Stein and Guido Weiss, Introduction to Fourier analysis on Euclidean spaces, Princeton University Press, Princeton, N.J., 1971. Princeton Mathematical Series, No. 32. MR 0304972
  • [26] 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, https://doi.org/10.1007/3-540-31186-6_30

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2010): 11K38, 11K45, 11T23, 65C05, 65C10

Retrieve articles in all journals with MSC (2010): 11K38, 11K45, 11T23, 65C05, 65C10


Additional Information

Josef Dick
Affiliation: School of Mathematics and Statistics, The University of New South Wales, Sydney NSW 2052, Australia
Email: josef.dick@unsw.edu.au

Domingo Gomez-Perez
Affiliation: Faculty of Sciences, University of Cantabria, E-39071 Santander, Spain
Email: domingo.gomez@unican.es

Friedrich Pillichshammer
Affiliation: Department for Financial Mathematics and Applied Number Theory, Johannes Kepler University Linz, Altenbergerstr. 69, 4040 Linz, Austria
Email: friedrich.pillichshammer@jku.at

Arne Winterhof
Affiliation: Johann Radon Institute for Computational and Applied Mathematics, Austrian Academy of Sciences, Altenbergerstr. 69, 4040 Linz, Austria
Email: arne.winterhof@oeaw.ac.at

DOI: https://doi.org/10.1090/proc/13490
Keywords: Weighted star discrepancy, pseudorandom numbers, tractability, quasi-Monte Carlo
Received by editor(s): December 21, 2015
Received by editor(s) in revised form: September 9, 2016
Published electronically: January 27, 2017
Additional Notes: The research of the first author was supported under the Australian Research Councils Discovery Projects funding scheme (project number DP150101770). The research of the second author was supported by the Ministerio de Economia y Competitividad research project MTM2014-55421-P. The third and fourth authors were supported by the Austrian Science Fund (FWF): Projects F5509-N26 (third author) and F5511-N26 (fourth author), respectively, which are part of the Special Research Program “Quasi-Monte Carlo Methods: Theory and Applications”.
Dedicated: In memory of Joseph Frederick Traub (1932–2015) and Oscar Moreno de Ayala (1946–2015)
Communicated by: Walter Van Assche
Article copyright: © Copyright 2017 American Mathematical Society

American Mathematical Society