Scaled lattice rules for integration on ℝ^{𝕕} achieving higher-order convergence with error analysis in terms of orthogonal projections onto periodic spaces

Nuyens, Dirk; Suzuki, Yuya

doi:10.1090/mcom/3754

Scaled lattice rules for integration on $\mathbb {R}^d$ achieving higher-order convergence with error analysis in terms of orthogonal projections onto periodic spaces
HTML articles powered by AMS MathViewer

by Dirk Nuyens and Yuya Suzuki;

Math. Comp. 92 (2023), 307-347

DOI: https://doi.org/10.1090/mcom/3754

Published electronically: August 12, 2022

HTML | PDF | Request permission

Abstract:

We introduce a new method to approximate integrals $\int _{\mathbb {R}^d} f(\boldsymbol {x}) \,\mathrm {d}\boldsymbol {x}$ which simply scales lattice rules from the unit cube $[0,1]^d$ to properly sized boxes on $\mathbb {R}^d$, hereby achieving higher-order convergence that matches the smoothness of the integrand function $f$ in a certain Sobolev space of dominating mixed smoothness. Our method only assumes that we can evaluate the integrand function $f$ and does not assume a particular density nor the ability to sample from it. In particular, for the theoretical analysis we show a new result that the method of adding Bernoulli polynomials to a function to make it “periodic” on a box without changing its integral value over the box is equivalent to an orthogonal projection from a well chosen Sobolev space of dominating mixed smoothness to an associated periodic Sobolev space of the same dominating mixed smoothness, which we call a Korobov space. We note that the Bernoulli polynomial method is often not used because of its excessive computational complexity and also here we only make use of it in our theoretical analysis. We show that our new method of applying scaled lattice rules to increasing boxes can be interpreted as orthogonal projections with decreasing projection error. Such a method would not work on the unit cube since then the committed error caused by non-periodicity of the integrand would be constant, but for integration on the Euclidean space we can use the certain decay towards zero when the boxes grow. Hence we can bound the truncation error as well as the projection error and show higher-order convergence in applying scaled lattice rules for integration on Euclidean space. We illustrate our theoretical analysis by numerical experiments which confirm our findings.

References

