Multilevel hierarchical decomposition of finite element white noise with application to multilevel Markov chain Monte Carlo. (English) Zbl 1476.62012
Summary: In this work we develop a new hierarchical multilevel approach to generate Gaussian random field realizations in an algorithmically scalable manner that is well suited to incorporating into multilevel Markov chain Monte Carlo (MCMC) algorithms. This approach builds off of other partial differential equation (PDE) approaches for generating Gaussian random field realizations; in particular, a single field realization may be formed by solving a reaction-diffusion PDE with a spatial white noise source function as the right-hand side. While these approaches have been explored to accelerate forward uncertainty quantification tasks, e.g., multilevel Monte Carlo, the previous constructions are not directly applicable to multilevel MCMC frameworks which build fine-scale random fields in a hierarchical fashion from coarse-scale random fields. Our new hierarchical multilevel method relies on a hierarchical decomposition of the white noise source function in \(L^2\) which allows us to form Gaussian random field realizations across multiple levels of discretization in a way that fits into multilevel MCMC algorithmic frameworks. After presenting our main theoretical results and numerical scaling results to showcase the utility of this new hierarchical PDE method for generating Gaussian random field realizations, this method is tested on a four-level MCMC algorithm to explore its feasibility.
MSC:
| 62-08 | Computational methods for problems pertaining to statistics |
| 62M30 | Inference from spatial processes |
| 65C40 | Numerical analysis or methods applied to Markov chains |
| 35R60 | PDEs with randomness, stochastic partial differential equations |
| 60H40 | White noise theory |
Keywords:
Gaussian random field; nonlinear Bayesian inference; Markov chain Monte Carlo; multilevel Markov chain Monte Carlo; high-dimensional uncertainty quantification; algebraic multigridReferences:
| [1] | GLVis: OpenGL Finite Element Visualization Tool, http://glvis.org. |
| [2] | HYPRE: High Performance Preconditioners, http://www.llnl.gov/CASC/hypre/. · Zbl 1056.65046 |
| [3] | MFEM: Modular Finite Element Methods Library, http://mfem.org. · Zbl 1524.65001 |
| [4] | ParELAG: Element-Agglomeration Algebraic Multigrid and Upscaling Library, version 2.0, http://github.com/LLNL/parelag, 2015. |
| [5] | ParELAGMC: Parallel Element Agglomeration Multilevel Monte Carlo Library, http://github.com/LLNL/parelagmc, 2018. |
| [6] | R.J. Adler and J.E. Taylor, Random Fields and Geometry, Springer, New York, 2009. · Zbl 1149.60003 |
| [7] | R.J. Adler, J.E. Taylor, and K.J. Worsley, Applications of random fields and geometry: Foundations and case studies, in preparation. |
| [8] | R. Anderson, J. Andrej, A. Barker, J. Bramwell, J.-S. Camier, J. Cerveny V. Dobrev, Y. Dudouit, A. Fisher, Tz. Kolev, W. Pazner, M. Stowell, V. Tomov, I. Akkerman, J. Dahm, D. Medina, and S. Zampini, MFEM: A modular finite element library, Comput. Math. Appl., 81 (2021), pp. 42-74. · Zbl 1524.65001 |
| [9] | A. Barth, C. Schwab, and N. Zollinger, Multi-level Monte Carlo finite element method for elliptic PDEs with stochastic coefficients, Numer. Math., 119 (2011), pp. 123-161. · Zbl 1230.65006 |
| [10] | M. Bebendorf, Hierarchical Matrices, Springer, Berlin, 2008. · Zbl 1151.65090 |
| [11] | A. Beskos, M. Girolami, S. Lan, P.E. Farrell, and A.M. Stuart, Geometric MCMC for infinite-dimensional inverse problems, J. Comput. Phys., 335 (2017), pp. 327-351. · Zbl 1375.35627 |
| [12] | T. Bui-Thanh, O. Ghattas, J. Martin, and G. Stadler, A computational framework for infinite-dimensional Bayesian inverse problems part I: The linearized case, with application to global seismic inversion, SIAM J. Sci. Comput., 35 (2013), pp. A2494-A2523, https://doi.org/10.1137/12089586X. · Zbl 1287.35087 |
| [13] | T. Bui-Thanh and M.A. Girolami, Solving large-scale PDE-constrained Bayesian inverse problems with Riemann manifold Hamiltonian Monte Carlo, Inverse Problems, 30 (2014), 114014. · Zbl 1306.65269 |
| [14] | J.A. Christen and C. Fox, Markov chain Monte Carlo using an approximation, J. Comput. Graph. Statist., 14 (2005), pp. 795-810. |
| [15] | 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 |
| [16] | S.L. Cotter, G.O. Roberts, A.M. Stuart, and D. White, MCMC methods for functions: Modifying old algorithms to make them faster, Statist. Sci., 28 (2013), pp. 424-446. · Zbl 1331.62132 |
| [17] | 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 |
| [18] | T. Cui, G. Detommaso, and R. Scheichl, Multilevel Dimension-Independent Likelihood-Informed MCMC for Large-Scale Inverse Problems, preprint, https://arxiv.org/abs/1910.12431, 2019. |
| [19] | T. Cui, K.J.H. Law, and Y.M. Marzouk, Dimension-independent likelihood-informed MCMC, J. Comput. Phys., 304 (2016), pp. 109-137. · Zbl 1349.65009 |
| [20] | T. Cui, J. Martin, Y.M. Marzouk, A. Solonen, and A. Spantini, Likelihood-informed dimension reduction for nonlinear inverse problems, Inverse Problems, 30 (2014), 114015. · Zbl 1310.62030 |
| [21] | Y. Daon and G. Stadler, Mitigating the influence of the boundary on PDE-based covariance operators, Inverse Probl. Imaging, 12 (2018), pp. 1083-1102. · Zbl 1401.65043 |
| [22] | V. Dobrev, T. Kolev, C.S. Lee, V. Tomov, and P.S. Vassilevski, Algebraic hybridization and static condensation with application to scalable \(H{\text{(div)}}\) preconditioning, SIAM J. Sci. Comput., 41 (2019), pp. B425-B447, https://doi.org/10.1137/17M1132562. · Zbl 1420.65029 |
| [23] | T.J. Dodwell, C. Ketelsen, R. Scheichl, and A.L. Teckentrup, A hierarchical multilevel Markov chain Monte Carlo algorithm with applications to uncertainty quantification in subsurface flow, SIAM/ASA J. Uncertain. Quantif., 3 (2015), pp. 1075-1108, https://doi.org/10.1137/130915005. · Zbl 1330.65007 |
| [24] | D. Drzisga, B. Gmeiner, U. Rüde, R. Scheichl, and B. Wohlmuth, Scheduling massively parallel multigrid for multilevel Monte Carlo methods, SIAM J. Sci. Comput., 39 (2017), pp. S873-S897, https://doi.org/10.1137/16M1083591. · Zbl 1422.65016 |
| [25] | Y. Efendiev, T. Hou, and W. Luo, Preconditioning Markov chain Monte Carlo simulations using coarse-scale models, SIAM J. Sci. Comput., 28 (2006), pp. 776-803, https://doi.org/10.1137/050628568. · Zbl 1111.65003 |
| [26] | H.P. Flath, L.C. Wilcox, V. Akçelik, J. Hill, B. van Bloemen Waanders, and O. Ghattas, Fast algorithms for Bayesian uncertainty quantification in large-scale linear inverse problems based on low-rank partial Hessian approximations, SIAM J. Sci. Comput., 33 (2011), pp. 407-432, https://doi.org/10.1137/090780717. · Zbl 1229.65174 |
| [27] | H. Gahvari, A.H. Baker, M. Schulz, U.M. Yang, K.E. Jordan, and W.D. Gropp, Modeling the performance of an algebraic multigrid cycle on HPC platforms, in Proceedings of the 25th ACM International Conference on Supercomputing, ICS 2011, ACM, New York, 2011, pp. 172-181. |
| [28] | R.G. Ghanem and P.D. Spanos, Stochastic Finite Elements: A Spectral Approach, Springer, New York, 1991. · Zbl 0722.73080 |
| [29] | M.B. Giles, Multilevel Monte Carlo path simulation, Oper. Res., 56 (2008), pp. 607-617. · Zbl 1167.65316 |
| [30] | M.B. Giles, Multilevel Monte Carlo methods, in Monte Carlo and Quasi-Monte Carlo Methods 2012, Springer, Heidelberg, 2013, pp. 83-103. · Zbl 1302.65004 |
| [31] | 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 |
| [32] | W.K. Hastings, Monte Carlo sampling methods using Markov chains and their applications, Biometrika, 57 (1970), pp. 97-109. · Zbl 0219.65008 |
| [33] | S. Heinrich, Multilevel Monte Carlo methods, in Large-Scale Scientific Computing, Springer, New York, 2001, pp. 58-67. · Zbl 1031.65005 |
| [34] | D. Higdon, H. Lee, and Z. Bi, A Bayesian approach to characterizing uncertainty in inverse problems using coarse and fine-scale information, IEEE Trans. Signal Process., 50 (2002), pp. 389-399. · Zbl 1369.62047 |
| [35] | V.H. Hoang, J.H. Quek, and C. Schwab, Analysis of multilevel Markov chain Monte Carlo finite element method for Bayesian inversion of log-normal diffusions, Inverse Problems, 36 (2020), 035021. · Zbl 1491.65010 |
| [36] | J.D. Jansen, R.M. Fonseca, S. Kahrobaei, M.M. Siraj, G.M. Van Essen, and P.M.J. Van den Hof, The egg model-a geological ensemble for reservoir simulation, Geosci. Data J., 1 (2014), pp. 192-195. |
| [37] | 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 |
| [38] | C.S. Lee and P.S. Vassilevski, Parallel solver for H(div) problems using hybridization and AMG, in Domain Decomposition Methods in Science and Engineering XXIII, Springer, New York, 2017, pp. 69-80. · Zbl 1367.65172 |
| [39] | 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 |
| [40] | J. Martin, L.C. Wilcox, C. Burstedde, and O. Ghattas, A stochastic Newton MCMC method for large-scale statistical inverse problems with application to seismic inversion, SIAM J. Sci. Comput., 34 (2012), pp. A1460-A1487, https://doi.org/10.1137/110845598. · Zbl 1250.65011 |
| [41] | N. Metropolis, A.W. Rosenbluth, M.N. Rosenbluth, A.H. Teller, and E. Teller, Equation of state calculations by fast computing machines, J. Chem. Phys., 21 (1953), pp. 1087-1092. · Zbl 1431.65006 |
| [42] | S. Osborn, P.S. Vassilevski, and U. Villa, A multilevel, hierarchical sampling technique for spatially correlated random fields, SIAM J. Sci. Comput., 39 (2017), pp. S543-S562, https://doi.org/10.1137/16M1082688. · Zbl 1422.65406 |
| [43] | 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 nonmatching meshes, Numer. Linear Algebra Appl., 25 (2018), e2146. · Zbl 1499.65006 |
| [44] | N. Petra, J. Martin, G. Stadler, and O. Ghattas, A computational framework for infinite-dimensional Bayesian inverse problems, part II: Stochastic Newton MCMC with application to ice sheet flow inverse problems, SIAM J. Sci. Comput., 36 (2014), pp. A1525-A1555, https://doi.org/10.1137/130934805. · Zbl 1303.35110 |
| [45] | C. Robert and G. Casella, Monte Carlo Statistical Methods, 2nd ed., Springer, New York, 2004. · Zbl 1096.62003 |
| [46] | L. Roininen, J.M.J. Huttunen, and S. Lasanen, Whittle-Matérn priors for Bayesian statistical inversion with applications in electrical impedance tomography, Inverse Probl. Imaging, 8 (2014), pp. 561-586. · Zbl 1302.65245 |
| [47] | A. Sokal, Monte Carlo methods in statistical mechanics: Foundations and new algorithms, in Functional Integration, Springer, New York, 1997, pp. 131-192. · Zbl 0890.65006 |
| [48] | A.M. Stuart, Inverse problems: A Bayesian perspective, Acta Numer., 19 (2010), pp. 451-559. · Zbl 1242.65142 |
| [49] | 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 |
| [50] | The Trilinos Project Team, The Trilinos Project Website, https://trilinos.github.io/. · Zbl 1136.65354 |
| [51] | P. Whittle, Stochastic processes in several dimensions, B. Inst. Internat. Statist., 40 (1963), pp. 974-994. · Zbl 0129.10603 |
| [52] | C. Williams, K.I. Christopher, and M. Seeger, Using the Nyström method to speed up kernel machines, in Advances in Neural Information Processing Systems, NeurIPS, San Diego, CA, 2001, pp. 682-688. |
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.
