Application of Quasi-Monte Carlo Methods to Elliptic PDEs with Random Diffusion Coefficients: A Survey of Analysis and Implementation

I. Babus̆ka, F. Nobile, and R. Tempone, A stochastic collocation method for elliptic partial differential equations with random input data, SIAM J. Numer. Anal. 45 (2007), 1005–1034. I. Babus̆ka, R. Tempone, and G.E. Zouraris, Galerkin finite element approximations of stochastic elliptic partial differential equations, SIAM J. Numer. Anal. 42 (2004), 800–825. J. Baldeaux and J. Dick, QMC rules of arbitrary high order: reproducing kernel Hilbert space approach, Constr. Approx. 30 (2009), 495–527. J. Baldeaux, J. Dick, J. Greslehner, and F. Pillichshammer, Construction algorithms for higher order polynomial lattice rules, J. Complexity 27 (2011), 281–299. J. Baldeaux, J. Dick, G. Leobacher, D. Nuyens, and F. Pillichshammer, Efficient calculation of the worst-case error and (fast) component-by-component construction of higher order polynomial lattice rules, Numer. Algorithms 59 (2012), 403–431. A. Barth, Ch. Schwab, and N. Zollinger, Multi-level Monte Carlo finite element method for elliptic PDEs with stochastic coefficients, Numer. Math. 119 (2011), 123–161. V. I. Bogachev, Gaussian Measures, AMS Monographs Vol. 62, American Mathematical Society, R.I., USA, 1998. H. Bungartz and M. Griebel, Sparse grids, Acta Numer. 13 (2004), 147–269. R. E. Caflisch, W. Morokoff, and A. Owen, Valuation of mortgage backed securities using Brownian bridges to reduce effective dimension, J. Comput. Finance 1 (1997), 27–46. J. Charrier, Strong and weak error estimates for elliptic partial differential equations with random coefficients, SIAM J. Numer. Anal. 50 (2012), 216–246. 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), 322–352. K. A. Cliffe, M. B. Giles, R. Scheichl, and A. L. Teckentrup, Multilevel Monte Carlo methods and applications to elliptic PDEs with random coefficients, Computing and Visualization in Science Science 14 (2011), 3–15. A. Cohen, A. Chkifa, and Ch. Schwab, Breaking the curse of dimensionality in sparse polynomial approximation of parametric PDEs, Journ. Math. Pures et Appliquees 103 (2015), 400–428. A. Cohen and R. DeVore, Approximation of high-dimensional parametric PDEs, Acta Numer. 24 (2015), 1–159. A. Cohen, R. DeVore, and Ch. Schwab, Convergence rates of best \(N\)-term Galerkin approximations for a class of elliptic sPDEs, Found. Comp. Math. 10 (2010), 615–646. N. Collier, A.-L. Haji-Ali, F. Nobile, E. von Schwerin, and R. Tempone, A continuation multilevel Monte Carlo algorithm, BIT, 55 (2015), 399–432. R. Cools, F. Y. Kuo, and D. Nuyens, Constructing embedded lattice rules for multivariate integration, SIAM J. Sci. Comput. 28 (2006), 2162–2188. G. Dagan, Solute transport in heterogeneous porous formations, J. Fluid Mech. 145 (1984), 151–177. J. Dick, On the convergence rate of the component-by-component construction of good lattice rules, J. Complexity 20 (2004), 493–522. J. Dick, Explicit constructions of Quasi-Monte Carlo rules for the numerical integration of high-dimensional periodic functions, SIAM J. Numer. Anal. 45 (2007), 2141–2176. J. Dick, Walsh spaces containing smooth functions and Quasi-Monte Carlo rules of arbitrary high order, SIAM J. Numer. Anal. 46 (2008), 1519–1553. J. Dick, The decay of the Walsh coefficients of smooth functions, Bull. Aust. Math. Soc. 80 (2009), 430–453. J. Dick, F. Y. Kuo, Q. T. Le Gia, D. Nuyens, and Ch. Schwab, Higher order QMC Galerkin discretization for parametric operator equations, SIAM J. Numer. Anal. 52 (2014), 2676–2702. J. Dick, F. Y. Kuo, Q. T. Le Gia, and Ch. Schwab, Fast QMC matrix-vector multiplication, SIAM J. Sci. Comput. 37 (2015), A1436–A1450. J. Dick, F. Y. Kuo, Q. T. Le Gia, and Ch. Schwab, Multi-level higher order QMC Galerkin discretization for affine parametric operator equations, SIAM J. Numer. Anal. 54 (2016), 2541–2568. J. Dick, F .Y. Kuo, F. Pillichshammer, and I. H. Sloan, Construction algorithms for polynomial lattice rules for multivariate integration, Math. Comp. 74 (2005), 1895–1921. J. Dick, F. Y. Kuo, and I. H. Sloan, High-dimensional integration: the Quasi-Monte Carlo way, Acta Numer. 22 (2013), 133–288. J. Dick, Q. T. Le Gia, and Ch. Schwab, Higher order Quasi-Monte Carlo integration for holomorphic, parametric operator equations, in review. J. Dick, D. Nuyens, and F. Pillichshammer, Lattice rules for nonperiodic smooth integrands, Numer. Math. 126 (2014), 259–291. J. Dick and F. Pillichshammer, Multivariate integration in weighted Hilbert spaces based on Walsh functions and weighted Sobolev spaces, J. Complexity 21 (2005), 149–195. J. Dick and F. Pillichshammer, Digital Nets and Sequences, Cambridge University Press, 2010. J. Dick, F. Pillichshammer, and B. J. Waterhouse, The construction of good extensible rank-\(1\) lattices, Math. Comp. 77 (2008), 2345–2374. J. Dick, I. H. Sloan, X. Wang, and H. Woźniakowski, Liberating the weights, J. Complexity 20 (2004), 593–623. C. R. Dietrich and G. H. Newsam, Fast and exact simulation of stationary Gaussian processes through circulant embedding of the covariance matrix, SIAM J. Sci. Comput. 18, 1088–1107 (1997). R. Freeze, A stochastic conceptual analysis of one-dimensional groundwater flow in nonuniform homogeneous media, Water Resour. Res. 11 (1975), 725–741. M. Ganesh and S. C. Hawkins, A high performance computing and sensitivity analysis algorithm for stochastic many-particle wave scattering, SIAM J. Sci. Comput. 37 (2015), A1475–A1503. R. N. Gantner and Ch. Schwab, Computational Higher-Order QMC integration, Research Report 2014-24, Seminar for Applied Mathematics, ETH Zürich. R. G. Ghanem and P. D. Spanos, Stochastic Finite Elements, Dover, 1991. M. B. Giles, Improved multilevel Monte Carlo convergence using the Milstein scheme, Monte Carlo and Quasi-Monte Carlo methods 2006, Springer, 2007, pp 343–358. M. B. Giles, Multilevel Monte Carlo path simulation, Oper. Res. 256 (2008), 981–986. M. B. Giles, Multilevel Monte Carlo methods, Acta Numer. 24 (2015), 259–328. M. B. Giles and B. J. Waterhouse, Multilevel quasi-Monte Carlo path simulation. Radon Series Comp. Appl. Math. 8 (2009), 1–18. T. Goda, Good interlaced polynomial lattice rules for numerical integration in weighted Walsh spaces, J. Comput. Appl. Math. 285 (2015), 279–294. T. Goda and J. Dick, Construction of interlaced scrambled polynomial lattice rules of arbitrary high order, Found. Comput. Math. 15 (2015), 1245–1278. T. Goda, K. Suzuki, and T. Yoshiki, Digital nets with infinite digit expansions and construction of folded digital nets for quasi-Monte Carlo integration, J. Complexity 33 (2016), 30–54. I. G. Graham, F. Y. Kuo, J. Nichols, R. Scheichl, Ch. Schwab, and I. H. Sloan, QMC FE methods for PDEs with log-normal random coefficients, Numer. Math. 131 (2015), 329–368. I. G. Graham, F. Y. Kuo, D. Nuyens, R. Scheichl, and I. H. Sloan, Quasi-Monte Carlo methods for elliptic PDEs with random coefficients and applications, J. Comput. Phys. 230 (2011), 3668–3694. I. G. Graham, F. Y. Kuo, D. Nuyens, R. Scheichl, and I. H. Sloan, Analysis of QMC methods with circulant embedding for elliptic PDEs with lognormal coefficients, in preparation. M. Gunzburger, C. Webster, and G. Zhang, Stochastic finite element methods for partial differential equations with random input data, Acta Numer. 23 (2014), 521–650. A.L. Haji-Ali, F. Nobile, and R. Tempone, Multi-index Monte Carlo: when sparsity meets sampling, Numer. Math. 132 (2016), 767–806. H. Harbrecht, M. Peters, and M. Siebenmorgen, On multilevel quadrature for elliptic stochastic partial differential equations, in Sparse Grids and Applications, Lecture Notes in Computational Science and Engineering, Volume 88, 2013, pp.161–179. H. Harbrecht, M. Peters, and M. Siebenmorgen, Multilevel accelerated quadrature for PDEs with log-normal distributed random coefficient. Preprint 2013-18, Math. Institut, Universität Basel, 2013. H. Harbrecht, M. Peters, and M. Siebenmorgen, On the quasi-Monte Carlo method with Halton points for elliptic PDEs with log-normal diffusion, Math. Comp., appeared online. S. Heinrich, Monte Carlo complexity of global solution of integral equations, J. Complexity 14 (1998), 151–175. S. Heinrich, Multilevel Monte Carlo methods, Lecture notes in Compu. Sci. Vol. 2179, Springer, 2001, pp. 3624–3651. F. J. Hickernell, Obtaining \(O(N^{-2+\epsilon })\) convergence for lattice quadrature rules, in Monte Carlo and Quasi-Monte Carlo Methods 2000 (K. T. Fang, F. J. Hickernell, and H. Niederreiter, eds.), Springer, Berlin, 2002, pp. 274–289. F. J. Hickernell, P. Kritzer, F. Y. Kuo, and D. Nuyens, Weighted compound integration rules with higher order convergence for all \(N\), Numer. Algorithms 59 (2012), 161–183. V. H. Hoang and Ch. Schwab, Regularity and generalized polynomial chaos approximation of parametric and random second-order hyperbolic partial differential equations, Analysis and Applications (Singapore) 10 (2012), 295–326. V. H. Hoang and Ch. Schwab, Analytic regularity and polynomial approximation of stochastic, parametric elliptic multiscale PDEs, Analysis and Applications (Singapore) 11 (2013), 1350001, 50. V. Hoang, Ch. Schwab, and A. Stuart, Sparse MCMC gpc finite element methods for Bayesian inverse problems, Inverse Problems 29 (2013), 085010. R. J. Hoeksema and P. K. Kitanidis, Analysis of the spatial structure of properties of selected aquifers, Water Resour. Res. 21 (1985), 536–572. S. Joe, Construction of good rank-\(1\) lattice rules based on the weighted star discrepancy, in Monte Carlo and Quasi-Monte Carlo Methods 2004 (H. Niederreiter and D. Talay, eds.), Springer Verlag, pp. 181–196, 2006. S. Joe and F. Y. Kuo, Constructing Sobol\(^{\prime }\) sequences with better two-dimensional projections, SIAM J. Sci. Comput. 30 (2008), 2635–2654. A. Kunoth and Ch. Schwab, Analytic regularity and GPC approximation for stochastic control problems constrained by linear parametric elliptic and parabolic PDEs, SIAM J. Control and Optimization 51 (2013), 2442–2471. F. Y. Kuo, Component-by-component constructions achieve the optimal rate of convergence for multivariate integration in weighted Korobov and Sobolev spaces, J. Complexity 19 (2003), 301–320. F. Y. Kuo, R. Scheichl, Ch. Schwab, I. H. Sloan, and E. Ullmann, Multilevel quasi-Monte Carlo methods for lognormal diffusion problems. Math. Comp., to appear F. Y. Kuo, Ch. Schwab, and I. H. Sloan, Quasi-Monte Carlo methods for high dimensional integration: the standard weighted-space setting and beyond, ANZIAM J. 53 (2011), 1–37. F. Y. Kuo, Ch. Schwab, and I. H. Sloan, Quasi-Monte Carlo finite element methods for a class of elliptic partial differential equations with random coefficient, SIAM J. Numer. Anal. 50 (2012), 3351–3374. F. Y. Kuo, Ch. Schwab, and I. H. Sloan, Multi-level quasi-Monte Carlo finite element methods for a class of elliptic partial differential equations with random coefficient, Found. Comput. Math. 15 (2015), 411–449. F. Y. Kuo, I. H. Sloan, G. W. Wasilkowski, and B. J. Waterhouse, Randomly shifted lattice rules with the optimal rate of convergence for unbounded integrands, J. Complexity 26 (2010), 135–160. Q. T. Le Gia, A QMC-spectral method for elliptic PDEs with random coefficients on the unit sphere, in Monte Carlo and Quasi-Monte Carlo Methods 2012 (J. Dick, F. Y. Kuo, G. W. Peters and I. H. Sloan, eds.), Springer Verlag, Heidelberg, 2013, pp. 491–508. M. Loève. Probability Theory, Volume II. Springer-Verlag, New York, 4th edition, 1978. Z. Lu and D. Zhang, A comparative study on quantifying uncertainty of flow in randomly heterogeneous media using Monte Carlo simulations, the conventional and KL-based moment-equation approaches, SIAM J. Sci. Comput. 26 (2004), 558–577. R. L. Naff, D. F. Haley, and E. A. Sudicky, High-resolution Monte Carlo simulation of flow and conservative transport in heterogeneous porous media 1. Methodology and flow results, Water Resour. Res., 34 (1998), 663–677. R. L. Naff, D. F. Haley, and E. A. Sudicky, High-resolution Monte Carlo simulation of flow and conservative transport in heterogeneous porous media 2. Transport Results, Water Resour. Res., 34 (1998), 679–697. J. A. Nichols and F. Y. Kuo, Fast CBC construction of randomly shifted lattice rules achieving \(\cal {O}(N^{-1+\delta })\) in weighted spaces with POD weights, J. Complexity 30 (2014), 444–468. H. Niederreiter, Random Number Generation and Quasi-Monte Carlo Methods, SIAM, Philadelphia, 1992. V. Nistor and C. Schwab, High order Galerkin approximations for parametric second order elliptic partial differential equations, Math. Mod. Meth. Appl. Sci. 23 (2013), 1729–1760. F. Nobile, R. Tempone, and C. G. Webster, A sparse grid stochastic collocation method for partial differential equations with random input data, SIAM J. Numer. Anal. 46 (2008), 2309–2345. 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), 2411–2442. E. Novak and H. Woźniakowski, Tractability of Multivariate Problems, Volume I: Linear Information, European Mathematical Society, Zürich, 2008. E. Novak and H. Woźniakowski, Tractability of Multivariate Problems, II: Standard Information for Functionals, European Mathematical Society, Zürich, 2010. E. Novak and H. Woźniakowski, Tractability of Multivariate Problems, Volume III: Standard Information for Operators, European Mathematical Society, Zürich, 2012. D. Nuyens, The construction of good lattice rules and polynomial lattice rules, In: Uniform Distribution and Quasi-Monte Carlo Methods (P. Kritzer, H. Niederreiter, F. Pillichshammer, A. Winterhof, eds.), Radon Series on Computational and Applied Mathematics Vol. 15, De Gruyter, 2014, pp. 223–256. D. Nuyens and R. Cools, Fast algorithms for component-by-component construction of rank-\(1\) lattice rules in shift-invariant reproducing kernel Hilbert spaces, Math. Comp. 75 (2006), 903–920. D. Nuyens and R. Cools, Fast component-by-component construction of rank-\(1\) lattice rules with a non-prime number of points, J. Complexity 22 (2006), 4–28. D. Nuyens and R. Cools, Fast component-by-component construction, a reprise for different kernels, in Monte Carlo and quasi-Monte Carlo methods 2004 (H. Niederreiter and D. Talay, eds.), Springer, Berlin, 2006, pp. 373–387. S. H. Paskov and J. F. Traub, Faster valuation of financial derivatives, J. Portfolio Management 22 (1995), 113–120. P. Robbe, D. Nuyens, and S. Vandewalle, A practical multilevel quasi-Monte Carlo method for elliptic PDEs with random coefficients. In Master Thesis “Een parallelle multilevel Monte-Carlo-methode voor de simulatie van stochastische partiële differentiaalvergelijkingen” by P. Robbe, June 2015. Y. Rubin, Applied Stochastic Hydrogeology, Oxford University Press, New York, 2003. C. Schillings and Ch. Schwab, Sparse, adaptive smolyak algorithms for Bayesian inverse problems, Inverse Problems 29 (2013), 065011. C. Schillings and Ch. Schwab, Sparsity in Bayesian inversion of parametric operator equations, Inverse Problems 30 (2014), 065007. Ch. Schwab, QMC Galerkin discretizations of parametric operator equations, in Monte Carlo and Quasi-Monte Carlo Methods 2012 (J. Dick, F. Y. Kuo, G. W. Peters and I. H. Sloan, eds.), Springer Verlag, Heidelberg, 2013, pp. 613–629. Ch. Schwab and C. J. Gittelson, Sparse tensor discretizations of high-dimensional parametric and stoch astic PDEs, Acta Numer. 20 (2011), 291–467. Ch. Schwab and R. A. Todor, Karhunen-Loève approximation of random fields by generalized fast multipole methods, J. Comput. Phy. 217 (2006), 100–122. Ch. Schwab and R. A. Todor, Convergence rates for sparse chaos approximations of elliptic problems with stochastic coefficients, IMA J. Numer. Anal. 27 (2007), 232–261. I. H. Sloan, What’s New in high-dimensional integration? – designing quasi-Monte Carlo for applications, In: Proceedings of the ICIAM, Beijing, China (L. Guo and Z. Ma eds), Higher Education Press, Beijing, 2015, pp. 365–386. I. H. Sloan and S. Joe, Lattice Methods for Multiple Integration, Oxford University Press, Oxford, 1994. I. H. Sloan, F. Y. Kuo, and S. Joe, Constructing randomly shifted lattice rules in weighted Sobolev spaces, SIAM J. Numer. Anal. 40 (2002), 1650–1665. I. H. Sloan and A, V. Reztsov, Component-by-component construction of good lattice rules, Math. Comp. 71 (2002), 263–273. I. H. Sloan, X. Wang, and H. Woźniakowski, Finite-order weights imply tractability of multivariate integration, J. Complexity 20 (2004), 46–74. I. H. Sloan and H. Woźniakowski, When are quasi-Monte Carlo algorithms efficient for high-dimensional integrals?, J. Complexity 14 (1998), 1–33. A. L. Teckentrup, P. Jantsch, C. G. Webster, and M. Gunzburger, A multilevel stochastic collocation method for partial differential equations with random input data, Preprint arXiv:1404.2647 (2014). A. L. Teckentrup, R. Scheichl, M. B. Giles, and E. Ullmann, Further analysis of multilevel Monte Carlo methods for elliptic PDEs with random coefficient, Numer. Math. 125 (2013), 569–600. X. Wang, Strong tractability of multivariate integration using quasi-Monte Carlo algorithms, Math. Comp. 72 (2002), 823–838. D. Xiu and G. E. Karniadakis, Modeling uncertainty in flow simulations via generalized polynomial chaos, J. Comput. Phys. 187 (2003), 137–167. T. Yoshiki, Bounds on Walsh coefficients by dyadic difference and a new Koksma-Hlawka type inequality for Quasi-Monte Carlo integration. arXiv:1504.03175 (2015). D. Zhang, Stochastic Methods for Flow in Porous Media: Coping with Uncertainties, Academic Press, San Diego, 2002.