×

Recycling samples in the multigrid multilevel (quasi-)Monte Carlo method. (English) Zbl 1437.65007

Summary: The multilevel Monte Carlo method is an efficient variance reduction technique. It uses a sequence of coarse approximations to reduce the computational cost in uncertainty quantification applications. The method is nowadays often considered to be the method of choice for solving PDEs with random coefficients when many uncertainties are involved. When using full multigrid to solve the deterministic problem, coarse solutions obtained by the solver can be recycled as samples in the multilevel Monte Carlo method, as was pointed out by P. Kumar, C. W. Oosterlee and R. P. Dwight [“A multigrid multilevel Monte Carlo method using high-order finite-volume scheme for lognormal diffusion problems”, Int. J. Uncertain. Quantif. 7, No. 1, 57–81 (2017; doi:10.1615/Int.J.UncertaintyQuantification.2016018677)]. In this article, an alternative approach is considered, using quasi-Monte Carlo points, to speed up convergence. Additionally, our method comes with an improved variance estimate which is also valid in case of the Monte Carlo based approach. The new method is illustrated on the example of an elliptic PDE with lognormal diffusion coefficient. Numerical results for a variety of random fields with different smoothness parameters in the Matérn covariance function show that sample recycling is more efficient when the input random field is nonsmooth.

MSC:

