×

Multilevel QMC with product weights for affine-parametric, elliptic PDEs. (English) Zbl 1405.65008

Dick, Josef (ed.) et al., Contemporary computational mathematics – a celebration of the 80th birthday of Ian Sloan. In 2 volumes. Cham: Springer (ISBN 978-3-319-72455-3/hbk; 978-3-319-72456-0/ebook). 373-405 (2018).
Summary: We present an error analysis of higher order Quasi-Monte Carlo (QMC) integration and of randomly shifted QMC lattice rules for parametric operator equations with uncertain input data taking values in Banach spaces. Parametric expansions of these input data in locally supported bases such as splines or wavelets was shown in [the first author et al., SIAM J. Numer. Anal. 56, No. 1, 111–135 (2018; Zbl 1378.65072)] to allow for dimension independent convergence rates of combined QMC-Galerkin approximations. In the present work, we review and refine the results in that reference to the multilevel setting, along the lines of F. Y. Kuo et al. [Found. Comput. Math. 15, No. 2, 411–449 (2015; Zbl 1318.65006)] where randomly shifted lattice rules and globally supported representations were considered, and also the results of J. Dick et al. [SIAM J. Numer. Anal. 54, No. 4, 2541–2568 (2016; Zbl 1347.65012)] in the particular situation of locally supported bases in the parametrization of uncertain input data. In particular, we show that locally supported basis functions allow for multilevel QMC quadrature with product weights, and prove new error vs. work estimates superior to those in these references (albeit at stronger, mixed regularity assumptions on the parametric integrand functions than what was required in the single-level QMC error analysis in the first reference above). Numerical experiments on a model affine-parametric elliptic problem confirm the analysis.
For the entire collection see [Zbl 1398.65010].

MSC:

65C05 Monte Carlo methods
65D30 Numerical integration
65N30 Finite element, Rayleigh-Ritz and Galerkin methods for boundary value problems involving PDEs
35J47 Second-order elliptic systems
65N15 Error bounds for boundary value problems involving PDEs

Software:

