Abstract
We survey recent convergence rate bounds for single-level and multilevel QMC Finite Element (FE for short) algorithms for the numerical approximation of linear, second order elliptic PDEs in divergence form in a bounded, polygonal domain D. The diffusion coefficient a is assumed to be an isotropic, log-Gaussian random field (GRF for short) in D. The representation of the GRF \(Z = \log a\) is assumed affine-parametric with i.i.d. standard normal random variables, and with locally supported functions \(\psi _j\) characterizing the spatial variation of the GRF Z. The goal of computation is the evaluation of expectations (i.e., of so-called “ensemble averages”) of (linear functionals of) the random solution. The QMC rules employed are randomly shifted lattice rules proposed in Nichols, Kuo (J Complex 30:444–468, 2014, [19]) as used and analyzed previously in a similar setting (albeit for globally in D supported spatial representation functions \(\psi _j\) as arise in Karhunen-Loève expansions) in Graham et al. (Numer Math 131:329–368, 2015, [9]), Kuo et al. (Math Comput 86:2827–2860, 2017, [14]). The multilevel QMC-FE approximation \(Q^*_L\) analyzed here for locally supported \(\psi _j\) was proposed first in Kuo, Schwab, Sloan (Found Comput Math 15:411–449, 2015, [17]) for affine-parametric operator equations. As shown in Gantner, Herrmann, Schwab (SIAM J Numer Anal 56:111–135, 2018, [7]), Gantner, Herrmann, Schwab (Contemporary computational mathematics - a celebration of the 80th birthday of Ian Sloan. Springer, Cham, 2018, [6]), Herrmann, Schwab (QMC integration for lognormal-parametric, elliptic PDEs: local supports and product weights. Technical Report 2016-39, Seminar for Applied Mathematics, ETH Zürich, Switzerland, 2016, [10]), Herrmann, Schwab (Multilevel quasi-Monte Carlo integration with product weights for elliptic PDEs with lognormal coefficients. Technical Report 2017-19, Seminar for Applied Mathematics, ETH Zürich, Switzerland, 2017, [11]) localized supports of the \(\psi _j\) (which appear in multiresolution representations of GRFs Z of Lévy–Ciesielski type in D) allow for the use of product weights, originally proposed in construction of QMC rules in Sloan, Woźniakowski (J Complex 14:1–33, 1998, [23]) (cf. the survey (Dick, Kuo, Sloan in Acta Numer 22:133–288, 2013, [4]) and references there). The present results from Herrmann, Schwab (Multilevel quasi-Monte Carlo integration with product weights for elliptic PDEs with lognormal coefficients. Technical Report 2017-19, Seminar for Applied Mathematics, ETH Zürich, Switzerland, 2017, [11]) on convergence rates for the multilevel QMC FE algorithm allow for general polygonal domains D and for GRFs Z whose realizations take values in weighted spaces containing \(W^{1,\infty }(D)\). Localized support assumptions on \(\psi _j\) are shown to allow QMC rule generation by the fast, FFT based CBC constructions in Nuyens, Cools (J Complex 22:4–28, 2006, [21]), Nuyens, Cools (Math Comput 75:903–920, 2006, [20]) which scale linearly in the integration dimension which, for multiresolution representations of GRFs, is proportional to the number of degrees of freedom used in the FE discretization in the physical domain D. We show numerical experiments based on public domain QMC rule generating software in Gantner (A generic c++ library for multilevel quasi-Monte Carlo. In: Proceedings of the Platform for Advanced Scientific Computing Conference, PASC ’16, ACM, New York, USA, pp 11:1–11:12 2016, [5]), Kuo, Nuyens (Found Comput Math 16:1631–1696, 2016, [13]).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Babuška, I., Kellogg, R.B., Pitkäranta, J.: Direct and inverse error estimates for finite elements with mesh refinements. Numer. Math. 33(4), 447–471 (1979)
Bachmayr, M., Cohen, A., DeVore, R., Migliorati, G.: Sparse polynomial approximation of parametric elliptic PDEs. part II: lognormal coefficients. ESAIM. Math. Model. Numer. Anal. 51(1), 341–363 (2017)
Bogachev, V.I.: Gaussian Measures, Mathematical Surveys and Monographs, vol. 62. American Mathematical Society, Providence (1998)
Dick, J., Kuo, F.Y., Sloan, I.H.: High-dimensional integration: the quasi-Monte Carlo way. Acta Numer. 22, 133–288 (2013)
Gantner, R.N.: A generic c++ library for multilevel quasi-Monte Carlo. In: Proceedings of the Platform for Advanced Scientific Computing Conference, PASC ’16, ACM, New York, NY, USA, pp. 11:1–11:12 (2016)
Gantner, R.N., Herrmann, L., Schwab, C.: Multilevel QMC with product weights for affine-parametric, elliptic PDEs. In: Dick, J., Kuo, F.Y., Woźniakowski, H. (eds.) Contemporary Computational Mathematics - a celebration of the 80th birthday of Ian Sloan. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-72456-0_18
Gantner, R.N., Herrmann, L., Schwab, C.: Quasi-Monte Carlo integration for affine-parametric, elliptic PDEs: local supports and product weights. SIAM J. Numer. Anal. 56(1), 111–135 (2018)
Gantner, R.N., Schwab, C.: Computational higher order quasi-Monte Carlo integration. Monte Carlo and Quasi-Monte Carlo Methods: MCQMC, vol. 163, pp. 271–288. Springer, Leuven, Belgium (2016)
Graham, I.G., Kuo, F.Y., Nichols, J.A., Scheichl, R., Schwab, C., Sloan, I.H.: Quasi-Monte Carlo finite element methods for elliptic PDEs with lognormal random coefficients. Numer. Math. 131(2), 329–368 (2015)
Herrmann, L., Schwab, C.: QMC integration for lognormal-parametric, elliptic PDEs: local supports and product weights. Technical Report 2016-39, Seminar for Applied Mathematics, ETH Zürich, Switzerland (2016). https://www.sam.math.ethz.ch/sam_reports/reports_final/reports2016/2016-39_rev1.pdf
Herrmann, L., Schwab, C.: Multilevel quasi-Monte Carlo integration with product weights for elliptic PDEs with lognormal coefficients. Technical Report 2017-19, Seminar for Applied Mathematics, ETH Zürich, Switzerland (2017). https://www.sam.math.ethz.ch/sam_reports/reports_final/reports2017/2017-19.pdf
Hilber, N., Reichmann, O., Schwab, C., Winter, C.: Computational Methods for Quantitative Finance. Finite Element Methods for Derivative Pricing. Springer, Heidelberg (2013)
Kuo, F.Y., Nuyens, D.: Application of quasi-Monte Carlo Methods to elliptic PDEs with random diffusion coefficients: a survey of analysis and implementation. Found. Comput. Math. 16(6), 1631–1696 (2016)
Kuo, F.Y., Scheichl, R., Schwab, Ch., Sloan, I.H., Ullmann, E.: Multilevel quasi-Monte Carlo methods for lognormal diffusion problems. Math. Comput. 86(308), 2827–2860 (2017)
Kuo, F.Y., Schwab, Ch., Sloan, I.H.: Quasi-Monte Carlo methods for high-dimensional integration: the standard (weighted Hilbert space) setting and beyond. ANZIAM J. 53(1), 1–37 (2011)
Kuo, F.Y., Schwab, Ch., Sloan, I.H.: Quasi-Monte Carlo finite element methods for a class of elliptic partial differential equations with random coefficients. SIAM J. Numer. Anal. 50(6), 3351–3374 (2012)
Kuo, F.Y., Schwab, Ch., Sloan, I.H.: Multi-level quasi-Monte Carlo finite element methods for a class of elliptic PDEs with random coefficients. Found. Comput. Math. 15(2), 411–449 (2015)
Kuo, F.Y., Sloan, I.H., Wasilkowski, G.W., Waterhouse, B.J.: Randomly shifted lattice rules with the optimal rate of convergence for unbounded integrands. J. Complex. 26(2), 135–160 (2010)
Nichols, J.A., Kuo, F.Y.: Fast CBC construction of randomly shifted lattice rules achieving \(\cal{O}(n^{-1+\delta })\) convergence for unbounded integrands over \(\mathbb{R}^s\) in weighted spaces with POD weights. J. Complex. 30(4), 444–468 (2014)
Nuyens, D., Cools, R.: Fast algorithms for component-by-component construction of rank-1 lattice rules in shift-invariant reproducing kernel Hilbert spaces. Math. Comput. 75(254), 903–920 (2006). (electronic)
Nuyens, D., Cools, R.: Fast component-by-component construction of rank-1 lattice rules with a non-prime number of points. J. Complex. 22(1), 4–28 (2006)
Opic, B., Kufner, A.: Hardy-Type Inequalities. Pitman Research Notes in Mathematics Series, vol. 219. Longman Scientific Technical, Harlow (1990)
Sloan, I.H., Woźniakowski, H.: When are quasi-Monte Carlo algorithms efficient for high-dimensional integrals? J. Complex. 14(1), 1–33 (1998)
Stein, E.M.: Singular Integrals and Differentiability Properties of Functions. Princeton Mathematical Series. Princeton University Press, Princeton (1970). No. 30
Triebel, H.: Interpolation Theory, Function Spaces, Differential Operators, 2nd edn. Johann Ambrosius Barth, Heidelberg (1995)
Acknowledgements
This work was supported in part by the Swiss National Science Foundation (SNSF) under grant SNF 159940. The authors acknowledge the computational resources provided by the EULER cluster of ETH Zürich. The authors thank Robert N. Gantner for letting them use parts of his Python code.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer International Publishing AG, part of Springer Nature
About this paper
Cite this paper
Herrmann, L., Schwab, C. (2018). QMC Algorithms with Product Weights for Lognormal-Parametric, Elliptic PDEs. In: Owen, A., Glynn, P. (eds) Monte Carlo and Quasi-Monte Carlo Methods. MCQMC 2016. Springer Proceedings in Mathematics & Statistics, vol 241. Springer, Cham. https://doi.org/10.1007/978-3-319-91436-7_17
Download citation
DOI: https://doi.org/10.1007/978-3-319-91436-7_17
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-91435-0
Online ISBN: 978-3-319-91436-7
eBook Packages: Mathematics and StatisticsMathematics and Statistics (R0)