Multilevel quasi-Monte Carlo integration with product weights for elliptic PDEs with lognormal coefficients

Herrmann, L.; Schwab, C.

ESAIM: Mathematical Modelling and Numerical Analysis , Tome 53 (2019) no. 5, pp. 1507-1552.

Suite au passage du modèle économique de la revue en S20, le texte intégral des articles des années 2019 et 2020 est accessible uniquement sur le site de l'éditeur et est réservé aux abonnés.

We analyze the convergence rate of a multilevel quasi-Monte Carlo (MLQMC) Finite Element Method (FEM) for a scalar diffusion equation with log-Gaussian, isotropic coefficients in a bounded, polytopal domain D ⊂ ℝ^d. The multilevel algorithm $Q_L^{*}$ which we analyze here was first proposed, in the case of parametric PDEs with sequences of independent, uniformly distributed parameters in Kuo et al. (Found. Comput. Math. 15 (2015) 411–449). The random coefficient is assumed to admit a representation with locally supported coefficient functions, as arise for example in spline- or multiresolution representations of the input random field. The present analysis builds on and generalizes our single-level analysis in Herrmann and Schwab (Numer. Math. 141 (2019) 63–102). It also extends the MLQMC error analysis in Kuo et al. (Math. Comput. 86 (2017) 2827–2860), to locally supported basis functions in the representation of the Gaussian random field (GRF) in D, and to product weights in QMC integration. In particular, in polytopal domains D ⊂ ℝ^d, d=2,3, our analysis is based on weighted function spaces to describe solution regularity with respect to the spatial coordinates. These spaces allow GRFs and PDE solutions whose realizations become singular at edges and vertices of D. This allows for non-stationary GRFs whose covariance operators and associated precision operator are fractional powers of elliptic differential operators in D with boundary conditions on ∂D. In the weighted function spaces in D, first order, Lagrangian Finite Elements on regular, locally refined, simplicial triangulations of D yield optimal asymptotic convergence rates. Comparison of the ε-complexity for a class of Matérn-like GRF inputs indicates, for input GRFs with low sample regularity, superior performance of the present MLQMC-FEM with locally supported representation functions over alternative representations, e.g. of Karhunen–Loève type. Our analysis yields general bounds for the ε-complexity of the MLQMC algorithm, uniformly with respect to the dimension of the parameter space.

[1] R.J. Adler, The geometry of random fields. In: Wiley Series in Probability and Mathematical Statistics. John Wiley & Sons Ltd., Chichester (1981). | MR | Zbl

[2] J.H. Adler and V. Nistor, Graded mesh approximation in weighted Sobolev spaces and elliptic equations in 2D. Math. Comput. 84 (2015) 2191–2220. | DOI | MR | Zbl

[3] T. Apel, A.L. Lombardi and M. Winkler, Anisotropic mesh refinement in polyhedral domains: error estimates with data in L² (Ω). ESAIM: M2AN 48 (2014) 1117–1145. | DOI | Numdam | MR | Zbl

[4] T. Apel, J. Pfefferer and M. Winkler, Local mesh refinement for the discretization of Neumann boundary control problems on polyhedra. Math. Methods Appl. Sci. 39 (2016) 1206–1232. | DOI | MR | Zbl

[5] I. Babuška, R. Bruce Kellogg and J. Pitkäranta, Direct and inverse error estimates for finite elements with mesh refinements. Numer. Math. 33 (1979) 447–471. | DOI | MR | Zbl

[6] M. Bachmayr, A. Cohen, D. Dũng and C. Schwab, Fully discrete approximation of parametric and stochastic elliptic PDEs. SIAM J. Numer. Anal. 55 (2017) 2151–2186. | DOI | MR | Zbl

[7] M. Bachmayr, A. Cohen, R. Devore and G. Migliorati, Sparse polynomial approximation of parametric elliptic PDEs. part II: lognormal coefficients. ESAIM: M2AN 51 (2017) 341–363. | DOI | Numdam | MR | Zbl

[8] M. Bachmayr, A. Cohen and G. Migliorati, Representations of Gaussian random fields and approximation of elliptic PDEs with lognormal coefficients. J. Fourier Anal. Appl. 24 (2018) 621–649. | DOI | MR | Zbl

[9] L. Banjai, J.M. Melenk, R.H. Nochetto, E. Otarola, A.J. Salgado and C. Schwab, Tensor FEM for spectral fractional diffusion. Found. Comput. Math. DOI: (2018). | DOI | MR | Zbl

[10] V.I. Bogachev, Gaussian Measures. Vol. 62 of Mathematical Surveys and Monographs. American Mathematical Society, Providence, RI (1998). | MR | Zbl

