Abstract
In Monte Carlo methods quadrupling the sample size halves the error. In simulations of stochastic partial differential equations (SPDEs), the total work is the sample size times the solution cost of an instance of the partial differential equation. A Multi-level Monte Carlo method is introduced which allows, in certain cases, to reduce the overall work to that of the discretization of one instance of the deterministic PDE. The model problem is an elliptic equation with stochastic coefficients. Multi-level Monte Carlo errors and work estimates are given both for the mean of the solutions and for higher moments. The overall complexity of computing mean fields as well as k-point correlations of the random solution is proved to be of log-linear complexity in the number of unknowns of a single Multi-level solve of the deterministic elliptic problem. Numerical examples complete the theoretical analysis.
Similar content being viewed by others
References
Babuška I., Nobile F., Tempone R.: A stochastic collocation method for elliptic partial differential equations with random input data. SIAM J. Numer. Anal. 45, 1005–1034 (2007, electronic)
Babuška, I., Tempone, R., Zouraris, G.E.: Galerkin Finite Element approximations of stochastic elliptic partial differential equations. SIAM J. Numer. Anal., 42, 800–825 (2004, electronic)
Barth A.: A Finite Element Method for martingale-driven stochastic partial differential equations. Commun. Stoch. Anal. 4, 355–375 (2010)
Barth, A., Lang, A.: Almost sure convergence of a Galerkin–Milstein approximation for stochastic partial differential equations. Tech. Report 2011–15. Seminar for Applied Mathematics, ETH Zurich, March 2009 (in review)
Barth, A., Lang, A.: Simulation of stochastic partial differential equations using Finite Element methods. Stochastics (2010, in press)
Bieri, M., Andreev, R., Schwab, C.: Sparse tensor discretization of elliptic SPDEs. SIAM J. Sci. Comput. 31, 4281–4304 (2009/2010)
Bieri M., Schwab C.: Sparse high order FEM for elliptic sPDEs. Comput. Methods Appl. Mech. Eng. 198, 1149–1170 (2009)
Braess D.: Finite Elemente, 3rd edn. Springer, Berlin (2002)
Brenner S.C., Scott L.R.: The Mathematical Theory of Finite Element Methods, 2nd edn. Springer, Berlin (2002)
Cohen, A.: Numerical analysis of wavelet methods. In: Studies in Mathematics and its Applications. North-Holland, Amsterdam (2003)
Cohen A., DeVore R., Schwab C.: Convergence rates of best n-term approximations for a class of elliptic spdes. Found. Comput. Math. 10, 615–646 (2010)
Cohen A., DeVore R., Schwab C.: Analytic regularity and polynomial approximation of parametric and stochastic elliptic PDEs. J. Anal. Appl. 9, 11–47 (2011)
Da Prato G., Zabczyk J.: Stochastic equations in infinite dimensions. Encyclopedia of Mathematics and its Applications, vol. 44. Cambridge University Press, Cambridge (1992)
Dietrich C.R., Newsam G.N.: Fast and exact simulation of stationary Gaussian processes through circulant embedding of the covariance matrix. SIAM J. Sci. Comput. 18, 1088–1107 (1997)
Geissert M., Kovács M., Larsson S.: Rate of weak convergence of the Finite Element Method for the stochastic heat equation with additive noise. BIT Numer. Math. 49, 343–356 (2009)
Gilbarg D., Trudinger N.S.: Elliptic partial differential equations of second order. In: Classics in Mathematics. Springer, Berlin (2001, reprint of the 1998 edition)
Giles M.: Improved multilevel Monte Carlo convergence using the Milstein scheme. Preprint NA-06/22. Oxford University Computing Laboratory, Parks Road (2006)
Giles M.B.: Multilevel Monte Carlo path simulation. Oper. Res. 56, 607–617 (2008)
Griebel M., Oswald P.: On additive Schwarz preconditioners for sparse grid discretizations. Numer. Math. 66, 449–463 (1994)
Grisvard P.: Elliptic problems in nonsmooth domains. Monographs and Studies in Mathematics, vol. 24. Pitman (Advanced Publishing Program), Boston (1985)
Heinrich, S.: Multilevel Monte Carlo Methods. In: Large-Scale Scientific Computing, Third International Conference, LSSC 2001, Sozopol, Bulgaria, June 6–10, 2001 (Revised Papers, S. Margenov, J. Wasniewski, and P. Y. Yalamov, eds., vol. 2179 of Lecture Notes in Computer Science, Springer, 2001, pp. 58–67)
Kovács M., Larsson S., Saedpanah F.: Finite Element approximation of the linear stochastic wave equation with additive noise. SIAM J. Numer. Anal. 48, 408–427 (2010)
Lang A., Potthoff J.: Fast simulation of Gaussian random fields (2009, in review)
Lions, J.-L., Magenes E.: Non-homogeneous boundary value problems and applications, vol. I. Springer-Verlag, New York (1972). (Translated from the French by P. Kenneth, Die Grundlehren der mathematischen Wissenschaften, Band 181)
Mishra S., Schwab C.: Sparse tensor Multi-Level Monte Carlo Finite Volume Methods for hyperbolic conservation laws with random intitial data. Tech. Report 2010-24. Seminar for Applied Mathematics, ETH Zurich, September 2010 (in review)
Mishra S., Schwab C., Šukys J.: Multi-Level Monte Carlo Finite Volume Mmethods for nonlinear systems of conservation laws in multi-dimensions with random intitial data. Tech. Report 2011-02. Seminar for Applied Mathematics, ETH Zurich, January 2011 (in review)
Naff R.L., Haley D.F., Sudicky E.: High-resolution Monte Carlo simulation of flow and conservative transport in heterogeneous porous media 1. Methodology and flow results. Water Resour. Res. 34, 663–677 (1998)
Naff R.L., Haley D.F., Sudicky E.: High-resolution Monte Carlo simulation of flow and conservative transport in heterogeneous porous media 2. Transport results. Water Resour. Res. 34, 679–697 (1998)
Nobile F., Tempone R., Webster C.G.: An anisotropic sparse grid stochastic collocation method for partial differential equations with random input data. SIAM J. Numer. Anal. 46, 2411–2442 (2008)
Nobile F., Tempone R., Webster C.G.: A sparse grid stochastic collocation method for partial differential equations with random input data. SIAM J. Numer. Anal. 46, 2309–2345 (2008)
Schwab C., Todor R.A.: Sparse Finite Elements for elliptic problems with stochastic loading. Numer. Math. 95, 707–734 (2003)
Schwab C., Todor R.A.: Sparse Finite Elements for stochastic elliptic problems—higher order moments. Computing 71, 43–63 (2003)
Schwab C., Todor R.A.: Karhunen–Loève approximation of random fields by generalized fast multipole methods. J. Comput. Phys. 217, 100–122 (2006)
von Petersdorff T., Schwab C.: Numerical solution of parabolic equations in high dimensions. M2AN Math. Model. Numer. Anal. 38, 93–127 (2004)
Author information
Authors and Affiliations
Corresponding author
Additional information
The authors wish to express their thanks to Roman Andreev and Claude J. Gittelson for fruitful discussions and helpful comments. The research partially supported under ERC AdG Grant STAHDPDE No. 247277.
Rights and permissions
About this article
Cite this article
Barth, A., Schwab, C. & Zollinger, N. Multi-level Monte Carlo Finite Element method for elliptic PDEs with stochastic coefficients. Numer. Math. 119, 123–161 (2011). https://doi.org/10.1007/s00211-011-0377-0
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00211-011-0377-0