On the quasi-Monte Carlo method with Halton points for elliptic PDEs with log-normal diffusion
HTML articles powered by AMS MathViewer
- by Helmut Harbrecht, Michael Peters and Markus Siebenmorgen PDF
- Math. Comp. 86 (2017), 771-797 Request permission
Abstract:
This article is dedicated to the computation of the moments of the solution to elliptic partial differential equations with random, log-normally distributed diffusion coefficients by the quasi-Monte Carlo method. Our main result is that the convergence rate of the quasi-Monte Carlo method based on the Halton sequence for the moment computation depends only linearly on the dimensionality of the stochastic input parameters. In particular, we attain this rather mild dependence on the stochastic dimensionality without any randomization of the quasi-Monte Carlo method under consideration. For the proof of the main result, we require related regularity estimates for the solution and its powers. These estimates are also provided here. Numerical experiments are given to validate the theoretical findings.References
- Milton Abramowitz and Irene A. Stegun (eds.), Handbook of mathematical functions, with formulas, graphs, and mathematical tables, Dover Publications, Inc., New York, 1966. MR 0208797
- Robert A. Adams, Sobolev spaces, Pure and Applied Mathematics, Vol. 65, Academic Press [Harcourt Brace Jovanovich, Publishers], New York-London, 1975. MR 0450957
- Emanouil I. Atanassov, On the discrepancy of the Halton sequences, Math. Balkanica (N.S.) 18 (2004), no. 1-2, 15–32. MR 2076074
- Ivo Babuška, Fabio Nobile, and Raúl Tempone, A stochastic collocation method for elliptic partial differential equations with random input data, SIAM J. Numer. Anal. 45 (2007), no. 3, 1005–1034. MR 2318799, DOI 10.1137/050645142
- Ivo Babuška, Raúl Tempone, and Georgios E. Zouraris, Galerkin finite element approximations of stochastic elliptic partial differential equations, SIAM J. Numer. Anal. 42 (2004), no. 2, 800–825. MR 2084236, DOI 10.1137/S0036142902418680
- Andrea Barth, Christoph Schwab, and Nathaniel Zollinger, Multi-level Monte Carlo finite element method for elliptic PDEs with stochastic coefficients, Numer. Math. 119 (2011), no. 1, 123–161. MR 2824857, DOI 10.1007/s00211-011-0377-0
- Julia Charrier, Strong and weak error estimates for elliptic partial differential equations with random coefficients, SIAM J. Numer. Anal. 50 (2012), no. 1, 216–246. MR 2888311, DOI 10.1137/100800531
- 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), no. 1, 322–352. MR 3033013, DOI 10.1137/110853054
- G. M. Constantine and T. H. Savits, A multivariate Faà di Bruno formula with applications, Trans. Amer. Math. Soc. 348 (1996), no. 2, 503–520. MR 1325915, DOI 10.1090/S0002-9947-96-01501-2
- Pingyi Fan, New inequalities of Mill’s ratio and application to the inverse Q-function approximation, Aust. J. Math. Anal. Appl. 10 (2013), no. 1, Art. 11, 11. MR 3128834
- Philipp Frauenfelder, Christoph Schwab, and Radu Alexandru Todor, Finite elements for elliptic problems with stochastic coefficients, Comput. Methods Appl. Mech. Engrg. 194 (2005), no. 2-5, 205–228. MR 2105161, DOI 10.1016/j.cma.2004.04.008
- Roger G. Ghanem and Pol D. Spanos, Stochastic finite elements: a spectral approach, Springer-Verlag, New York, 1991. MR 1083354, DOI 10.1007/978-1-4612-3094-6
- Michael B. Giles, Multilevel Monte Carlo path simulation, Oper. Res. 56 (2008), no. 3, 607–617. MR 2436856, DOI 10.1287/opre.1070.0496
- C. J. Gittelson, Stochastic Galerkin discretization of the log-normal isotropic diffusion problem, Math. Models Methods Appl. Sci. 20 (2010), no. 2, 237–263. MR 2649152, DOI 10.1142/S0218202510004210
- I. G. Graham, F. Y. Kuo, J. A. Nichols, R. Scheichl, Ch. Schwab, and I. H. Sloan, Quasi-Monte Carlo finite element methods for elliptic PDEs with lognormal random coefficients, Numer. Math. 131 (2015), no. 2, 329–368. MR 3385149, DOI 10.1007/s00211-014-0689-y
- J. H. Halton, On the efficiency of certain quasi-random sequences of points in evaluating multi-dimensional integrals, Numer. Math. 2 (1960), 84–90. MR 121961, DOI 10.1007/BF01386213
- J. M. Hammersley and D. C. Handscomb, Monte Carlo methods, Methuen & Co., Ltd., London; Barnes & Noble, Inc., New York, 1965. MR 0223065
- H. Harbrecht, M. Peters, and M. Siebenmorgen, Multilevel quadrature for PDEs with log-normally distributed diffusion coefficient, to appear in SIAM/ASA Journal on Uncertainty Quantification.
- H. Harbrecht, M. Peters, and M. Siebenmorgen, On multilevel quadrature for elliptic stochastic partial differential equations, in Sparse Grids and Applications, J. Garcke and M. Griebel, eds., vol. 88 of Lecture Notes in Computational Science and Engineering, Springer, Berlin-Heidelberg, 2013, pp. 161–179.
- Helmut Harbrecht, Michael Peters, and Markus Siebenmorgen, Efficient approximation of random fields for numerical applications, Numer. Linear Algebra Appl. 22 (2015), no. 4, 596–617. MR 3367825, DOI 10.1002/nla.1976
- Stefan Heinrich, The multilevel method of dependent tests, Advances in stochastic simulation methods (St. Petersburg, 1998) Stat. Ind. Technol., Birkhäuser Boston, Boston, MA, 2000, pp. 47–61. MR 1752538
- S. Heinrich Multilevel Monte Carlo Methods, in Lecture Notes in Large Scale Scientific Computing, London, 2001, Springer, pp. 58–67.
- Fred J. Hickernell, A generalized discrepancy and quadrature error bound, Math. Comp. 67 (1998), no. 221, 299–322. MR 1433265, DOI 10.1090/S0025-5718-98-00894-1
- Fred J. Hickernell, Ian H. Sloan, and Grzegorz W. Wasilkowski, On tractability of weighted integration over bounded and unbounded regions in $\Bbb R^s$, Math. Comp. 73 (2004), no. 248, 1885–1901. MR 2059741, DOI 10.1090/S0025-5718-04-01624-2
- Edmund Hlawka, Über die Diskrepanz mehrdimensionaler Folgen $\textrm {mod}\,1$, Math. Z. 77 (1961), 273–284 (German). MR 150106, DOI 10.1007/BF01180179
- Viet Ha Hoang and Christoph Schwab, $N$-term Wiener chaos approximation rate for elliptic PDEs with lognormal Gaussian random inputs, Math. Models Methods Appl. Sci. 24 (2014), no. 4, 797–826. MR 3163401, DOI 10.1142/S0218202513500681
- F. Y. Kuo, Ch. 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), no. 1, 1–37. MR 2928989, DOI 10.1017/S1446181112000077
- Frances Y. Kuo, Grzegorz W. Wasilkowski, and Benjamin J. Waterhouse, Randomly shifted lattice rules for unbounded integrands, J. Complexity 22 (2006), no. 5, 630–651. MR 2257826, DOI 10.1016/j.jco.2006.04.006
- Michel Loève, Probability theory. I, 4th ed., Graduate Texts in Mathematics, Vol. 45, Springer-Verlag, New York-Heidelberg, 1977. MR 0651017
- M. Matsumoto and T. Nishimura, Mersenne Twister: a 623-dimensionally equidistributed uniform pseudo-random number generator, ACM Trans. Model. Comput. Simul. 8 (1998), 3–30.
- Hermann G. Matthies and Andreas Keese, Galerkin methods for linear and nonlinear elliptic stochastic partial differential equations, Comput. Methods Appl. Mech. Engrg. 194 (2005), no. 12-16, 1295–1331. MR 2121216, DOI 10.1016/j.cma.2004.05.027
- Harald Niederreiter, Random number generation and quasi-Monte Carlo methods, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 63, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1992. MR 1172997, DOI 10.1137/1.9781611970081
- F. Nobile, R. Tempone, and C. G. Webster, An anisotropic sparse grid stochastic collocation method for partial differential equations with random input data, SIAM J. Numer. Anal. 46 (2008), no. 5, 2411–2442. MR 2421041, DOI 10.1137/070680540
- Erich Novak and Henryk Woźniakowski, Tractability of multivariate problems. Vol. 1: Linear information, EMS Tracts in Mathematics, vol. 6, European Mathematical Society (EMS), Zürich, 2008. MR 2455266, DOI 10.4171/026
- Erich Novak and Henryk Woźniakowski, Tractability of multivariate problems. Volume II: Standard information for functionals, EMS Tracts in Mathematics, vol. 12, European Mathematical Society (EMS), Zürich, 2010. MR 2676032, DOI 10.4171/084
- Erich Novak and Henryk Woźniakowski, Tractability of multivariate problems. Volume III: Standard information for operators, EMS Tracts in Mathematics, vol. 18, European Mathematical Society (EMS), Zürich, 2012. MR 2987170, DOI 10.4171/116
- Art B. Owen, Halton sequences avoid the origin, SIAM Rev. 48 (2006), no. 3, 487–503. MR 2278439, DOI 10.1137/S0036144504441573
- J. K. Patel and C. B. Read, Handbook of the Normal Distribution, CRC Press, Boca Raton, 1996.
- Carl Edward Rasmussen and Christopher K. I. Williams, Gaussian processes for machine learning, Adaptive Computation and Machine Learning, MIT Press, Cambridge, MA, 2006. MR 2514435
- D. S. Mitrinović, J. Sándor, and B. Crstici, Handbook of number theory, Mathematics and its Applications, vol. 351, Kluwer Academic Publishers Group, Dordrecht, 1996. MR 1374329
- Christoph Schwab and Claude Jeffrey Gittelson, Sparse tensor discretizations of high-dimensional parametric and stochastic PDEs, Acta Numer. 20 (2011), 291–467. MR 2805155, DOI 10.1017/S0962492911000055
- Christian G. Simader, On Dirichlet’s boundary value problem, Lecture Notes in Mathematics, Vol. 268, Springer-Verlag, Berlin-New York, 1972. An $L^{p}$-theory based on a generalization of Gȧrding’s inequality. MR 0473503
- I. H. Sloan, F. Y. Kuo, and S. Joe, Constructing randomly shifted lattice rules in weighted Sobolev spaces, SIAM J. Numer. Anal. 40 (2002), no. 5, 1650–1665. MR 1950616, DOI 10.1137/S0036142901393942
- Ian H. Sloan and Henryk Woźniakowski, When are quasi-Monte Carlo algorithms efficient for high-dimensional integrals?, J. Complexity 14 (1998), no. 1, 1–33. MR 1617765, DOI 10.1006/jcom.1997.0463
- Xiaoqun Wang, A constructive approach to strong tractability using quasi-Monte Carlo algorithms, J. Complexity 18 (2002), no. 3, 683–701. MR 1928803, DOI 10.1006/jcom.2002.0641
- H. Woźniakowski, Tractability and strong tractability of linear multivariate problems, J. Complexity 10 (1994), no. 1, 96–128. MR 1263379, DOI 10.1006/jcom.1994.1004
- S. C. Zaremba, Some applications of multidimensional integration by parts, Ann. Polon. Math. 21 (1968), 85–96. MR 235731, DOI 10.4064/ap-21-1-85-96
Additional Information
- Helmut Harbrecht
- Affiliation: Departement Mathematik und Informatik, Universität Basel, Spiegelgasse 1, 4051 Basel, Switzerland
- Email: helmut.harbrecht@unibas.ch
- Michael Peters
- Affiliation: Departement Mathematik und Informatik, Universität Basel, Spiegelgasse 1, 4051 Basel, Switzerland
- MR Author ID: 975028
- Email: michael.peters@unibas.ch, markus@unibas.ch
- Markus Siebenmorgen
- Affiliation: Departement Mathematik und Informatik, Universität Basel, Spiegelgasse 1, 4051 Basel, Switzerland
- Email: siebenmorgen@unibas.ch
- Received by editor(s): November 6, 2013
- Received by editor(s) in revised form: December 18, 2014, and July 6, 2015
- Published electronically: March 24, 2016
- Additional Notes: This research was supported by the Swiss National Science Foundation (SNSF) through the project “Rapid Solution of Boundary Value Problems on Stochastic Domains”.
- © Copyright 2016 American Mathematical Society
- Journal: Math. Comp. 86 (2017), 771-797
- MSC (2010): Primary 65C05, 65C30, 60H25, 65N30
- DOI: https://doi.org/10.1090/mcom/3107
- MathSciNet review: 3584548