Exponential convergence and tractability of multivariate integration for Korobov spaces

Authors:
Josef Dick, Gerhard Larcher, Friedrich Pillichshammer and Henryk Woźniakowski

Journal:
Math. Comp. **80** (2011), 905-930

MSC (2010):
Primary 11K45, 65C05, 65D30

Published electronically:
November 2, 2010

MathSciNet review:
2772101

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: In this paper we study multivariate integration for a weighted Korobov space for which the Fourier coefficients of the functions decay exponentially fast. This implies that the functions of this space are infinitely times differentiable. Weights of the Korobov space monitor the influence of each variable and each group of variables. We show that there are numerical integration rules which achieve an exponential convergence of the worst-case integration error. We also investigate the dependence of the worst-case error on the number of variables , and show various tractability results under certain conditions on weights of the Korobov space. Tractability means that the dependence on is never exponential, and sometimes the dependence on is polynomial or there is no dependence on at all.

**1.**N. Aronszajn,*Theory of reproducing kernels*, Trans. Amer. Math. Soc.**68**(1950), 337–404. MR**0051437**, 10.1090/S0002-9947-1950-0051437-7**2.**Yann Bugeaud,*Approximation by algebraic numbers*, Cambridge Tracts in Mathematics, vol. 160, Cambridge University Press, Cambridge, 2004. MR**2136100****3.**Ronald Cools and Hilde Govaert,*Five- and six-dimensional lattice rules generated by structured matrices*, J. Complexity**19**(2003), no. 6, 715–729. Information-Based Complexity Workshop (Minneapolis, MN, 2002). MR**2039626**, 10.1016/j.jco.2003.08.001**4.**Ronald Cools and James N. Lyness,*Three- and four-dimensional 𝐾-optimal lattice rules of moderate trigonometric degree*, Math. Comp.**70**(2001), no. 236, 1549–1567 (electronic). MR**1836918**, 10.1090/S0025-5718-01-01326-6**5.**Josef Dick and Friedrich Pillichshammer,*On the mean square weighted ℒ₂ discrepancy of randomized digital (𝓉,𝓂,𝓈)-nets over ℤ₂*, Acta Arith.**117**(2005), no. 4, 371–403. MR**2140164**, 10.4064/aa117-4-4**6.**Josef Dick, Friedrich Pillichshammer, and Benjamin J. Waterhouse,*The construction of good extensible rank-1 lattices*, Math. Comp.**77**(2008), no. 264, 2345–2373. MR**2429889**, 10.1090/S0025-5718-08-02009-7**7.**Fred J. Hickernell,*Lattice rules: how well do they measure up?*, Random and quasi-random point sets, Lecture Notes in Statist., vol. 138, Springer, New York, 1998, pp. 109–166. MR**1662841**, 10.1007/978-1-4612-1702-2_3**8.**J. N. Lyness,*Notes on lattice rules*, J. Complexity**19**(2003), no. 3, 321–331. Numerical integration and its complexity (Oberwolfach, 2001). MR**1984117**, 10.1016/S0885-064X(03)00005-0**9.**Jiří Matoušek,*Geometric discrepancy*, Algorithms and Combinatorics, vol. 18, Springer-Verlag, Berlin, 1999. An illustrated guide. MR**1697825****10.**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****11.**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****12.**Dirk Nuyens and Ronald Cools,*Fast algorithms for component-by-component construction of rank-1 lattice rules in shift-invariant reproducing kernel Hilbert spaces*, Math. Comp.**75**(2006), no. 254, 903–920 (electronic). MR**2196999**, 10.1090/S0025-5718-06-01785-6**13.**N. N. Osipov,*Construction of lattice cubature formulas with the trigonometric 𝑑-property on the basis of extremal lattices*, Zh. Vychisl. Mat. Mat. Fiz.**48**(2008), no. 2, 212–219 (Russian, with Russian summary); English transl., Comput. Math. Math. Phys.**48**(2008), no. 2, 201–208. MR**2426458**, 10.1134/S0965542508020048**14.**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****15.**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**, 10.1137/S0036142901393942**16.**I. H. Sloan and H. Woźniakowski,*An intractability result for multiple integration*, Math. Comp.**66**(1997), no. 219, 1119–1124. MR**1401946**, 10.1090/S0025-5718-97-00834-X**17.**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**, 10.1006/jcom.1997.0463**18.**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**, 10.1006/jcom.2001.0599

Retrieve articles in *Mathematics of Computation*
with MSC (2010):
11K45,
65C05,
65D30

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

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

**Gerhard Larcher**

Affiliation:
Institut für Finanzmathematik, Universität Linz, Altenbergstraße 69, A-4040 Linz, Austria

Email:
gerhard.larcher@jku.at

**Friedrich Pillichshammer**

Affiliation:
Institut für Finanzmathematik, Universität Linz, Altenbergstraße 69, A-4040 Linz, Austria

Email:
friedrich.pillichshammer@jku.at

**Henryk Woźniakowski**

Affiliation:
Department of Computer Science, Columbia University, New York, New York 10027, USA and Institute of Applied Mathematics, University of Warsaw, ul. Banacha 2, 02-097 Warszawa, Poland

Email:
henryk@cs.columbia.edu

DOI:
https://doi.org/10.1090/S0025-5718-2010-02433-0

Keywords:
Quasi-Monte Carlo,
numerical integration,
lattice rules,
tractability.

Received by editor(s):
July 13, 2009

Received by editor(s) in revised form:
March 17, 2010

Published electronically:
November 2, 2010

Additional Notes:
The second author was supported by the Austrian Science Foundation (FWF), Project P21196

The third author was supported by the Austrian Research Foundation (FWF), Project S 9609, which is part of the Austrian Research Network “Analytic Combinatorics and Probabilistic Number Theory”.

The fourth author was partially supported by the National Science Foundation.

Article copyright:
© Copyright 2010
American Mathematical Society