Fast component-by-component construction of lattice algorithms for multivariate approximation with POD and SPOD weights

Cools, Ronald; Kuo, Frances; Nuyens, Dirk; Sloan, Ian

doi:10.1090/mcom/3586

Fast component-by-component construction of lattice algorithms for multivariate approximation with POD and SPOD weights
HTML articles powered by AMS MathViewer

by Ronald Cools, Frances Y. Kuo, Dirk Nuyens and Ian H. Sloan HTML | PDF

Math. Comp. 90 (2021), 787-812 Request permission

Abstract:

In a recent paper by the same authors, we provided a theoretical foundation for the component-by-component (CBC) construction of lattice algorithms for multivariate $L_2$ approximation in the worst case setting, for functions in a periodic space with general weight parameters. The construction led to an error bound that achieves the best possible rate of convergence for lattice algorithms. Previously available literature covered only weights of a simple form commonly known as product weights. In this paper we address the computational aspect of the construction. We develop fast CBC construction of lattice algorithms for special forms of weight parameters, including the so-called POD weights and SPOD weights which arise from PDE applications, making the lattice algorithms truly applicable in practice. With $d$ denoting the dimension and $n$ the number of lattice points, we show that the construction cost is $\mathcal {O}(d n\log (n) + d^2\log (d) n)$ for POD weights, and $\mathcal {O}(d n\log (n) + d^3\sigma ^2 n)$ for SPOD weights of degree $\sigma \ge 2$. The resulting lattice generating vectors can be used in other lattice-based approximation algorithms, including kernel methods or splines.

References