[11] J.H. Bramble, Multigrid methods. In: Vol. 294 of Pitman Research Notes in Mathematics Series. Longman Scientific & Technical, Harlow; copublished in the United States with John Wiley & Sons, Inc., New York, NY (1993). | MR | Zbl

[12] J. Charrier, Strong and weak error estimates for elliptic partial differential equations with random coefficients. SIAM J. Numer. Anal. 50 (2012) 216–246. | DOI | MR | Zbl

[13] P.G. Ciarlet, Linear and Nonlinear Functional Analysis With Applications. Society for Industrial and Applied Mathematics, Philadelphia, PA (2013). | DOI | MR | Zbl

[14] J. Dick, F.Y. Kuo and I.H. Sloan, High-dimensional integration: the quasi-Monte Carlo way. Acta Numer. 22 (2013) 133–288. | DOI | MR | Zbl

[15] J. Dick, F.Y. Kuo, Q.T. Le Gia, D. Nuyens and C. Schwab, Higher order QMC Petrov-Galerkin discretization for affine parametric operator equations with random field inputs. SIAM J. Numer. Anal. 52 (2014) 2676–2702. | DOI | MR | Zbl

[16] C.R. Dietrich and G.N. Newsam, Fast and exact simulation of stationary Gaussian processes through circulant embedding of the covariance matrix. SIAM J. Sci. Comput. 18 (1997) 1088–1107. | DOI | MR | Zbl

[17] M.M. Dunlop, M.A. Girolami, A.M. Stuart and A.L. Teckentrup, How deep are deep Gaussian processes? J. Mach. Learn. Res. 19 (2018) 54. | MR | Zbl

[18] G.-A. Fuglstad, F. Lindgren, D. Simpson and H. Rue, Exploring a new class of non-stationary spatial Gaussian random fields with varying local anisotropy. Statist. Sinica 25 (2015) 115–133. | MR | Zbl

[19] R.N. Gantner, L. Herrmann and C. Schwab, Multilevel QMC with product weights for affine-parametric, elliptic PDEs, edited by J. Dick, F.Y. Kuo, H. Woz'Niakowski. In: Contemporary Computational Mathematics – A Celebration of the 80th Birthday of Ian Sloan. Springer International Publishing, Cham (2018) 373–405. | DOI | MR | Zbl

[20] R.N. Gantner, L. Herrmann and C. Schwab, Quasi-Monte Carlo integration for affine-parametric, elliptic PDEs: local supports and product weights. SIAM J. Numer. Anal. 56 (2018) 111–135. | DOI | MR | Zbl

[21] F.D. Gaspoz and P. Morin, Convergence rates for adaptive finite elements. IMA J. Numer. Anal. 29 (2009) 917–936. | DOI | MR | Zbl

[22] A. George, Nested dissection of a regular finite element mesh. SIAM J. Numer. Anal. 10 (1973) 345–363. | DOI | MR | Zbl

[23] C.J. Gittelson, Representation of Gaussian fields in series with independent coefficients. IMA J. Numer. Anal. 32 (2012) 294–319. | DOI | MR | Zbl

[24] G.H. Golub and C.F. Van Loan, Matrix computations, 3rd edition. In: Johns Hopkins Studies in the Mathematical Sciences. Johns Hopkins University Press, Baltimore, MD (1996). | MR | Zbl

[25] I.G. Graham, F.Y. Kuo, D. Nuyens, R. Scheichl and I.H. Sloan, Quasi-Monte Carlo methods for elliptic PDEs with random coefficients and applications. J. Comput. Phys. 230 (2011) 3668–3694. | DOI | MR | Zbl

[26] I.G. Graham, F.Y. Kuo, J.A. Nichols, R. Scheichl, C. Schwab and I.H. Sloan, Quasi-Monte Carlo finite element methods for elliptic PDEs with lognormal random coefficients. Numer. Math. 131 (2015) 329–368. | DOI | MR | Zbl

[27] I.G. Graham, F.Y. Kuo, D. Nuyens, R. Scheichl and I.H. Sloan, Analysis of circulant embedding methods for sampling stationary random fields. SIAM J. Numer. Anal. 56 (2018) 1871–1895. | DOI | MR | Zbl

[28] I.G. Graham, F.Y. Kuo, D. Nuyens, R. Scheichl and I.H. Sloan, Circulant embedding with QMC: analysis for elliptic PDE with lognormal coefficients. Numer. Math. 140 (2018) 479–511. | DOI | MR | Zbl

[29] L. Herrmann, Strong convergence analysis of iterative solvers for random operator equations. Technical Report 2017-35, Seminar for Applied Mathematics, ETH Zürich (2017). | MR

