Exponential convergence and tractability of multivariate integration for Korobov spaces

Dick, Josef; Larcher, Gerhard; Pillichshammer, Friedrich; Woźniakowski, Henryk

doi:10.1090/S0025-5718-2010-02433-0

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