Multi-level Monte Carlo finite volume methods for uncertainty quantification in nonlinear systems of balance laws. (English) Zbl 1276.76066

Mishra, Siddhartha; Schwab, Christoph; Šukys, Jonas

Bijl, Hester (ed.) et al., Uncertainty quantification in computational fluid dynamics. Heidelberg: Springer (ISBN 978-3-319-00884-4/hbk; 978-3-319-00885-1/ebook). Lecture Notes in Computational Science and Engineering 92, 225-294 (2013).

Summary: A mathematical formulation of conservation and of balance laws with random input data, specifically with random initial conditions, random source terms and random flux functions, is reviewed. The concept of random entropy solution is specified. For scalar conservation laws in multi-dimensions, recent results on the existence and on the uniqueness of random entropy solutions with finite variances are presented. The combination of Monte Carlo sampling with Finite Volume Method

•  Scholarpedia
•  Wikipedia

discretization in space and time for the numerical approximation of the statistics of random entropy solutions is proposed. The finite variance of random entropy solutions is used to prove asymptotic error estimates for combined Monte Carlo Finite Volume Method discretizations of scalar conservation laws with random inputs. A Multi-Level extension of combined Monte Carlo Finite Volume Method (MC-FVM) discretizations is proposed and asymptotic error bounds are presented in the case of scalar, nonlinear hyperbolic conservation laws. Sparse tensor constructions for the computation of compressed approximations of two- and \(k-\)point space

•  nLab
•  Wikipedia
•  Wolfram MathWorld

-time correlation functions of random entropy solutions are introduced.Asymptotic error versus work estimates indicate superiority of Multi-Level versions of MC-FVM over the plain MC-FVM, under comparable assumptions on the random input data. In particular, it is shown that these compressed sparse tensor approximations converge essentially at the same rate as the MLMC-FVM estimators for the mean solutions.Extensions of the proposed algorithms to nonlinear, hyperbolic systems of balance laws are outlined. Multiresolution discretizations of random source terms which are exactly bias-free are indicated.Implementational aspects of these Multi-Level Monte Carlo Finite Volume methods, in particular results on large scale random number

•  Wikipedia
•  Wolfram MathWorld

generation, scalability and resilience on emerging massively parallel computing

•  Wikipedia
•  Wolfram MathWorld

platforms, are discussed.
For the entire collection see [Zbl 1276.76005].

© Springer International Publishing Switzerland 2013

MSC:

76M35	Stochastic analysis applied to problems in fluid mechanics
76M12	Finite volume methods applied to problems in fluid mechanics
76N15	Gas dynamics (general theory)

Software:

MersenneTwister; GEOCLAW; ALSVID-UQ

References:

