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

Harbrecht, Helmut; Peters, Michael; Siebenmorgen, Markus

doi:10.1090/mcom/3107

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