Skip to main content
Log in

Multi-level Monte Carlo Finite Element method for elliptic PDEs with stochastic coefficients

Numerische Mathematik Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. 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)

    Google Scholar 

  2. 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)

    Google Scholar 

  3. Barth A.: A Finite Element Method for martingale-driven stochastic partial differential equations. Commun. Stoch. Anal. 4, 355–375 (2010)

    MathSciNet  Google Scholar 

  4. 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)

  5. Barth, A., Lang, A.: Simulation of stochastic partial differential equations using Finite Element methods. Stochastics (2010, in press)

  6. Bieri, M., Andreev, R., Schwab, C.: Sparse tensor discretization of elliptic SPDEs. SIAM J. Sci. Comput. 31, 4281–4304 (2009/2010)

    Google Scholar 

  7. Bieri M., Schwab C.: Sparse high order FEM for elliptic sPDEs. Comput. Methods Appl. Mech. Eng. 198, 1149–1170 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  8. Braess D.: Finite Elemente, 3rd edn. Springer, Berlin (2002)

    Google Scholar 

  9. Brenner S.C., Scott L.R.: The Mathematical Theory of Finite Element Methods, 2nd edn. Springer, Berlin (2002)

    MATH  Google Scholar 

  10. Cohen, A.: Numerical analysis of wavelet methods. In: Studies in Mathematics and its Applications. North-Holland, Amsterdam (2003)

  11. 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)

    Article  MathSciNet  MATH  Google Scholar 

  12. Cohen A., DeVore R., Schwab C.: Analytic regularity and polynomial approximation of parametric and stochastic elliptic PDEs. J. Anal. Appl. 9, 11–47 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  13. Da Prato G., Zabczyk J.: Stochastic equations in infinite dimensions. Encyclopedia of Mathematics and its Applications, vol. 44. Cambridge University Press, Cambridge (1992)

    Google Scholar 

  14. 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)

    Article  MathSciNet  MATH  Google Scholar 

  15. 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)

    Article  MATH  Google Scholar 

  16. Gilbarg D., Trudinger N.S.: Elliptic partial differential equations of second order. In: Classics in Mathematics. Springer, Berlin (2001, reprint of the 1998 edition)

  17. Giles M.: Improved multilevel Monte Carlo convergence using the Milstein scheme. Preprint NA-06/22. Oxford University Computing Laboratory, Parks Road (2006)

    Google Scholar 

  18. Giles M.B.: Multilevel Monte Carlo path simulation. Oper. Res. 56, 607–617 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  19. Griebel M., Oswald P.: On additive Schwarz preconditioners for sparse grid discretizations. Numer. Math. 66, 449–463 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  20. Grisvard P.: Elliptic problems in nonsmooth domains. Monographs and Studies in Mathematics, vol. 24. Pitman (Advanced Publishing Program), Boston (1985)

    Google Scholar 

  21. 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)

  22. 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)

    Article  MathSciNet  MATH  Google Scholar 

  23. Lang A., Potthoff J.: Fast simulation of Gaussian random fields (2009, in review)

  24. 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)

  25. 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)

  26. 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)

  27. 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)

    Article  Google Scholar 

  28. 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)

    Article  Google Scholar 

  29. 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)

    Article  MathSciNet  MATH  Google Scholar 

  30. 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)

    Article  MathSciNet  MATH  Google Scholar 

  31. Schwab C., Todor R.A.: Sparse Finite Elements for elliptic problems with stochastic loading. Numer. Math. 95, 707–734 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  32. Schwab C., Todor R.A.: Sparse Finite Elements for stochastic elliptic problems—higher order moments. Computing 71, 43–63 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  33. Schwab C., Todor R.A.: Karhunen–Loève approximation of random fields by generalized fast multipole methods. J. Comput. Phys. 217, 100–122 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  34. von Petersdorff T., Schwab C.: Numerical solution of parabolic equations in high dimensions. M2AN Math. Model. Numer. Anal. 38, 93–127 (2004)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to Christoph Schwab.

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

Reprints 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

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00211-011-0377-0

Mathematics Subject Classification (2000)

Navigation