deal.ii; gMLQMC; QMC4PDE
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Arndt, D., Bangerth, W., Davydov, D., Heister, T., Heltai, L., Kronbichler, M., Maier, M., Pelteret, J.P., Turcksin, B., Wells, D.: The deal.II library, version 8.5. J. Numer. Math. (2017). https://doi.org/10.1515/jnma-2017-0058 · Zbl 1375.65148 · doi:10.1515/jnma-2017-0058
[2] 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) · Zbl 0423.65057 · doi:10.1007/BF01399326
[3] Bachmayr, M., Cohen, A., Migliorati, G.: Sparse polynomial approximation of parametric elliptic PDEs. Part I: affine coefficients. ESAIM Math. Model. Numer. Anal. 51(1), 321-339 (2017) · Zbl 1365.41003
[4] Chen, P., Schwab, Ch.: Model order reduction methods in computational uncertainty quantification. In: Handbook of Uncertainty Quantification, pp. 1-53. Springer International Publishing, Cham (2016)
[5] Dashti, M., Stuart, A.: The Bayesian approach to inverse problems. In: Handbook of Uncertainty Quantification, pp. 1-118. Springer International Publishing, Cham (2016)
[6] Dick, J., Kuo, F.Y., Sloan, I.H.: High-dimensional integration: the quasi-Monte Carlo way. Acta Numer. 22, 133-288 (2013) · Zbl 1296.65004 · doi:10.1017/S0962492913000044
[7] Dick, J., Kuo, F.Y., Le Gia, Q.T., Nuyens, D., Schwab, Ch.: Higher order QMC Petrov-Galerkin discretization for affine parametric operator equations with random field inputs. SIAM J. Numer. Anal. 52(6), 2676-2702 (2014) · Zbl 1326.65013 · doi:10.1137/130943984
[8] Dick, J., Kuo, F.Y., Le Gia, Q.T., Schwab, Ch.: Multilevel higher order QMC Petrov-Galerkin discretization for affine parametric operator equations. SIAM J. Numer. Anal. 54(4), 2541-2568 (2016) · Zbl 1347.65012 · doi:10.1137/16M1078690
[9] Gantner, R.N.: A generic C++ library for multilevel quasi-Monte Carlo. In: Proceedings of the Platform for Advanced Scientific Computing Conference, PASC’16, pp. 11:1-11:12. ACM, New York, NY (2016)
[10] Gantner, R.N., Schwab, Ch.: Computational higher order quasi-Monte Carlo integration. In: Monte Carlo and Quasi-Monte Carlo Methods: MCQMC, Leuven, April 2014, vol. 163, pp. 271-288. Springer, Cham (2016) · Zbl 1356.65003
[11] Gantner, R.N., Herrmann, L., Schwab, Ch.: Quasi-Monte Carlo integration for affine-parametric, elliptic PDEs: local supports and product weights. SIAM J. Numer. Anal. 56(1), 111-135 (2018) · Zbl 1378.65072 · doi:10.1137/16M1082597
[12] Gaspoz, F.D., Morin, P.: Convergence rates for adaptive finite elements. IMA J. Numer. Anal. 29(4), 917-936 (2009) · Zbl 1183.65134 · doi:10.1093/imanum/drn039
[13] Giles, M.B.: Multilevel Monte Carlo methods. Acta Numer. 24, 259-328 (2015) · Zbl 1316.65010 · doi:10.1017/S096249291500001X
[14] Graham, I.G., Kuo, F.Y., Nichols, J.A., Scheichl, R., Schwab, Ch., Sloan, I.H.: Quasi-Monte Carlo finite element methods for elliptic PDEs with lognormal random coefficients. Numer. Math. 131(2), 329-368 (2015) · Zbl 1341.65003 · doi:10.1007/s00211-014-0689-y
[15] Herrmann, L., Schwab, Ch.: QMC integration for lognormal-parametric, elliptic PDEs: local supports and product weights. Technical Report 2016-39 (revised), Seminar for Applied Mathematics, ETH Zürich (2016) · Zbl 07006664
[16] Herrmann, L., Schwab, Ch.: 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, Zürich (2017) · Zbl 07135561
[17] Herrmann, L., Schwab, Ch.: QMC algorithms with product weights for lognormal-parametric, elliptic PDEs. Technical Report 2017-04 (revised), Seminar for Applied Mathematics, ETH Zürich, Zürich (2017) · Zbl 1422.65017
[18] Hilber, N., Reichmann, O., Schwab, Ch., Winter, Ch.: Computational methods for quantitative finance. In: Finite Element Methods for Derivative Pricing. Springer Finance. Springer, Heidelberg (2013) · Zbl 1275.91005
[19] 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) · Zbl 1362.65015 · doi:10.1007/s10208-016-9329-5
[20] 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) · Zbl 1248.65001 · doi:10.1017/S1446181112000077
[21] 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) · Zbl 1271.65017 · doi:10.1137/110845537
[22] 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) · Zbl 1318.65006 · doi:10.1007/s10208-014-9237-5
[23] Kuo, F., Scheichl, R., Schwab, Ch., Sloan, I., Ullmann, E.: Multilevel quasi-Monte Carlo methods for lognormal diffusion problems. Math. Comput. 86(308), 2827-2860 (2017) · Zbl 1368.65005 · doi:10.1090/mcom/3207
[24] 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 (electronic) (2006) · Zbl 1094.65004
[25] 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) · Zbl 1092.65002 · doi:10.1016/j.jco.2005.07.002
[26] Schwab, Ch., Gittelson, C.J.: Sparse tensor discretizations of high-dimensional parametric and stochastic PDEs. Acta Numer. 20, 291-467 (2011) · Zbl 1269.65010 · doi:10.1017/S0962492911000055
[27] Sloan, I.H., Joe, S.: Lattice Methods for Multiple Integration. Oxford Science Publications. The Clarendon Press/Oxford University Press, Oxford/New York (1994) · Zbl 0855.65013
[28] Sloan, I.H., Woźniakowski, H.: When are quasi-Monte Carlo algorithms efficient for high-dimensional integrals? J. Complex. 14(1), 1-33 (1998) · Zbl 1032.65011 · doi:10.1006/jcom.1997.0463
[29] Sloan, I.H., Kuo, F.Y., Joe, S.: Constructing randomly shifted lattice rules in weighted Sobolev spaces. SIAM J. Numer. Anal. 40(5), 1650-1665 (2002) · Zbl 1037.65005 · doi:10.1137/S0036142901393942
[30] Sloan, I.H., Kuo, F.Y., Joe, S.: On the step-by-step construction of quasi-Monte Carlo integration rules that achieve strong tractability error bounds in weighted Sobolev spaces. Math. Comput. 71(240), 1609-1640 (2002) · Zbl 1011.65001 · doi:10.1090/S0025-5718-02-01420-5
[31] Triebel, H.: Interpolation Theory, Function Spaces, Differential Operators, 2nd edn. Johann Ambrosius Barth, Heidelberg (1995) · Zbl 0830.46028
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.