65C30 Numerical solutions to stochastic differential and integral equations
65C05 Monte Carlo methods
35R60 PDEs with randomness, stochastic partial differential equations
60H15 Stochastic partial differential equations (aspects of stochastic analysis)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] K. Atkinson and W. Han, Numerical solution of Fredholm integral equations of the second kind, in Theoretical Numerical Analysis, Texts in Applied Mathematics, Vol. 39, Springer, New York, NY, 2009, pp. 473-549, https://doi.org/10.1007/978-1-4419-0458-4_12. · Zbl 1181.47078
[2] A. Barth, C. Schwab, and N. Zollinger, Multi-level Monte Carlo finite element method for elliptic PDEs with stochastic coefficients, Numerische Mathematik, 119 (2011), pp. 123-161, https://doi.org/10.1007/s00211-011-0377-0. · Zbl 1230.65006
[3] W. Briggs, V. Henson, and S. McCormick, A Multigrid Tutorial, 2nd ed., SIAM, Philadelphia, PA, 2000, https://doi.org/10.1137/1.9780898719505. · Zbl 0958.65128
[4] 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. Visualization Sci., 14 (2011), pp. 3-15, https://doi.org/10.1007/s00791-011-0160-x. · Zbl 1241.65012
[5] G. Detommaso, T. Dodwell, and R. Scheichl, Continuous Level Monte Carlo and Sample-Adaptive Model Hierarchies, preprint, , 2018. · Zbl 07003658
[6] J. Dick, F. Y. Kuo, and I. H. Sloan, High-dimensional integration: The quasi-Monte Carlo way, Acta Numerica, 22 (2013), pp. 133-288, https://doi.org/10.1017/S0962492913000044. · Zbl 1296.65004
[7] 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
[8] M. Eigel, C. Merdon, and J. Neumann, An adaptive multilevel Monte Carlo method with stochastic bounds for quantities of interest with uncertain data, SIAM/ASA J. Uncertain. Quantif., 4 (2016), pp. 1219-1245, https://doi.org/10.1137/15M1016448. · Zbl 1398.35306
[9] D. Elfverson, F. Hellman, and A. M\aalqvist, A multilevel Monte Carlo method for computing failure probabilities, SIAM/ASA J. Uncertain. Quantif., 4 (2016), pp. 312-330, https://doi.org/10.1137/140984294. · Zbl 1343.65004
[10] O. G. Ernst, C. E. Powell, D. J. Silvester, and E. Ullmann, Efficient solvers for a linear stochastic Galerkin mixed formulation of diffusion problems with random data, SIAM J. Sci. Comput., 31 (2009), pp. 1424-1447, https://doi.org/10.1137/070705817. · Zbl 1187.35298
[11] R. G. Ghanem and P. D. Spanos, Stochastic Finite Elements: A Spectral Approach, Springer, New York, NY, 1991, https://doi.org/10.1007/978-1-4612-3094-6. · Zbl 0722.73080
[12] M. B. Giles, Multilevel Monte Carlo path simulation, Oper. Res., 56 (2008), pp. 607-617, https://doi.org/10.1287/opre.1070.0496. · Zbl 1167.65316
[13] M. B. Giles, Multilevel Monte Carlo methods, Acta Numerica, 24 (2015), pp. 259-328, https://doi.org/10.1017/S096249291500001X. · Zbl 1316.65010
[14] M. B. Giles and B. J. Waterhouse, Multilevel quasi-Monte Carlo path simulation, in Advanced Financial Modelling, Radon Series on Computational and Applied Mathematics, 2009, pp. 165-181, https://doi.org/10.1515/9783110213140.165. · Zbl 1181.91335
[15] I. Graham, F. Kuo, D. Nuyens, R. Scheichl, and I. 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
[16] 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), pp. 3668-3694, https://doi.org/10.1016/j.jcp.2011.01.023. · Zbl 1218.65009
[17] W. Hackbusch, Multi-Grid Methods and Applications, Springer-Verlag, Berlin, Heidelberg, 1985, https://doi.org/10.1007/978-3-662-02427-0. · Zbl 0595.65106
[18] W. Hackbusch, Iterative Solution of Large Sparse Systems of Equations, Springer-Verlag, New York, 1994, https://doi.org/10.1007/978-3-319-28483-5. · Zbl 0789.65017
[19] A.-L. Haji-Ali, F. Nobile, and R. Tempone, Multi-index Monte Carlo: When sparsity meets sampling, Numerische Mathematik, 132 (2016), pp. 767-806, https://doi.org/10.1007/s00211-015-0734-5. · Zbl 1339.65009
[20] A.-L. Haji-Ali, F. Nobile, E. von Schwerin, and R. Tempone, Optimization of mesh hierarchies in multilevel Monte Carlo samplers, Stoch. Partial Differ. Equ. Anal. Comput., 4 (2016), pp. 76-112, https://doi.org/10.1007/s40072-015-0049-7. · Zbl 1359.65013
[21] H. Hoel, E. Von Schwerin, A. Szepessy, and R. Tempone, Adaptive multilevel Monte Carlo simulation, in Numerical Analysis of Multiscale Computations, Springer-Verlag, Berlin, Heidelberg, 2012, pp. 217-234, https://doi.org/10.1007/978-3-642-21943-6_10. · Zbl 1245.65002
[22] P. Kumar, C. W. Oosterlee, and R. P. Dwight, A multigrid multilevel Monte Carlo method using high-order finite-volume scheme for lognormal diffusion problems, Int. J. Uncertain. Quantif., 7 (2017), pp. 57-81, https://doi.org/10.1615/Int.J.UncertaintyQuantification.2016018677. · Zbl 1498.65190
[23] P. Kumar, C. Rodrigo, F. J. Gaspar, and C. W. Oosterlee, On Cell-Centered Multigrid Methods and Local Fourier Analysis for PDEs with Random Coefficients, preprint, , 2018.
[24] F. Y. Kuo and D. 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), pp. 1631-1696, https://doi.org/10.1007/s10208-016-9329-5. · Zbl 1362.65015
[25] 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), pp. 2827-2860, https://doi.org/10.1090/mcom/3207. · Zbl 1368.65005
[26] F. Y. Kuo, C. 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), pp. 1-37, https://doi.org/10.1017/S1446181112000077. · Zbl 1248.65001
[27] O. Le Ma\^\itre and O. M. Knio, Spectral Methods for Uncertainty Quantification: With Applications to Computational Fluid Dynamics, Springer Science & Business Media, 2010, https://doi.org/10.1007/978-90-481-3520-2. · Zbl 1193.76003
[28] H. Niederreiter, Random Number Generation and Quasi-Monte Carlo Methods, SIAM, Philadelphia, PA, 1992, https://doi.org/10.1137/1.9781611970081. · Zbl 0761.65002
[29] 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), pp. 903-920, https://doi.org/10.1090/s0025-5718-06-01785-6. · Zbl 1094.65004
[30] D. Nuyens and F. Y. Kuo, QMC4PDE: A Practical Guide to the Software for Constructing Point Sets and Point Generator Code, 2016, https://people.cs.kuleuven.be/ dirk.nuyens/qmc4pde/.
[31] C.-h. Rhee and P. W. Glynn, Unbiased estimation with square root convergence for SDE models, Oper. Res., 63 (2015), pp. 1026-1043, https://doi.org/10.1287/opre.2015.1404. · Zbl 1347.65016
[32] P. Robbe, A Practical Multilevel Quasi-Monte Carlo Method for Elliptic PDEs with Random Coefficients, master thesis, “Een Parallelle Multilevel Monte-Carlo-Methode voor de Simulatie van Stochastische Partiële Differentiaalvergelijkingen”, Nuyens, D. and Vandewalle, S. (supervisors), 2016.
[33] P. Robbe, MultilevelEstimators.jl: Multilevel Monte Carlo for Julia, 2018, https://github.com/PieterjanRobbe/MultilevelEstimators.jl.
[34] P. Robbe, D. Nuyens, and S. Vandewalle, A multi-index quasi-Monte Carlo algorithm for lognormal diffusion problems, SIAM J. Sci. Comput., 39 (2017), pp. S851-S872, https://doi.org/10.1137/16M1082561. · Zbl 1386.60225
[35] P. Robbe, D. Nuyens, and S. Vandewalle, A dimension-adaptive multi-index Monte Carlo method applied to a model of a heat exchanger, in Monte Carlo and Quasi-Monte Carlo Methods, A. B. Owen and P. W. Glynn, eds., Springer International Publishing, New York, 2018, pp. 429-445. · Zbl 1407.80013
[36] J. Ruge and K. Stüben, Algebraic multigrid methods (AMG), in Multigrid Methods, Frontiers in Applied Mathematics 5, SIAM, Philadelphia, 1987, https://doi.org/10.1137/1.9781611971057.ch4. · Zbl 0659.65094
[37] Y. Saad, Iterative Methods for Sparse Linear Systems, SIAM, Philadelphia, 2003, https://doi.org/10.1137/1.9780898718003. · Zbl 1031.65046
[38] I. H. Sloan and S. Joe, Lattice Methods for Multiple Integration, Oxford University Press, New York and Oxford, 1994, https://doi.org/10.1137/1038021. · Zbl 0855.65013
[39] I. Sobol, On the distribution of points in a cube and the approximate evaluation of integrals, USSR Comput. Math. Math. Phys., 7 (1967), pp. 86-112, https://doi.org/10.1016/0041-5553(67)90144-9. · Zbl 0185.41103
[40] U. Trottenberg, C. W. Oosterlee, and A. Schuller, Multigrid, Academic Press Inc., San Diego, 2000.
[41] H. Van Emden and U. M. Yang, BoomerAMG: A parallel algebraic multigrid solver and preconditioner, Appl. Numer. Math., 41 (2002), pp. 155-177, https://doi.org/10.1016/S0168-9274(01)00115-5. · Zbl 0995.65128
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.