Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



On the quasi-Monte Carlo method with Halton points for elliptic PDEs with log-normal diffusion

Authors: Helmut Harbrecht, Michael Peters and Markus Siebenmorgen
Journal: Math. Comp. 86 (2017), 771-797
MSC (2010): Primary 65C05, 65C30, 60H25, 65N30
Published electronically: March 24, 2016
MathSciNet review: 3584548
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] M. Abramowitz and I. A. Stegun (eds.), Handbook of Mathematical Functions, with Formulas, Graphs, and Mathematical Tables, Dover Publications, Inc., New York, 1966. MR 0208797
  • [2] Robert A. Adams, Sobolev Spaces, Pure and Applied Mathematics, vol. 65, Academic Press [A subsidiary of Harcourt Brace Jovanovich, Publishers], New York-London, 1975. MR 0450957 (56 #9247)
  • [3] Emanouil I. Atanassov, On the discrepancy of the Halton sequences, Math. Balkanica (N.S.) 18 (2004), no. 1-2, 15-32. MR 2076074 (2005g:11137)
  • [4] 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 (2008e:65372),
  • [5] 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 (2005h:65012),
  • [6] 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 (2012i:65252),
  • [7] 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,
  • [8] 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,
  • [9] 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 (96g:05008),
  • [10] 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
  • [11] 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 (2005i:65186),
  • [12] Roger G. Ghanem and Pol D. Spanos, Stochastic Finite Elements: A Spectral Approach, Springer-Verlag, New York, 1991. MR 1083354 (91k:73102)
  • [13] Michael B. Giles, Multilevel Monte Carlo path simulation, Oper. Res. 56 (2008), no. 3, 607-617. MR 2436856 (2009g:65008),
  • [14] 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 (2011c:65259),
  • [15] 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,
  • [16] 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 0121961 (22 #12688)
  • [17] J. M. Hammersley and D. C. Handscomb, Monte Carlo Methods, Methuen & Co., Ltd., London; Barnes & Noble, Inc., New York, 1965. MR 0223065 (36 #6114)
  • [18] 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.
  • [19] 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.
  • [20] 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,
  • [21] 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 (2001e:65010)
  • [22] S. Heinrich Multilevel Monte Carlo Methods, in Lecture Notes in Large Scale Scientific Computing, London, 2001, Springer, pp. 58-67.
  • [23] Fred J. Hickernell, A generalized discrepancy and quadrature error bound, Math. Comp. 67 (1998), no. 221, 299-322. MR 1433265 (98c:65032),
  • [24] Fred J. Hickernell, Ian H. Sloan, and Grzegorz W. Wasilkowski, On tractability of weighted integration over bounded and unbounded regions in $ \mathbb{R}^s$, Math. Comp. 73 (2004), no. 248, 1885-1901. MR 2059741 (2005c:65018),
  • [25] Edmund Hlawka, Über die Diskrepanz mehrdimensionaler Folgen $ {\rm mod}\,1$, Math. Z. 77 (1961), 273-284 (German). MR 0150106 (27 #109)
  • [26] 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
  • [27] 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,
  • [28] 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 (2007m:65003),
  • [29] Michel Loève, Probability Theory. I+II, 4th ed., Graduate Texts in Mathematics, vol. 45, Springer-Verlag, New York-Heidelberg, 1977. MR 0651017 (58 #31324a)
  • [30] 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.
  • [31] 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 (2005j:65146),
  • [32] 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 (93h:65008)
  • [33] 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 (2009c:65331),
  • [34] Erich Novak and Henryk Woźniakowski, Tractability of Multivariate Problems. Vol. I: Linear Information, EMS Tracts in Mathematics, vol. 6, European Mathematical Society (EMS), Zürich, 2008. MR 2455266 (2009m:46037)
  • [35] Erich Novak and Henryk Woźniakowski, Tractability of Multivariate Problems. Vol. II: Standard Information for Functionals, EMS Tracts in Mathematics, vol. 12, European Mathematical Society (EMS), Zürich, 2010. MR 2676032
  • [36] Erich Novak and Henryk Woźniakowski, Tractability of Multivariate Problems. Vol. III: Standard Information for Operators, EMS Tracts in Mathematics, vol. 18, European Mathematical Society (EMS), Zürich, 2012. MR 2987170
  • [37] Art B. Owen, Halton sequences avoid the origin, SIAM Rev. 48 (2006), no. 3, 487-503. MR 2278439 (2007k:65009),
  • [38] J. K. Patel and C. B. Read, Handbook of the Normal Distribution, CRC Press, Boca Raton, 1996.
  • [39] 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 (2010i:68131)
  • [40] J. Sándor, D. S. Mitrinović, and B. Crstici, Handbook of Number Theory, Mathematics and its Applications, vol. 351, Kluwer Academic Publishers Group, Dordrecht, 1996. MR 1374329
  • [41] Christoph Schwab and Claude Jeffrey Gittelson, Sparse tensor discretizations of high-dimensional parametric and stochastic PDEs, Acta Numer. 20 (2011), 291-467. MR 2805155 (2012f:65018),
  • [42] Christian G. Simader, On Dirichlet's Boundary Value Problem: An $ L^{p}$-Theory Based on a Generalization of Garding's Inequality, Lecture Notes in Mathematics, Vol. 268, Springer-Verlag, Berlin-New York, 1972. MR 0473503 (57 #13169)
  • [43] 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 (2003m:65031),
  • [44] 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 (99d:65384),
  • [45] Xiaoqun Wang, A constructive approach to strong tractability using quasi-Monte Carlo algorithms, J. Complexity 18 (2002), no. 3, 683-701. MR 1928803 (2003m:65008),
  • [46] H. Woźniakowski, Tractability and strong tractability of linear multivariate problems, J. Complexity 10 (1994), no. 1, 96-128. MR 1263379 (95d:65117),
  • [47] S. C. Zaremba, Some applications of multidimensional integration by parts, Ann. Polon. Math. 21 (1968), 85-96. MR 0235731 (38 #4034)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 65C05, 65C30, 60H25, 65N30

Retrieve articles in all journals with MSC (2010): 65C05, 65C30, 60H25, 65N30

Additional Information

Helmut Harbrecht
Affiliation: Departement Mathematik und Informatik, Universität Basel, Spiegelgasse 1, 4051 Basel, Switzerland
Email: helmut.harbrecht

Michael Peters
Affiliation: Departement Mathematik und Informatik, Universität Basel, Spiegelgasse 1, 4051 Basel, Switzerland
Email: michael.peters,markus

Markus Siebenmorgen
Affiliation: Departement Mathematik und Informatik, Universität Basel, Spiegelgasse 1, 4051 Basel, Switzerland

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”.
Article copyright: © Copyright 2016 American Mathematical Society

American Mathematical Society