[1]	Abgrall, R., A simple, flexible and generic deterministic approach to uncertainty quantification in non-linear problems (2007), INRIA: Rapport de Recherche, INRIA
[2]	ALSVID. Available from http://folk.uio.no/mcmurry/amhd.
[3]	ALSVID-UQ. Available from http://www.sam.math.ethz.ch/alsvid-uq.
[4]	Aziz, K.; Settari, A., Fundamentals of petroleum reservoir simulation (1979), London: Applied Science Publishers, London
[5]	A. Barth, Ch. Schwab and N. Zollinger. Multilevel MC Method for Elliptic PDEs with Stochastic Coefficients. Numerische Mathematik, Volume 119(1), pp. 123-161, 2011. · Zbl 1230.65006
[6]	Barth, T. J., Numerical methods for gas-dynamics systems on unstructured meshes. An Introduction to Recent Developments in Theory and Numerics of Conservation Laws, pp. 195-285. Lecture Notes in Computational Science and Engineering volume 5, Springer, Berlin (1999), D. Kroner, M. Ohlberger, and Rohde, C.: Eds, D. Kroner, M. Ohlberger, and Rohde, C. · Zbl 0969.76040
[7]	P. D. Bates, S. N. Lane and R. I. Ferguson. Parametrization, Validation and Uncertainty analysis of CFD models of fluvial and flood hydraulics in natural environments. Computational Fluid Dynamics: Applications in environmental hydraulics, John Wiley and sons, pp. 193-212, 2005.
[8]	Chen, Q. Y.; Gottlieb, D.; Hesthaven, J. S., Uncertainty analysis for steady flow in a dual throat nozzle, J. Comput. Phys, 204, 378-398 (2005) · Zbl 1143.76430 · doi:10.1016/j.jcp.2004.10.019
[9]	B. Cockburn and C-W. Shu. TVB Runge-Kutta local projection discontinuous Galerkin finite element method for conservation laws. II. General framework. Math. Comput., 52, pp. 411-435, 1989. · Zbl 0662.65083
[10]	Constantine M. Dafermos. Hyperbolic Conservation Laws in Continuum Physics (2nd Ed.). Springer Verlag, 2005. · Zbl 1078.35001
[11]	Josef Dick, Franes Y. Kuo and Ian H. Sloan. High dimensional integration: the Quasi Monte-Carlo way. Acta Numerica, to appear, 2013. · Zbl 1296.65004
[12]	R. Eymard, T. Gallouët, and R. Herbin. Finite volume methods, in Handbook of numerical analysis, Vol. VII, pp. 713-1020, North-Holland, Amsterdam, 2000. · Zbl 0981.65095
[13]	Fisher, P. F.; Tate, N. J., Causes and consequences of error in digital elevation models, Prog. in Phy. Geography, 30, 4, 467-489 (2006) · doi:10.1191/0309133306pp492ra
[14]	G. Fishman. Monte Carlo. Springer, 1996. · Zbl 0859.65001
[15]	Fjordholm, U. S.; Mishra, S.; Tadmor, E., Well-balanced, energy stable schemes for the shallow water equations with varying topology, J. Comput. Phys., 230, 5587-5609 (2011) · Zbl 1452.35149 · doi:10.1016/j.jcp.2011.03.042
[16]	Fuchs, F.; McMurry, A. D.; Mishra, S.; Risebro, N. H.; Waagan, K., Approximate Riemann solver based high-order finite volume schemes for the Godunov-Powell form of ideal MHD equations in multi-dimensions, Comm. Comput. Phys., 9, 324-362 (2011) · Zbl 1364.76113
[17]	M. Giles. Improved multilevel Monte Carlo convergence using the Milstein scheme. Preprint NA-06/22, Oxford computing lab, Oxford, U.K, 2006.
[18]	Giles, M., Multilevel Monte Carlo path simulation, Oper. Res., 56, 607-617 (2008) · Zbl 1167.65316 · doi:10.1287/opre.1070.0496
[19]	E. Godlewski and P.A. Raviart. Hyperbolic Systems of Conservation Laws. Mathematiques et Applications, Ellipses Publ., Paris, 1991. · Zbl 0768.35059
[20]	Gottlieb, S.; Shu, C. W.; Tadmor, E., High order time discretizations with strong stability property, SIAM. Review, 43, 89-112 (2001) · Zbl 0967.65098 · doi:10.1137/S003614450036757X
[21]	A. Harten, B. Engquist, S. Osher and S. R. Chakravarty. Uniformly high order accurate essentially non-oscillatory schemes. J. Comput. Phys., pp. 231-303, 1987s. · Zbl 0652.65067
[22]	S. Heinrich. Multilevel Monte Carlo methods. Large-scale scientific computing, Third international conference LSSC 2001, Sozopol, Bulgaria, 2001, Lecture Notes in Computer Science, Vol 2170, pp. 58-67, Springer Verlag, 2001. · Zbl 1031.65005
[23]	P. L’Ecuyer and F. Panneton. Fast Random Number Generators Based on Linear Recurrences Modulo 2: Overview and Comparison. Proceedings of the 2005 Winter Simulation Conference, pp. 110-119, IEEE press, 2005.
[24]	L’Ecuyer, P.; Panneton, F., Fast Random Number Generators Based on Linear Recurrences Modulo 2, ACM Trans. Math. Software, 32, 1-16 (2006) · Zbl 1346.94089 · doi:10.1145/1132973.1132974
[25]	LeVeque, R. A., Numerical Solution of Hyperbolic Conservation Laws (2005), Press: Cambridge Univ, Press
[26]	LeVeque, R.; George, D.; Berger, M., Tsunami modeling with adaptively refined finite volume methods, Acta Numerica, 20, 211-289 (2011) · Zbl 1426.76394 · doi:10.1017/S0962492911000043
[27]	Lin, G.; Su, C. H.; Karniadakis, G. E., The stochastic piston problem, PNAS, 101, 15840-15845 (2004) · Zbl 1135.76334 · doi:10.1073/pnas.0405889101
[28]	Ma, X.; Zabaras, N., An adaptive hierarchical sparse grid collocation algorithm for the solution of stochastic differential equations, J. Comp. Phys, 228, 3084-3113 (2009) · Zbl 1161.65006 · doi:10.1016/j.jcp.2009.01.006
[29]	Matsumoto, M.; Nishimura, T., Mersenne Twister: a 623-dimensionally equidistributed uniform pseudorandom number generator, ACM Trans. Modeling and Computer Simulation, 8, 3-30 (1998) · Zbl 0917.65005 · doi:10.1145/272991.272995
[30]	Mishra, S.; Schwab, Ch., Sparse tensor multi-level Monte Carlo finite volume methods for hyperbolic conservation laws with random initial data, Math. Comp., 280, 81, 1979-2018 (2012) · Zbl 1271.65018 · doi:10.1090/S0025-5718-2012-02574-9
[31]	S. Mishra, N.H. Risebro, Ch. Schwab and S. Tokareva. Numerical solution of scalar conservation laws with random flux functions. SAM Technical Report No. 2012-35, in review, 2012. Also available from http://www.sam.math.ethz.ch/sam_reports/index.php?id=2012-35. · Zbl 1343.65007
[32]	S. Mishra, Ch. Schwab and J. Šukys. Multi-level Monte Carlo finite volume methods for nonlinear systems of conservation laws in multi-dimensions. J. Comp. Phys., 231(8), pp. 3365-3388, 2012. · Zbl 1402.76083
[33]	Mishra, S.; Schwab, Ch.; Šukys, J., Multi-level Monte Carlo Finite Volume methods for shallow water equations with uncertain topography in multi-dimensions, SIAM J. Sci. Comput., 34, 6, B761-B784 (2012) · Zbl 1263.76045 · doi:10.1137/110857295
[34]	S. Pauli and P. Arbenz and Ch. Schwab. Intrinsic fault tolerance of multi level Monte Carlo methods. SAM Technical Report 2012-24, Seminar für Angewandte Mathematik ETH Zürich, 2012. Also available from http://www.sam.math.ethz.ch/sam_reports/index.php?id=2012-24.
[35]	Poette, G.; Després, B.; Lucor, D., Uncertainty quantification for systems of conservation laws, J. Comput. Phys., 228, 2443-2467 (2009) · Zbl 1161.65309 · doi:10.1016/j.jcp.2008.12.018
[36]	Prato, G. D.; Zabcyk, J., Stochastic Equations in infinite dimensions (1991), Press: Cambridge Univ, Press
[37]	G. Schmidlin. Fast solution algorithms for integral equations in \({\mathbb{R}}^3 \) . PhD dissertation ETH Zürich No. 15016, 2003.
[38]	G. Schmidlin and Ch. Schwab. Wavelet Galerkin BEM on unstructured meshes by aggregation. LNCSE 20, pp. 369-278, Springer Lecture Notes in CSE, Springer Verlag, Berlin Heidelberg New York, 2002. · Zbl 0989.65139
[39]	Ch. Schwab and S. Tokareva. High order approximation of probabilistic shock profiles in hyperbolic conservation laws with uncertain initial data. ESAIM: Mathematical Modelling and Numerical Analysis, ESAIM: M2AN 47, 807-835 (2013) DOI: 10.1051/m2an/2012060, www.esaim-m2an.org. · Zbl 1266.65008
[40]	Shu, C. W.; Osher, S., Efficient implementation of essentially non-oscillatory schemes - II, J. Comput. Phys., 83, 32-78 (1989) · Zbl 0674.65061 · doi:10.1016/0021-9991(89)90222-2
[41]	Shu, C. W., Essentially non-oscillatory and weighted essentially non-oscillatory schemes for hyperbolic conservation laws (1997), NASA: ICASE Technical report, NASA · Zbl 0927.65111
[42]	J. Šukys, S. Mishra, and Ch. Schwab. Static load balancing for multi-level Monte Carlo finite volume solvers. PPAM 2011, Part I, LNCS 7203, pp. 245-254. Springer, Heidelberg, 2012. · Zbl 1402.76083
[43]	J. Tryoen, O. Le Maitre, M. Ndjinga and A. Ern. Intrusive projection methods with upwinding for uncertain non-linear hyperbolic systems. Preprint, 2010. · Zbl 1197.65013
[44]	von Petersdorff, T.; Schwab, Ch., Sparse Finite Element Methods for Operator Equations with Stochastic Data, Applications of Mathematics, 51, 2, 145-180 (2006) · Zbl 1164.65300 · doi:10.1007/s10492-006-0010-1
[45]	Wan, X.; Karniadakis, G. E., Long-term behaviour of polynomial chaos in stochastic flow simulations, Comput. Meth. Appl. Mech. Engg., 195, 5582-5596 (2006) · Zbl 1123.76058 · doi:10.1016/j.cma.2005.10.016
[46]	Welford, B. P., Note on a Method for Calculating Corrected Sums of Squares and Products, Technometrics, 4, 419-420 (1962) · doi:10.1080/00401706.1962.10490022
[47]	Witteveen, J. A. S.; Loeven, A.; Bijl, H., An adaptive stochastic finite element approach based on Newton-Cotes quadrature in simplex elements, Comput. Fluids, 38, 1270-1288 (2009) · Zbl 1242.76145 · doi:10.1016/j.compfluid.2008.12.002
[48]	Xiu, D.; Hesthaven, J. S., High-order collocation methods for differential equations with random inputs, SIAM J. Sci. Comput., 27, 1118-1139 (2005) · Zbl 1091.65006 · doi:10.1137/040615201
[49]	Brutus, ETH Zürich, de.wikipedia.org/wiki/Brutus_(Cluster).
[50]	Cray XE6, Swiss National Supercomputing Center (CSCS), Lugano, www.cscs.ch.
[51]	MPI: A Message-Passing Interface Standard. Version 2.2, 2009, available from: http://www.mpi-forum.org/docs/mpi-2.2/mpi22-report.pdf.
[52]	Open MPI: Open Source High Performance Computing. Available from http://www.open-mpi.org/.