Joakim Bäck, Fabio Nobile, Lorenzo Tamellini, and Raul Tempone, Stochastic spectral Galerkin and collocation methods for PDEs with random coefficients: a numerical comparison (J. S. Hesthaven and E. M. Ronquist, eds.), Lecture Notes in Computational Science and Engineering, vol. 76, Springer, 2011. Code available at https://sites.google.com/view/sparse-grids-kit.
Marc Beckers and Ann Haegemans, Transformation of integrands for lattice rules, Numerical integration (Bergen, 1991) NATO Adv. Sci. Inst. Ser. C: Math. Phys. Sci., vol. 357, Kluwer Acad. Publ., Dordrecht, 1992, pp. 329–340. MR 1198915
Ronald Cools, Frances Y. Kuo, and Dirk Nuyens, Constructing embedded lattice rules for multivariable integration, SIAM J. Sci. Comput. 28 (2006), no. 6, 2162–2188. MR 2272256, DOI 10.1137/06065074X
Ronald Cools, Frances Y. Kuo, Dirk Nuyens, and Gowri Suryanarayana, Tent-transformed lattice rules for integration and approximation of multivariate non-periodic functions, J. Complexity 36 (2016), 166–181. MR 3530643, DOI 10.1016/j.jco.2016.05.004
Josef Dick, Christian Irrgeher, Gunther Leobacher, and Friedrich Pillichshammer, On the optimal order of integration in Hermite spaces with finite smoothness, SIAM J. Numer. Anal. 56 (2018), no. 2, 684–707. MR 3780119, DOI 10.1137/16M1087461
Josef Dick, Frances Y. Kuo, Quoc T. Le Gia, Dirk Nuyens, and Christoph Schwab, Higher order QMC Petrov-Galerkin discretization for affine parametric operator equations with random field inputs, SIAM J. Numer. Anal. 52 (2014), no. 6, 2676–2702. MR 3276428, DOI 10.1137/130943984
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, Dirk Nuyens, and Friedrich Pillichshammer, Lattice rules for nonperiodic smooth integrands, Numer. Math. 126 (2014), no. 2, 259–291. MR 3150223, DOI 10.1007/s00211-013-0566-0
Josef Dick, Ian H. Sloan, Xiaoqun Wang, and Henryk Woźniakowski, Liberating the weights, J. Complexity 20 (2004), no. 5, 593–623. MR 2086942, DOI 10.1016/j.jco.2003.06.002
F. W. J. Olver, A. B. Olde Daalhuis, D. W. Lozier, B. I. Schneider, R. F. Boisvert, C. W. Clark, B. R. Miller, B. V. Saunders, H. S. Cohl, and M. A. McClain (eds.), NIST Digital Library of Mathematical Functions, 2022.
Takashi Goda, Kosuke Suzuki, and Takehito Yoshiki, Lattice rules in non-periodic subspaces of Sobolev spaces, Numer. Math. 141 (2019), no. 2, 399–427. MR 3905431, DOI 10.1007/s00211-018-1003-1
Fred J. Hickernell, Obtaining $O(N^{-2+\epsilon })$ convergence for lattice quadrature rules, Monte Carlo and quasi-Monte Carlo methods, 2000 (Hong Kong), Springer, Berlin, 2002, pp. 274–289. MR 1958860
Fred J. Hickernell, Peter Kritzer, Frances Y. Kuo, and Dirk Nuyens, Weighted compound integration rules with higher order convergence for all $N$, Numer. Algorithms 59 (2012), no. 2, 161–183. MR 2873129, DOI 10.1007/s11075-011-9482-5
Christian Irrgeher and Gunther Leobacher, High-dimensional integration on $\Bbb R^d$, weighted Hermite spaces, and orthogonal transforms, J. Complexity 31 (2015), no. 2, 174–205. MR 3305992, DOI 10.1016/j.jco.2014.09.002
N. M. Korobov, Teoretiko-chislovye metody v priblizhennom analize, Gosudarstv. Izdat. Fiz.-Mat. Lit., Moscow, 1963 (Russian). MR 157483
Frances Y. Kuo and Dirk Nuyens, Application of quasi-Monte Carlo methods to elliptic PDEs with random diffusion coefficients: a survey of analysis and implementation, Found. Comput. Math. 16 (2016), no. 6, 1631–1696. MR 3579719, DOI 10.1007/s10208-016-9329-5
Frances Y. Kuo, Ian H. Sloan, Grzegorz W. Wasilkowski, and Benjamin J. Waterhouse, Randomly shifted lattice rules with the optimal rate of convergence for unbounded integrands, J. Complexity 26 (2010), no. 2, 135–160. MR 2607729, DOI 10.1016/j.jco.2009.07.005
Frances Y. Kuo, Ian H. Sloan, and Henryk Woźniakowski, Periodization strategy may fail in high dimensions, Numer. Algorithms 46 (2007), no. 4, 369–391. MR 2374244, DOI 10.1007/s11075-007-9145-8
D. H. Lehmer, On the maxima and minima of Bernoulli polynomials, Amer. Math. Monthly 47 (1940), 533–538. MR 2378, DOI 10.2307/2303833
Dong T. P. Nguyen and Dirk Nuyens, Multivariate integration over $\Bbb {R}^s$ with exponential rate of convergence, J. Comput. Appl. Math. 315 (2017), 327–342. MR 3583689, DOI 10.1016/j.cam.2016.11.016
Dong T. P. Nguyen and Dirk Nuyens, MDFEM: multivariate decomposition finite element method for elliptic PDEs with lognormal diffusion coefficients using higher-order QMC and FEM, ESAIM Math. Model. Numer. Anal. 55 (2021), no. 4, 1461–1505. MR 4290093, DOI 10.1051/m2an/2021029
James A. Nichols and Frances Y. Kuo, Fast CBC construction of randomly shifted lattice rules achieving $\scr {O}(n^{-1+\delta })$ convergence for unbounded integrands over $\Bbb {R}^s$ in weighted spaces with POD weights, J. Complexity 30 (2014), no. 4, 444–468. MR 3212781, DOI 10.1016/j.jco.2014.02.004
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
Walter Rudin, Principles of mathematical analysis, 3rd ed., International Series in Pure and Applied Mathematics, McGraw-Hill Book Co., New York-Auckland-Düsseldorf, 1976. MR 385023
Avram Sidi, A new variable transformation for numerical integration, Numerical integration, IV (Oberwolfach, 1992) Internat. Ser. Numer. Math., vol. 112, Birkhäuser, Basel, 1993, pp. 359–373. MR 1248416
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
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
S. K. Zaremba, La méthode des “bons treillis” pour le calcul des intégrales multiples, Applications of number theory to numerical analysis (Proc. Sympos., Univ. Montréal, Montreal, Que., 1971) Academic Press, New York-London, 1972, pp. 39–119 (French, with English summary). MR 343530