×

Multilevel quasi Monte Carlo methods for elliptic PDEs with random field coefficients via fast white noise sampling. (English) Zbl 07385001

Summary: When solving partial differential equations (PDEs) with random fields as coefficients, the efficient sampling of random field realizations can be challenging. In this paper we focus on the fast sampling of Gaussian fields using quasi-random points in a finite element and multilevel quasi Monte Carlo (MLQMC) setting. Our method uses the stochastic PDE (SPDE) approach of Lindgren et al. combined with a new fast algorithm for white noise sampling which is tailored to (ML)QMC. We express white noise as a wavelet series expansion that we divide into two parts. The first part is sampled using quasi-random points and contains a finite number of terms in order of decaying importance to ensure good quasi Monte Carlo (QMC) convergence. The second part is a correction term which is sampled using standard pseudo-random numbers. We show how the sampling of both terms can be performed in linear time and memory complexity in the number of mesh cells via a supermesh construction, yielding an overall linear cost. Furthermore, our technique can be used to enforce the MLQMC coupling even in the case of nonnested mesh hierarchies. We demonstrate the efficacy of our method with numerical experiments.

MSC:

65C05 Monte Carlo methods
60G60 Random fields
65N30 Finite element, Rayleigh-Ritz and Galerkin methods for boundary value problems involving PDEs
60H35 Computational methods for stochastic equations (aspects of stochastic analysis)
35R60 PDEs with randomness, stochastic partial differential equations
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] M. Bachmayr, I. G. Graham, V. K. Nguyen, and R. Scheichl, Unified Analysis of Periodization-Based Sampling Methods for Matérn Covariances, preprint, https://arxiv.org/abs/1905.13522, 2019. · Zbl 1471.60047
[2] S. Balay, S. Abhyankar, M. Adams, J. Brown, P. R. Brune, K. Buschelman, V. Eijkhout, W. Gropp, D. Kaushik, M. G. Knepley, et al., PETSc Users Manual Revision 3.8, Tech. Report, Argonne National Laboratory (ANL), Lemont, IL, 2017.
[3] G. Beylkin, R. Coifman, and V. Rokhlin, Wavelets in numerical analysis, in Wavelets and Their Applications, Jones & Bartlett, Boston, MA, 1992, pp. 181-210. · Zbl 0798.65126
[4] D. Bolin and K. Kirchner, The SPDE Approach for Gaussian Random Fields with General Smoothness, preprint, https://arxiv.org/abs/1711.04333v1, 2017.
[5] D. Bolin, K. Kirchner, and M. Kovács, Numerical solution of fractional elliptic stochastic PDEs with spatial white noise, IMA J. Numer. Anal., 40 (2020), pp. 1051-1073. · Zbl 1466.65181
[6] S. Brenner and R. L. Scott, The Mathematical Theory of Finite Element Methods, Texts Appl. Math. 15, Springer, New York, 1994. · Zbl 0804.65101
[7] R. E. Caflish, W. Morokoff, and A. Owen, Valuation of mortgage-backed securities using Brownian bridges to reduce effective dimension, J. Comput. Finance, 1 (1997), pp. 27-46.
[8] J. Charrier, R. Scheichl, and A. L. Teckentrup, Finite element error analysis of elliptic PDEs with random coefficients and its application to multilevel Monte Carlo methods, SIAM J. Numer. Anal., 51 (2013), pp. 322-352, https://doi.org/10.1137/110853054. · Zbl 1273.65008
[9] K. A. Cliffe, M. B. Giles, R. Scheichl, and A. L. Teckentrup, Multilevel Monte Carlo methods and applications to elliptic PDEs with random coefficients, Comput. Vis. Sci., 14 (2011), pp. 3-15. · Zbl 1241.65012
[10] M. Croci, Multilevel Monte Carlo Methods for Uncertainty Quantification in Brain Simulations, Ph.D. thesis, University of Oxford, Oxford, UK, 2019.
[11] M. Croci and P. E. Farrell, Complexity bounds on supermesh construction for quasi-uniform meshes, J. Comput. Phys., 414 (2020), pp. 1-7. · Zbl 1440.65015
[12] M. Croci, M. B. Giles, M. E. Rognes, and P. E. Farrell, Efficient white noise sampling and coupling for multilevel Monte Carlo with nonnested meshes, SIAM/ASA J. Uncertain. Quantif., 6 (2018), pp. 1630-1655, https://doi.org/10.1137/18M1175239. · Zbl 07003649
[13] M. Croci, V. Vinje, and M. E. Rognes, Fast uncertainty quantification of tracer distribution in the brain interstitial fluid with multilevel and quasi Monte Carlo, Internat. J. Numer. Methods Biomed. Engrg., 37 (2021), e3412, https://doi.org/10.1002/cnm.3412.
[14] I. Daubechies, Orthonormal bases of compactly supported wavelets, Comm. Pure Appl. Math., 41 (1988), pp. 909-996. · Zbl 0644.42026
[15] J. Dick, F. Y. Kuo, and I. H. Sloan, High-dimensional integration: The quasi-Monte Carlo way, Acta Numer., 22 (2013), pp. 133-288. · Zbl 1296.65004
[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), pp. 1088-1107, https://doi.org/10.1137/S1064827592240555. · Zbl 0890.65149
[17] J. Dölz, H. Harbrecht, and C. Schwab, Covariance regularity and \(\mathcal{H} \)-matrix approximation for rough random fields, Numer. Math., 135 (2017), pp. 1045-1071. · Zbl 1362.65124
[18] R. D. Falgout and U. M. Yang, hypre: A library of high performance preconditioners, in International Conference on Computational Science, Springer, New York, 2002, pp. 632-641. · Zbl 1056.65046
[19] P. E. Farrell, Galerkin Projection of Discrete Fields via Supermesh Construction, Ph.D. thesis, Imperial College London, London, 2009.
[20] P. E. Farrell and J. R. Maddison, Conservative interpolation between volume meshes by local Galerkin projection, Comput. Methods Appl. Mech. Engrg., 200 (2011), pp. 89-100. · Zbl 1225.76193
[21] P. E. Farrell, M. D. Piggott, C. C. Pain, G. J. Gorman, and C. R. Wilson, Conservative interpolation between unstructured meshes via supermesh construction, Comput. Methods Appl. Mech. Engrg., 198 (2009), pp. 2632-2642. · Zbl 1228.76105
[22] M. Feischl, F. Y. Kuo, and I. H. Sloan, Fast random field generation with H-matrices, Numer. Math., 140 (2018), pp. 639-676. · Zbl 1404.65033
[23] M. B. Giles, Multilevel Monte Carlo path simulation, Oper. Res., 56 (2008), pp. 607-617. · Zbl 1167.65316
[24] M. B. Giles, Multilevel Monte Carlo methods, Acta Numer., 24 (2015), pp. 259-328. · Zbl 1316.65010
[25] M. B. Giles and B. J. Waterhouse, Multilevel quasi-Monte Carlo path simulation, in Advanced Financial Modelling, Radon Ser. Comput. Appl. Math. 8, De Gruyter, Berlin, 2009, pp. 165-181. · Zbl 1181.91335
[26] P. Glasserman, Monte Carlo Methods in Financial Engineering, Springer, New York, 2004. · Zbl 1038.91045
[27] I. Graham, F. Kuo, D. Nuyens, R. Scheichl, and I. Sloan, Quasi-Monte Carlo methods for elliptic PDEs with random coefficients and applications, J. Comput. Phys., 230 (2011), pp. 3668-3694. · Zbl 1218.65009
[28] 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 log-normal random coefficients, Numer. Math., 131 (2013), pp. 329-368. · Zbl 1341.65003
[29] 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), pp. 1871-1895, https://doi.org/10.1137/17M1149730. · Zbl 1434.60114
[30] 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), pp. 479-511, https://doi.org/10.1007/s00211-018-0968-0. · Zbl 1417.65203
[31] W. Hackbusch, Elliptic Differential Equations: Theory and Numerical Treatment, Springer-Verlag, New York, 1992. · Zbl 0755.35021
[32] W. Hackbusch, Hierarchical Matrices: Algorithms and Analysis, Springer, New York, 2015. · Zbl 1336.65041
[33] S. Heinrich, Multilevel Monte Carlo methods, in Large-Scale Scientific Computing, Springer, Berlin, Heidelberg, 2001, pp. 58-67. · Zbl 1031.65005
[34] L. Herrmann and C. Schwab, Multilevel quasi-Monte Carlo integration with product weights for elliptic PDEs with lognormal coefficients, ESAIM Math. Model. Numer. Anal., 53 (2019), pp. 1507-1552. · Zbl 07135561
[35] T. Hida, H.-H. Kuo, J. Potthoff, and L. Streit, White Noise: An Infinite Dimensional Calculus, Springer, Dorcrecht, The Netherlands, 1993. · Zbl 0771.60048
[36] H. Inaba and B. D. Tapley, Generalized random processes: A theory and the white Gaussian process, SIAM J. Control, 13 (1975), pp. 719-735, https://doi.org/10.1137/0313041. · Zbl 0272.60038
[37] K. Itô, Stationary random distributions, Mem. College Sci. Univ. Kyoto Ser. A Math., 28 (1954), pp. 209-223. · Zbl 0059.11505
[38] S. Joe and F. Y. Kuo, Constructing Sobol \('\) sequences with better two-dimensional projections, SIAM J. Sci. Comput., 30 (2008), pp. 2635-2654, https://doi.org/10.1137/070709359. · Zbl 1171.65364
[39] B. N. Khoromskij, A. Litvinenko, and H. G. Matthies, Application of hierarchical matrices for computing the Karhunen-Loève expansion, Computing, 84 (2009), pp. 49-67. · Zbl 1162.65306
[40] U. Khristenko, L. Scarabosio, P. Swierczynski, E. Ullmann, and B. Wohlmuth, Analysis of boundary effects on PDE-based sampling of Whittle-Matérn random fields, SIAM/ASA J. Uncertain. Quantif., 7 (2019), pp. 948-974, https://doi.org/10.1137/18M1215700. · Zbl 07118418
[41] F. Y. Kuo, R. Scheichl, C. Schwab, I. H. Sloan, and E. Ullmann, Multilevel quasi-Monte Carlo methods for lognormal diffusion problems, Math. Comp., 86 (2017), pp. 2827-2860. · Zbl 1368.65005
[42] 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), pp. 411-449. · Zbl 1318.65006
[43] C. Lemieux, Monte Carlo and Quasi-Monte Carlo Sampling, Springer Ser. Statist., Springer-Verlag, New York, 2009. · Zbl 1269.65001
[44] 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), pp. 423-498. · Zbl 1274.62360
[45] A. Logg, K.-A. Mardal, and G. Wells, Automated Solution of Differential Equations by the Finite Element Method: The FEniCS Book, Lect. Notes Comput. Sci. Engrg. 84, Springer, Berlin, 2012. · Zbl 1247.65105
[46] J. R. Maddison, P. E. Farrell, and I. Panourgias, Parallel Supermeshing for Multimesh Modelling, Tech. Report eCSE03-08, ARCHER, 2013.
[47] S. Osborn, P. S. Vassilevski, and U. Villa, A Multilevel, Hierarchical Sampling Technique for Spatially Correlated Random Fields, preprint, https://arxiv.org/abs/1703.08498, 2017. · Zbl 1422.65406
[48] S. Osborn, P. Zulian, T. Benson, U. Villa, R. Krause, and P. S. Vassilevski, Scalable hierarchical PDE sampler for generating spatially correlated random fields using non-matching meshes, Numer. Linear Algebra Appl., 25 (2018), e2146, https://doi.org/10.1002/nla.2146. · Zbl 1499.65006
[49] A. B. Owen, Variance and discrepancy with alternative scramblings, ACM Trans. Model. Comput. Simul., 13 (2003), pp. 363-378. · Zbl 1390.65037
[50] R. Potsepaev and C. L. Farmer, Application of stochastic partial differential equations to reservoir property modelling, in Proceedings of the ECMOR XII-12th European Conference on the Mathematics of Oil Recovery, Vol. 2, 2014.
[51] I. M. Sobol’, D. Asotsky, A. Kreinin, and S. Kucherenko, Construction and comparison of high-dimensional Sobol’ generators, Wilmott, 56 (2011), pp. 64-79.
[52] T. J. Sullivan, Introduction to Uncertainty Quantification, Texts Appl. Math. 63, Springer, Cham, 2015. · Zbl 1336.60002
[53] A. L. Teckentrup, R. Scheichl, M. B. Giles, and E. Ullmann, Further analysis of multilevel Monte Carlo methods for elliptic PDEs with random coefficients, Numer. Math., 125 (2013), pp. 569-600. · Zbl 1306.65009
[54] A. J. Wathen, Realistic eigenvalue bounds for the Galerkin mass matrix, IMA J. Numer. Anal., 7 (1987), pp. 449-457. · Zbl 0648.65076
[55] P. Whittle, On stationary processes in the plane, Biometrika, 41 (1954), pp. 434-449. · Zbl 0058.35601
[56] A. T. A. Wood and G. Chan, Simulation of stationary Gaussian processes in \([0,1]^d\), J. Comput. Graph. Statist., 3 (1994), pp. 409-432.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.