Glenn Byrenheid, Lutz Kämmerer, Tino Ullrich, and Toni Volkmer, Tight error bounds for rank-1 lattice sampling in spaces of hybrid mixed smoothness, Numer. Math. 136 (2017), no. 4, 993–1034. MR 3671595, DOI 10.1007/s00211-016-0861-7
Albert Cohen, Ronald DeVore, and Christoph Schwab, Convergence rates of best $N$-term Galerkin approximations for a class of elliptic sPDEs, Found. Comput. Math. 10 (2010), no. 6, 615–646. MR 2728424, DOI 10.1007/s10208-010-9072-2
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 Ian H. Sloan, Lattice algorithms for multivariate approximation in periodic spaces with general weight parameters, 75 years of mathematics of computation, Contemp. Math., vol. 754, Amer. Math. Soc., [Providence], RI, [2020] ©2020, pp. 93–113. MR 4132118, DOI 10.1090/conm/754/15150
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
Ronald Cools and Dirk Nuyens, A Belgian view on lattice rules, Monte Carlo and quasi-Monte Carlo methods 2006, Springer, Berlin, 2008, pp. 3–21. MR 2479214, DOI 10.1007/978-3-540-74496-2_{1}
Josef Dick, Walsh spaces containing smooth functions and quasi-Monte Carlo rules of arbitrary high order, SIAM J. Numer. Anal. 46 (2008), no. 3, 1519–1553. MR 2391005, DOI 10.1137/060666639
Josef Dick, Peter Kritzer, Frances Y. Kuo, and Ian H. Sloan, Lattice-Nyström method for Fredholm integral equations of the second kind with convolution type kernels, J. Complexity 23 (2007), no. 4-6, 752–772. MR 2371991, DOI 10.1016/j.jco.2007.03.004
Josef Dick, Frances Y. Kuo, Quoc T. Le Gia, and Christoph Schwab, Multilevel higher order QMC Petrov-Galerkin discretization for affine parametric operator equations, SIAM J. Numer. Anal. 54 (2016), no. 4, 2541–2568. MR 3537887, DOI 10.1137/16M1078690
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 and Friedrich Pillichshammer, Digital nets and sequences, Cambridge University Press, Cambridge, 2010. Discrepancy theory and quasi-Monte Carlo integration. MR 2683394, DOI 10.1017/CBO9780511761188
Josef Dick, Ian H. Sloan, Xiaoqun Wang, and Henryk Woźniakowski, Good lattice rules in weighted Korobov spaces with general weights, Numer. Math. 103 (2006), no. 1, 63–97. MR 2207615, DOI 10.1007/s00211-005-0674-6
Adrian Ebert, Hernan Leövey, and Dirk Nuyens, Successive coordinate search and component-by-component construction of rank-1 lattice rules, Monte Carlo and quasi–Monte Carlo methods, Springer Proc. Math. Stat., vol. 241, Springer, Cham, 2018, pp. 197–215. MR 3828141, DOI 10.1007/978-3-319-91436-7_{1}0
I. G. Graham, F. Y. Kuo, J. A. Nichols, R. Scheichl, Ch. Schwab, and I. H. Sloan, Quasi-Monte Carlo finite element methods for elliptic PDEs with lognormal random coefficients, Numer. Math. 131 (2015), no. 2, 329–368. MR 3385149, DOI 10.1007/s00211-014-0689-y
Ivan G. Graham, Frances Y. Kuo, Dirk Nuyens, Rob Scheichl, and Ian H. Sloan, Circulant embedding with QMC: analysis for elliptic PDE with lognormal coefficients, Numer. Math. 140 (2018), no. 2, 479–511. MR 3851064, DOI 10.1007/s00211-018-0968-0
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}
Fred J. Hickernell and Hee Sun Hong, Quasi-Monte-Carlo methods and their randomizations, Applied probability (Hong Kong, 1999) AMS/IP Stud. Adv. Math., vol. 26, Amer. Math. Soc., Providence, RI, 2002, pp. 59–78. MR 1909878, DOI 10.1090/amsip/026/06
V. Kaarnioja, Y. Kazashi, F. Y. Kuo, F. Nobile, and I. H. Sloan, Fast approximation by periodic kernel-based lattice-point interpolation with application in uncertainty quantification, arXiv:2007.06367 (2020).
V. Kaarnioja, F. Y. Kuo, and I. H. Sloan, Uncertainty quantification using periodic random variables, SIAM J. Numer. Anal. 58 (2020), no. 2, 1068–1091. MR 4080389, DOI 10.1137/19M1262796
Lutz Kämmerer, Reconstructing hyperbolic cross trigonometric polynomials by sampling along rank-1 lattices, SIAM J. Numer. Anal. 51 (2013), no. 5, 2773–2796. MR 3115464, DOI 10.1137/120871183
Lutz Kämmerer, Daniel Potts, and Toni Volkmer, Approximation of multivariate periodic functions by trigonometric polynomials based on rank-1 lattice sampling, J. Complexity 31 (2015), no. 4, 543–576. MR 3348081, DOI 10.1016/j.jco.2015.02.004
D. Krieg and M. Ullrich, Function values are enough for $L_2$-approximation, arXiv:1905.02516 (2019).
F. Y. Kuo, Component-by-component constructions achieve the optimal rate of convergence for multivariate integration in weighted Korobov and Sobolev spaces, J. Complexity 19 (2003), no. 3, 301–320. Numerical integration and its complexity (Oberwolfach, 2001). MR 1984116, DOI 10.1016/S0885-064X(03)00006-2
F. Y. Kuo, G. Migliorati, F. Nobile, and D. Nuyens, Function integration, reconstruction and approximation using rank-$1$ lattices, arXiv:1908.01178 (2019), to appear in Math. Comp.
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
F. Y. Kuo, Ch. Schwab, and I. H. Sloan, Quasi-Monte Carlo methods for high-dimensional integration: the standard (weighted Hilbert space) setting and beyond, ANZIAM J. 53 (2011), no. 1, 1–37. MR 2928989, DOI 10.1017/S1446181112000077
Frances Y. Kuo, Christoph Schwab, and Ian H. Sloan, Quasi-Monte Carlo finite element methods for a class of elliptic partial differential equations with random coefficients, SIAM J. Numer. Anal. 50 (2012), no. 6, 3351–3374. MR 3024159, DOI 10.1137/110845537
F. Y. Kuo, I. H. Sloan, G. W. Wasilkowski, and H. Woźniakowski, On decompositions of multivariate functions, Math. Comp. 79 (2010), no. 270, 953–966. MR 2600550, DOI 10.1090/S0025-5718-09-02319-9
Frances Y. Kuo, Ian H. Sloan, and Henryk Woźniakowski, Lattice rules for multivariate approximation in the worst case setting, Monte Carlo and quasi-Monte Carlo methods 2004, Springer, Berlin, 2006, pp. 289–330. MR 2208715, DOI 10.1007/3-540-31186-6_{1}8
Frances Y. Kuo, Ian H. Sloan, and Henryk Woźniakowski, Lattice rule algorithms for multivariate approximation in the average case setting, J. Complexity 24 (2008), no. 2, 283–323. MR 2400322, DOI 10.1016/j.jco.2006.10.006
Frances Y. Kuo, Grzegorz W. Wasilkowski, and Henryk Woźniakowski, On the power of standard information for multivariate approximation in the worst case setting, J. Approx. Theory 158 (2009), no. 1, 97–125. MR 2523723, DOI 10.1016/j.jat.2008.01.011
Pierre L’Ecuyer and David Munger, On figures of merit for randomly-shifted lattice rules, Monte Carlo and quasi-Monte Carlo methods 2010, Springer Proc. Math. Stat., vol. 23, Springer, Heidelberg, 2012, pp. 133–159. MR 3173832, DOI 10.1007/978-3-642-27440-4_{6}
Christiane Lemieux, Monte Carlo and quasi-Monte Carlo sampling, Springer Series in Statistics, Springer, New York, 2009. MR 2723077
Gunther Leobacher and Friedrich Pillichshammer, Introduction to quasi-Monte Carlo integration and applications, Compact Textbooks in Mathematics, Birkhäuser/Springer, Cham, 2014. MR 3289176, DOI 10.1007/978-3-319-03425-6
Dong Li and Fred J. Hickernell, Trigonometric spectral collocation methods on lattices, Recent advances in scientific computing and partial differential equations (Hong Kong, 2002) Contemp. Math., vol. 330, Amer. Math. Soc., Providence, RI, 2003, pp. 121–132. MR 2011715, DOI 10.1090/conm/330/05887
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, Ian H. Sloan, and Henryk Woźniakowski, Tractability of approximation for weighted Korobov spaces on classical and quantum computers, Found. Comput. Math. 4 (2004), no. 2, 121–156. MR 2049868, DOI 10.1007/s10208-002-0074-6
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
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, DOI 10.4171/084
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, DOI 10.4171/116
Dirk Nuyens, The construction of good lattice rules and polynomial lattice rules, Uniform distribution and quasi-Monte Carlo methods, Radon Ser. Comput. Appl. Math., vol. 15, De Gruyter, Berlin, 2014, pp. 223–255. MR 3287367
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
Dirk Nuyens and Ronald Cools, Fast component-by-component construction of rank-1 lattice rules with a non-prime number of points, J. Complexity 22 (2006), no. 1, 4–28. MR 2198499, DOI 10.1016/j.jco.2005.07.002
Dirk Nuyens and Ronald Cools, Fast component-by-component construction, a reprise for different kernels, Monte Carlo and quasi-Monte Carlo methods 2004, Springer, Berlin, 2006, pp. 373–387. MR 2208719, DOI 10.1007/3-540-31186-6_{2}2
Dirk Nuyens, Gowri Suryanarayana, and Markus Weimar, Construction of quasi-Monte Carlo rules for multivariate integration in spaces of permutation-invariant functions, Constr. Approx. 45 (2017), no. 2, 311–344. MR 3619446, DOI 10.1007/s00365-016-9362-2
Daniel Potts and Toni Volkmer, Sparse high-dimensional FFT based on rank-1 lattice sampling, Appl. Comput. Harmon. Anal. 41 (2016), no. 3, 713–748. MR 3546427, DOI 10.1016/j.acha.2015.05.002
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 A. V. Reztsov, Component-by-component construction of good lattice rules, Math. Comp. 71 (2002), no. 237, 263–273. MR 1862999, DOI 10.1090/S0025-5718-01-01342-4
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
Gowri Suryanarayana, Dirk Nuyens, and Ronald Cools, Reconstruction and collocation of a class of non-periodic functions by sampling along tent-transformed rank-1 lattices, J. Fourier Anal. Appl. 22 (2016), no. 1, 187–214. MR 3448919, DOI 10.1007/s00041-015-9412-3
Grace Wahba, Spline models for observational data, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 59, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1990. MR 1045442, DOI 10.1137/1.9781611970128
Xiaoyan Zeng, King-Tai Leung, and Fred J. Hickernell, Error analysis of splines for periodic problems using lattice designs, Monte Carlo and quasi-Monte Carlo methods 2004, Springer, Berlin, 2006, pp. 501–514. MR 2208728, DOI 10.1007/3-540-31186-6_{3}1
Xiaoyan Zeng, Peter Kritzer, and Fred J. Hickernell, Spline methods using integration lattices and digital nets, Constr. Approx. 30 (2009), no. 3, 529–555. MR 2558692, DOI 10.1007/s00365-009-9072-0