[30] L. Herrmann and C. Schwab, QMC algorithms with product weights for lognormal-parametric, elliptic PDEs. In: Monte Carlo and Quasi-Monte Carlo Methods: MCQMC 2016, Stanford, CA, August 14–19. Vol. 241 of Springer Proc. Math. Stat. Springer, Cham (2018) 313–330. | DOI | MR | Zbl

[31] L. Herrmann and C. Schwab, QMC integration for lognormal-parametric, elliptic PDEs: local supports and product weights. Numer. Math. 141 (2019) 63–102. | DOI | MR | Zbl

[32] L. Herrmann, A. Lang and C. Schwab, Numerical analysis of lognormal diffusions on the sphere. Stochastics Partial Differ. Equ.: Anal. Comput. 6 (2018) 1–44. | MR | Zbl

[33] Y. Kazashi, Quasi-Monte Carlo integration with product weights for elliptic PDEs with log-normal coefficients. IMA J. Numer. Anal. 39 (2019) 1563–1593. | DOI | MR | Zbl

[34] F.Y. Kuo, I.H. Sloan, G.W. Wasilkowski and B.J. Waterhouse, Randomly shifted lattice rules with the optimal rate of convergence for unbounded integrands. J. Complexity 26 (2010) 135–160. | DOI | MR | Zbl

[35] F.Y. Kuo, C. Schwab and I.H. Sloan, Multi-level quasi-Monte Carlo finite element methods for a class of elliptic PDEs with random coefficients. Found. Comput. Math. 15 (2015) 411–449. | DOI | MR | Zbl

[36] F.Y. Kuo, R. Scheichl, C. Schwab, I.H. Sloan and E. Ullmann, Multilevel quasi-Monte Carlo methods for lognormal diffusion problems. Math. Comput. 86 (2017) 2827–2860. | DOI | MR | Zbl

[37] H. Li, An anisotropic finite element method on polyhedral domains: interpolation error analysis. Math. Comput. 87 (2018) 1567–1600. | DOI | MR | Zbl

[38] F. Lindgren, H. Rue and J. Lindström, An explicit link between Gaussian fields and Gaussian Markov random fields: the stochastic partial differential equation approach. J. R. Stat. Soc. Ser. B Stat. Methodol. 73 (2011) 423–498. With discussion and a reply by the authors. | DOI | MR | Zbl

[39] B. Matérn, Spatial variation, 2nd edition. With a Swedish summary. Vol. 36 of Lecture Notes in Statistics. Springer-Verlag, Berlin (1986). | DOI | MR | Zbl

[40] V. Mazya and J. Rossmann, Elliptic equations in polyhedral domains. Vol. 162 of Mathematical Surveys and Monographs. American Mathematical Society, Providence, RI (2010). | DOI | MR | Zbl

[41] J.A. Nichols and F.Y. Kuo, Fast CBC construction of randomly shifted lattice rules achieving $𝒪\left(n^{-1+\delta }\right)$ convergence for unbounded integrands over ${ℝ}^3$ in weighted spaces with POD weights. J. Complexity 30 (2014) 444–468. | DOI | MR | Zbl

[42] D. Nuyens and R. Cools, Fast algorithms for component-by-component construction of rank-1 lattice rules in shift-invariant reproducing kernel Hilbert spaces. Math. Comput. 75 (2006) 903–920. | DOI | MR | Zbl

[43] D. Nuyens and R. Cools, Fast component-by-component construction of rank-1 lattice rules with a non-prime number of points. J. Complexity 22 (2006) 4–28. | DOI | MR | Zbl

[44] N. Rekatsinas and R. Stevenson, A quadratic finite element wavelet Riesz basis. Int. J. Wavelets Multiresolut. Inf. Process. 16 (2018) 1850033. | DOI | MR | Zbl

[45] H. Triebel, Interpolation Theory, Function Spaces, Differential Operators, 2nd edition. Johann Ambrosius Barth, Heidelberg (1995). | MR | Zbl

[46] T. Von Petersdorff and C. Schwab, Wavelet approximations for first kind boundary integral equations on polygons. Numer. Math. 74 (1996) 479–516. | DOI | MR | Zbl

[47] P. Whittle, On stationary processes in the plane. Biometrika 41 (1954) 434–449. | DOI | MR | Zbl

[48] P. Whittle, Stochastic processes in several dimensions. Bull. Inst. Internat. Statist. 40 (1963) 974–994. | MR | Zbl

[49] J. Xu, Iterative methods by space decomposition and subspace correction. SIAM Rev. 34 (1992) 581–613. | DOI | MR | Zbl