## Exponential convergence and tractability of multivariate integration for Korobov spaces

HTML articles powered by AMS MathViewer

- by Josef Dick, Gerhard Larcher, Friedrich Pillichshammer and Henryk Woźniakowski PDF
- Math. Comp.
**80**(2011), 905-930 Request permission

## 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 $s$, and show various tractability results under certain conditions on weights of the Korobov space. Tractability means that the dependence on $s$ is never exponential, and sometimes the dependence on $s$ is polynomial or there is no dependence on $s$ at all.## 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 - Yann Bugeaud,
*Approximation by algebraic numbers*, Cambridge Tracts in Mathematics, vol. 160, Cambridge University Press, Cambridge, 2004. MR**2136100**, DOI 10.1017/CBO9780511542886 - 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**, DOI 10.1016/j.jco.2003.08.001 - Ronald Cools and James N. Lyness,
*Three- and four-dimensional $K$-optimal lattice rules of moderate trigonometric degree*, Math. Comp.**70**(2001), no. 236, 1549–1567. MR**1836918**, DOI 10.1090/S0025-5718-01-01326-6 - Josef Dick and Friedrich Pillichshammer,
*On the mean square weighted $\scr L_2$ discrepancy of randomized digital $(t,m,s)$-nets over $\Bbb Z_2$*, Acta Arith.**117**(2005), no. 4, 371–403. MR**2140164**, DOI 10.4064/aa117-4-4 - 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**, DOI 10.1090/S0025-5718-08-02009-7 - 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} - J. N. Lyness,
*Notes on lattice rules*, J. Complexity**19**(2003), no. 3, 321–331. Numerical integration and its complexity (Oberwolfach, 2001). MR**1984117**, DOI 10.1016/S0885-064X(03)00005-0 - Jiří Matoušek,
*Geometric discrepancy*, Algorithms and Combinatorics, vol. 18, Springer-Verlag, Berlin, 1999. An illustrated guide. MR**1697825**, DOI 10.1007/978-3-642-03942-3 - 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 - 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 - 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. MR**2196999**, DOI 10.1090/S0025-5718-06-01785-6 - N. N. Osipov,
*Construction of lattice cubature formulas with the trigonometric $d$-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**, DOI 10.1134/S0965542508020048 - 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 and H. Woźniakowski,
*An intractability result for multiple integration*, Math. Comp.**66**(1997), no. 219, 1119–1124. MR**1401946**, DOI 10.1090/S0025-5718-97-00834-X - 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

## 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
- MR Author ID: 661956
- ORCID: 0000-0001-6952-9218
- 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
- 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. - © Copyright 2010 American Mathematical Society
- Journal: Math. Comp.
**80**(2011), 905-930 - MSC (2010): Primary 11K45, 65C05, 65D30
- DOI: https://doi.org/10.1090/S0025-5718-2010-02433-0
- MathSciNet review: 2772101