Abstract
We consider hyperbolic systems of conservation laws and review developments in the general area of computational uncertainty quantification (UQ) for these equations. We focus on non-intrusive sampling methods of the Monte-Carlo (MC) and Multi-level Monte-Carlo (MLMC) type. The modeling of uncertainty, within the framework of random fields and random entropy solutions, is discussed. We also describe (ML)MC finite volume methods and present the underlying error bounds and complexity estimates. Based on these bounds, and numerical experiments, we illustrate the gain in efficiency resulting from the use of MLMC methods in this context. Recent progress in the mathematical UQ frameworks of measure-valued and statistical solutions is briefly presented, with comprehensive literature survey.
Access provided by CONRICYT-eBooks. Download chapter PDF
Similar content being viewed by others
1 Introduction
Systems of conservation laws are nonlinear partial differential equations of the form
Here, the unknown \(\mathbf {U}= \mathbf {U}(x,t) : {\mathbb {R}}^d\times {\mathbb {R}}_+ \to {\mathbb {R}}^N\) is the vector of conserved variables, \(\mathbf {F} = (\mathbf { F}^1, \dots , \mathbf {F}^d) : {\mathbb {R}}^{N\times N} \to {\mathbb {R}}^{N\times d}\) is the flux function and \(\mathbf {c} = (\mathbf {c}^1, \dots , \mathbf {c}^d) : {\mathbb {R}}^d \times {\mathbb {R}}_+ \to {\mathbb {R}}^{N\times d}\) is a spatio-temporal coefficient. We denote \({\mathbb {R}}_+ := [0,\infty )\). Here, U 0 denotes the prescribed initial data.
In bounded domains, the system (1) needs to be supplemented with suitable boundary conditions.
The system (1) is termed hyperbolic if the flux Jacobian matrix has real eigenvalues [11]. Hyperbolic systems of conservation laws arise in a wide variety of models in physics and engineering and we refer to [11] for a wide range of examples. Solutions of (1) can develop discontinuities in finite time, even for smooth initial data (see again [11] and the references there). Therefore, solutions of (1) are weak solutions in that \(\mathbf {U} \in (L^1_{\mathrm {loc}} ({\mathbb {R}}^d \times {\mathbb {R}}_+))^N\) is required to satisfy the integral identity
for all test functions \(\varphi \in C^1_{0}({\mathbb {R}}_+ \times {\mathbb {R}}^d)\). It is well known that weak solutions are not necessarily unique [11]. Additional admissibility criteria or entropy conditions are necessary to obtain uniqueness. In space dimension d > 1, rigorous existence and uniqueness results for conservation (balance) laws and for generic initial data are available only for the scalar case, i.e., in the case N = 1.
1.1 Numerical Methods
Numerical methods for the solution of (2) comprise Finite Difference (FD), Finite Volume (FV) and Discontinuous Galerkin (DG) methods. We refer to the textbooks [28, 42] and the references there.
Within the popular FV framework [28], the cell averages of the unknown are updated in time in terms of numerical fluxes across cell interfaces. These numerical fluxes are often obtained by the (approximate) solutions of Riemann problems in the direction normal to the cell interface. Higher order spatial accuracy is obtained by reconstructing cell averages in terms of non-oscillatory piecewise polynomial functions, within the TVD [42], ENO [33] and WENO [55] procedures or using Discontinuous Galerkin methods (see, e.g. [7]). Higher order temporal accuracy is achieved by employing strong stability preserving Runge-Kutta methods [30]. Space-time DG-discretizations can also be employed for High-order spatio-temporal accuracy [34].
1.2 Aims and Scope
Any numerical scheme approximating (1) requires the initial data U 0, the coefficients c and the flux function F, as well as suitable boundary conditions, as inputs. However, in practice, these inputs are obtained by measurements (observations). Moreover, measurements cannot be precise and always involve some degree of uncertainty. Input uncertainty for (1) implies, upon uncertainty propagation, corresponding uncertainty in the solution.
The modeling, mathematical analysis, numerical approximation and numerical quantification of solution uncertainty, given experimental data, comprise the discipline of uncertainty quantification (UQ).
One aim in this article is to survey computational methods for the efficient, computational UQ for nonlinear, hyperbolic conservation laws with random inputs, and to provide some indications on the numerical analysis of UQ methods for these equations. Our focus in this article is on non-intrusive computational methods and their implementation, and on the mathematical analysis of their computational complexity. In our presentation, we emphasize broad applicability for a large class of conservation laws, rather than problem-specific, optimal results.
Our motivation for this focus on non-intrusive methods is as follows: first, non-intrusive methods afford trivial integration of existing, deterministic numerical solvers of forward problems, and are, therefore, popular in computational UQ in science and engineering. Second and as mentioned earlier, nonlinear hyperbolic conservation laws are well known to exhibit solutions of very low regularity in physical space, due to shock formation even for smooth input data (initial and boundary data, as well as flux functions). Third, hyperbolicity implies finite speed of propagation which, in the context of UQ for conservation laws with parametric input uncertainty, implies propagation of singular supports into the domain of parameters that describe the uncertain inputs of the system. The presence of, in general, moving singular supports propagating along characteristics in parametric families of weak solutions precludes high convergence rates of “smooth” computational methods, such as generalized polynomial chaos, PCA etc. for this class of computational UQ problems (we mention, however, that even in the absence of viscosity, there are regularizing effects due to averaging; cases in point are the so-called “transport collapse” regularizations in averaging lemmas (see, e.g. [43, 44] and the references there) or due to statistical ensemble averaging of random entropy solutions (see, e.g. [54])).
We therefore focus in the present survey on sampling methods of Monte-Carlo (MC for short) and of Multi-Level MC (MLMC for short) type, as well as on stochastic collocation methods. These methods have in common that their computational realization is based on existing numerical conservation law solvers, for example the finite volume (FV) or discontinuous Galerkin (DG) type, without any modification; this implies, in particular, that existing discretization error bounds for these methods, e.g. from [8, 15, 39, 42] and the references there, can be used for an error analysis of non-intrusive computational UQ for hyperbolic conservation laws.
In contrast, intrusive computational methods will require, as a rule, some form of reformulation of the conservation law prior to discretization and entail, usually, significant refactoring resp. redesign of numerical solvers. We refer to, e.g., [24, 59] and references therein for examples of this type, where the so-called stochastic Galerkin methodology has been employed and was shown to require significant modifications of numerical schemes as well as of actual, numerical solver.
Given our focus on non-intrusive UQ methods of the MC and Multi-level MC type, we structure this survey as follows: in the first part, we will focus on the very specific problem of UQ for scalar conservation laws with random initial data. Here, we describe data and solution uncertainty in terms of random fields and within the framework of random entropy solutions [46]. This is feasible as the underlying deterministic solution operator is well-defined and forms a non-expansive (in time) semi-group on \(L^1(\mathbb {R}^d)\). We will formulate both the MC and MLMC methods and combine them with a FV space-time discretization to obtain rigorous convergence rates for the (ML)MC-FV scheme and demonstrate that the MLMC-FV method is significantly more efficient (computationally) than the MC-FV method.
Next, we extend the (ML)MC-FV schemes for UQ of systems of conservation laws with random inputs. Here, the underlying deterministic problem may be ill-posed within the class of entropy solutions [6]. Consequently, the notion of random entropy solutions may not be well-defined. Moreover, there is no rigorous convergence result for the underlying deterministic FV (or any other) discretization frameworks. Hence, we postulate convergence and obtain the corresponding error (and complexity) estimates for the (ML)MC-FV methods. Although this combination is seen to work well in practice, recent results [17, 18, 45] have demonstrated the limitations of this framework. Instead, novel solution concepts such as those of entropy measure valued solutions [17, 18] and statistical solutions [19] and have been proposed and analyzed. We will conclude with a brief review of these concepts.
2 Preliminaries
2.1 Random Variables in Banach Spaces
Our mathematical formulation of scalar conservation laws with random inputs will use the concept of random fields i.e., random variables taking values in function spaces. We recapitulate basic concepts as presented, for example, in [10, Chap1].
Let E be a Banach space, and let \((\varOmega , {\mathscr F})\) be a measurable space, with the set Ω of elementary events, and with \({\mathscr F}\) a corresponding σ-algebra. An E-valued random variable (or random variable taking values in E) is any mapping X : Ω → E such that the set {ω ∈ Ω: \(X(\omega ) \in A\} = \{X \in A\} \in {\mathscr F}\) for any \(A \in {\mathscr G}\), i.e. such that X is a \({\mathscr G}\)-measurable mapping from Ω into E. Here, \((E, {\mathscr G})\) denotes a measurable space on the Banach space E.
For a Banach space E, we denote the Borel σ-field \({\mathscr B}(E)\). Then, \((E, {\mathscr B}(E))\) is a measurable space and random variables taking values in E i.e. maps X : Ω → E are \(({\mathscr F}, {\mathscr B}(E))\) measurable. For a separable Banach space E with norm ∥∘∥ E and (topological) dual E ∗, \({\mathscr B}(E)\) is the smallest σ-field of subsets of E containing all sets
For a separable Banach space, X : Ω → E is an E-valued random variable iff for every φ ∈ E ∗, \(\omega \longmapsto \varphi (X(\omega )) \in \mathbb {R}^1\) is an \(\mathbb {R}^1\)-valued random variable: for any RV X : Ω → E on \((\varOmega , {\mathscr F})\) which takes values in E, the mapping \(\varOmega \ni \omega \longmapsto \|X(\omega )\|{ }_E \in \mathbb {R}^1\) is (strongly) measurable. For more details and proofs, we refer to [10] or to [60].
The strongly measurable mapping X : Ω → E is Bochner integrable if, for any probability measure \(\mathbb {P}\) on the measurable space \((\varOmega , {\mathscr F})\),
A probability measure \(\mathbb {P}\) on \((\varOmega , {\mathscr F})\) is a σ-additive set function from Ω into [0, 1] such that \(\mathbb {P}(\varOmega ) = 1\); the triplet \((\varOmega , {\mathscr F}, \mathbb {P})\) is called probability space. We shall always assume, unless explicitly stated, that \((\varOmega , {\mathscr F}, \mathbb {P})\) is complete.
An E-valued RV is called simple if it can assume only finitely many values. A simple RV X, taking values in E, has the explicit form (with χ A denoting the indicator function of \(A \in {\mathscr F}\))
For simple RVs X taking values in E and for any \({\mathscr B} \in {\mathscr F}\),
For such X(⋅) and for all \(B \in {\mathscr F}\),
For any random variable X : Ω → E which is Bochner integrable, there exists a sequence \(\{X_m\}_{m \in \mathbb {N}}\) of simple random variables such that, for all ω ∈ Ω, ∥X(ω) − X m (ω)∥ E → 0 as m →∞. Therefore, (5) and (6) extend in the usual fashion by continuity to any E-valued random variable. We denote the Bochner-integral
by \(\mathbb {E}[X]\) (“expectation” of X).
We introduce for 1 ≤ p ≤∞ Bochner spaces of p-summable random variables X taking values in the Banach-space E. The set \(L^1(\varOmega , {\mathscr F}, \mathbb {P}; E)\) comprises all (equivalence classes of) integrable, E-valued random variables X. It is a Banach space if equipped with the norm
Define \(L^p(\varOmega , {\mathscr F}, \mathbb {P}; E)\) for 1 ≤ p < ∞ as the set of p-summable random variables taking values E. With the norm
\(L^p(\varOmega , {\mathscr F}, \mathbb {P}; E)\) becomes a Banach space. For p = ∞, we denote by \(L^\infty (\varOmega , {\mathscr F}, \mathbb {P}; E)\) the set of all E-valued random variables which are essentially bounded. This set is a Banach space equipped with the norm
If T < ∞ and Ω = [0, T], \({\mathscr F} = {\mathscr B}([0,T])\), we write L p([0, T];E). Note that for any separable Banach-space E, and for any r ≥ p ≥ 1,
We conclude the section of preliminaries with a criterion for strong measurability.
Lemma 1 ([60, Corollary 1.13])
Let E 1 and E 2 be Banach spaces, and \((\varOmega ,\mathscr {F},\mathbb {P})\) a probability space. If f : Ω → E 1 is strongly Bochner measurable, and if ϕ : E 1 → E 2 is continuous, then the composition ϕ ∘ f : Ω → E 2 is strongly Bochner measurable.
2.2 Monte-Carlo (MC) Sampling in Banach Spaces
Let \(\widehat {Y}_i:\varOmega \rightarrow F\), i = 1, …, M, be independent identically distributed (“iid” for short) random variables taking values in the Banach space E. We let
be the Monte Carlo estimator for \(\mathbb {E}[\,Y^{(k)}]\). A computable estimate E M [ Y (k)] for the kth moment \(\mathscr {M}^k(Y)\) of Y will converge in E as M →∞ at a rate which depends on the integrability of Y . Specifically, at the rate of convergence (in terms of M) of
to zero as M →∞ for some 1 ≤ p < ∞. If E is a finite dimensional space or a Hilbert space, and if X ∈ L 2k(Ω;X), the so-called mean square error (MSE) is bounded as
using the independence of the samples \(\widehat {Y}_i\).
For general Banach spaces E, the convergence rate depends on the type of the Banach space, which is defined as follows [38, p. 246].
Definition 1
Let 1 ≤ p ≤∞ and Z j , \(j\in \mathbb {N}\) a sequence of Bernoulli-Rademacher random variables. A Banach space E is said to be of type p if there is a type constant C > 0 such that for all finite sequences \((x_j)_{j=1}^N\subset E\), \(N\in \mathbb {N}\),
By the triangle inequality, every Banach space has type 1. Hilbert spaces have type 2. One can show that the L p-spaces have type \(\min \{p,2\}\) for 1 ≤ p < ∞ [38].
One has the following result from [36], [38, Proposition 9.11] and [9, Section 4] for Banach spaces of type p.
Proposition 1 ([36])
Let E be a Banach space of type p with a type constant C t . Then, for every finite sequence \((Y_j)_{j=1}^N\) of independent mean zero random variables in L p(Ω), one has the bound
Corollary 1
Let E be a Banach space of type p ∈ [1, 2] with type constant C t . Then for every finite sequence \((Y_j)_{j=1}^N\) of iid mean zero random variables with Y j (ω) ∼ Y (ω) in L p(Ω),
Remark 1
The complexity of MC methods with respect to the type parameter p of the function space E has been investigated in [12, 13] and the references there. The relevance of Proposition 1 for MC methods applied to scalar conservation laws is due to \(L^1(\mathbb {R}^d)\) being crucial for the error- and well-posedness analysis of the underlying FV schemes for these problems. The space \(L^1(\mathbb {R}^d)\) being a Banach space of type 1, will a priori not allow for convergence rate bounds in MLMC-FV discretizations, as was incorrectly stipulated in [46], and also in related work [51] on combining MLMC discretization with the front-tracking algorithm.
Instead, and as pointed out in [48], lower rates of convergence of FV discretizations in the stronger norms \(L^p(\mathbb {R}^d)\) with p > 1, with the space \(L^p(\mathbb {R}^d)\) being of type \(\min \{p,2 \}\), lead to convergence and error vs. work analysis of (ML)MC-FV methods for scalar conservation laws, which will be described in detail subsequently.
3 Scalar Conservation Laws with Random Initial Data
We begin with a review of classical results on deterministic scalar conservation laws (SCLs). We also review random entropy solutions for SCLs with random initial data from [46], and in particular existence and uniqueness of a random entropy solution with finite second moments. Let us mention that SCLs with random input data have received considerable attention in the context of numerical methods for uncertainty quantification; we only mention [22, 63].
We also mention considerable activity on enlarging the class of admissible random flux functions, in particular by so-called “rough path” calculus and the kinetic (re)formulation of the SCL (14)–(15) rather than the Kružkov theory; we refer to [22, 26, 43, 44] and the references there.
3.1 Deterministic Scalar Hyperbolic Conservation Laws
In-order to present the basic ideas in a simple setting, we consider the Cauchy problem for scalar conservation laws (SCL) i.e., (1) with N = 1 and with a spatially homogeneous deterministic flux function f(u). Then, (1) can be written as
with
We supply the SCL (13) with initial condition
and an entropy admissibility condition, which we choose as the Kružkov entropy condition or an equivalent version of it.
3.2 Entropy Solution
It is well-known that the deterministic Cauchy problem (13), (15) admits, for each \(u_0 \in L^1(\mathbb {R}^d) \cap BV(\mathbb {R})\), a unique entropy solution u (see, e.g., [11, 28, 56]). For every t > 0, \(u (\cdot , t) \in L^1(\mathbb {R}^d)\). We require the (nonlinear) data-to-solution map
in our subsequent development. To state its properties, we introduce some additional notation: for a Banach-space E with norm ∥∘∥ E , and for 0 < T ≤ +∞, we denote by C([0, T];E) the space of bounded and continuous functions from [0, T] with values in E, and by L p(0, T;E), 1 ≤ p ≤ +∞, the space of strongly Bochner measurable functions from (0, T) to E such that for 1 ≤ p < +∞
respectively, if p = ∞,
are finite. The following existence result is classical. (see, for example, [35, Thms. 2.13, 2.14, Thm. 4.3] or also [15, 28, 29, 37, 42],
Theorem 1
Assume that in the SCL (14)–(15) holds \(f\in C^1(\mathbb {R};\mathbb {R}^d)\) , and the initial data u 0 satisfies
Then there holds:
-
(1)
The SCL (14)–(15) admits a unique entropy solution \(u \in L^\infty (\mathbb {R}^d \times (0,T))\).
-
(2)
For every t > 0, the (nonlinear) data-to-solution map S(t) given by
$$\displaystyle \begin{aligned} u(\cdot,t) = S(t) \,u_0 \end{aligned}$$satisfies
-
(i)
\(S(t): L^1(\mathbb {R}^d) \rightarrow L^1(\mathbb {R}^d)\) is a (non-expansive) Lipschitz map, i.e.,
$$\displaystyle \begin{aligned} \|S(t) u_0 - S(t) v_0\|{}_{L^1(\mathbb{R}^d)} \le \|u_0 - v_0\|{}_{L^1(\mathbb{R}^d)}\,. \end{aligned} $$(20) -
(ii)
S(t) maps \((L^1 \cap BV)(\mathbb {R}^d)\) into \((L^1\cap BV)(\mathbb {R}^d)\) and
$$\displaystyle \begin{aligned} TV(S(t) u_0) \le TV(u_0) \quad \forall u_0 \in (L^1 \cap BV) (\mathbb{R}^d)\,. \end{aligned} $$(21) -
(iii)
There hold the L ∞ and L 1 stability bounds
$$\displaystyle \begin{aligned} \|S(t)u_0\|{}_{L^\infty(\mathbb{R}^d)} & \le \|u_0\|{}_{L^\infty(\mathbb{R}^d)} \,; {} \end{aligned} $$(22)$$\displaystyle \begin{aligned} \|S(t)u_0\|{}_{L^1(\mathbb{R}^d)}\; & \le \|u_0\|{}_{L^1(\mathbb{R}^d)} \,. {} \end{aligned} $$(23) -
(iv)
The mapping S(t) is a uniformly continuous mapping from \(L^1(\mathbb {R}^d)\) into \(C([0, \infty ) ; L^1(\mathbb {R}^d))\) , and
$$\displaystyle \begin{aligned} \|S(\cdot) u_0 \|{}_{C([0,T]; L^1(\mathbb{R}^d))} = \max\limits_{0 \le t \le T} \|S(t)u_0\|{}_{L^1(\mathbb{R}^d)} \le \|u_0\|{}_{L^1(\mathbb{R}^d)} \,. \end{aligned} $$(24)
-
(i)
Hyperbolic conservation laws exhibit finite propagation speed of perturbations. As a consequence, compactly supported initial data gives rise to solutions which are compactly supported for all time, however, with time-dependent supports. We present one version of such a “domain of influence” result, for the SCL (14)–(15).
Proposition 2
For the Cauchy problem (14)–(15), assume that \(f\in C^1(\mathbb {R};\mathbb {R}^d)\) and that u 0 satisfies (19). Assume moreover that the initial data u 0 ∈ Z has compact support: there exists a finite, positive constant R such that
Then, for every 0 < t < ∞, the unique entropy solution u of the Cauchy problem (14)–(15) is compactly supported as well, and with \(\bar {M} := \| u_0 \|{ }_{L^\infty (\mathbb {R}^d)} < \infty \) , there holds
where
denotes a upper bound on the maximal propagation speed.
3.3 Random Entropy Solution
Based on Theorem 1, we will now formulate the SCL (14)–(15) for random initial data u 0(ω;⋅), with deterministic flux. To this end, we denote \((\varOmega , {\mathscr F}, \mathbb {P})\) a probability space. We assume given a Lipschitz continuous deterministic flux f and random initial data u 0, which satisfies the
Assumption 1 (Assumptions on the Random Input Data)
-
1.
The random initial data u 0 is an \(L^1(\mathbb {R}^d)\) -valued random variable on \((\varOmega , {\mathscr F}, \mathbb {P})\) . It is in particular a strongly Bochner measurable map
$$\displaystyle \begin{aligned} u_0 : (\varOmega, {\mathscr F}) \longmapsto \big(L^1(\mathbb{R}^d), \; {\mathscr B}(L^1(\mathbb{R}^d))\big)\,. \end{aligned} $$(28) -
2.
The map u 0 is also strongly Bochner measurable from \((\varOmega , {\mathscr F}, \mathbb {P})\) with values in the space \(Z = L^1(\mathbb {R}^d) \cap L^\infty (\mathbb {R}^d) \cap BV (\mathbb {R}^d)\) (taking values in the separable Banach space \(L^1(\mathbb {R}^d)\) , the random initial data u 0 is in particular separably valued in Z) introduced in (19), so that
$$\displaystyle \begin{aligned} \varOmega \ni \omega \mapsto u_0(\omega;\cdot) \in Z = (L^1\cap L^\infty\cap BV)(\mathbb{R}^d) \end{aligned} $$(29)is strongly Bochner measurable; here, we equip the space Z in (19), (29) with the norm
$$\displaystyle \begin{aligned} \|u\|{}_Z := \| u \|{}_{L^1(\mathbb{R}^d)} + \| u \|{}_{L^\infty(\mathbb{R}^d)} + TV(u) \;. \end{aligned} $$(30) -
3.
There holds a uniform bound: for some constant \(0< \bar {M} < \infty \) ,
$$\displaystyle \begin{aligned} \| u_0(\omega;\cdot) \|{}_{L^\infty(\varOmega;Z)} \leq \bar{M} < \infty\;, \end{aligned} $$(31) -
4.
The random initial data u 0 satisfies the bounded support assumption (25) with probability one, i.e. there exists a constant 0 < R < ∞ such that
$$\displaystyle \begin{aligned} \mathrm{supp}(u_0(\omega,\cdot)) \subset [-R,R]^d \quad \mathit{\text{with probability}}\; 1 \;. \end{aligned} $$(32) -
5.
The flux function f is bounded on the set of states: for \(\bar {M}\) as in (31), item 3, there holds, with \(S = [-\bar {M},\bar {M}]\) , the bound (27).
Since \(L^1(\mathbb {R}^d)\) and \(C^1(\mathbb {R}^d;\mathbb {R}^d)\) are separable, we may impose on the mapping (28) kth moment conditions
where the Bochner spaces are defined in Sect. 2. We consider the random scalar conservation law (RSCL)
Definition 2 ([46])
A random field u : Ω ∋ ω → u(ω;x, t), i.e., a strongly measurable mapping from \((\varOmega ,{\mathscr F})\) to \(C([0,T];L^1(\mathbb {R}^d))\), is a random entropy solution of the SCL (34) with random initial data u 0 satisfying (28)–(33) for some k ≥ 2 and with a spatially homogeneous flux f(u) if it satisfies the following conditions,
-
(i)
Weak solution:
For \(\mathbb {P}\)-a.e. ω ∈ Ω, u(ω;⋅, ⋅) satisfies the following integral identity
(35)for all test functions \(\varphi \in C_0^1(\mathbb {R}^d \times [0,T))\).
-
(ii)
Entropy condition: For any pair of (deterministic) entropy η and entropy flux Q(⋅) i.e., η, Q j with j = 1, 2, …, d are functions such that η is convex and such that \(Q^{\prime }_j(\cdot ) = \eta ^{\prime }f_j^{\prime }(\cdot )\) for all j, and u satisfies the following inequality
(36)for all deterministic test functions \(0 \le \varphi \in C_0^1(\mathbb {R}^d \times [0,T))\), \(\mathbb {P}\)-a.s.
We remark that it suffices to assume that (36) holds for all Kružkov entropy functions \(\eta (u)=\left |u-k\right |\), where k is any constant, which we assume throughout what follows.
Theorem 2 ([28, Chap. 2, Thms. 5.1,5.2])
Consider the SCL (14)–(15) with spatially homogeneous, bounded flux 
with random initial data \(u_0 : \varOmega \rightarrow L^1(\mathbb {R}^d)\) satisfying Assumption 1 and the kth moment condition (33) for some integer k ≥ 2. Then there exists a random entropy solution \(u : \varOmega \rightarrow C([0, T]; L^1(\mathbb {R}^d))\) which is “pathwise” unique, i.e., for \(\mathbb {P}\mathit{\text{-}}\mathit{\text{a.e.}}\ \omega \in \varOmega \)
, described in terms of the deterministic, nonlinear mapping S(t) from Theorem 1 such that
Moreover, \(u:\varOmega \to C(0,T;L^1(\mathbb {R}^d))\) is \(\mathbb {P}\) -a.s. separably valued and strongly Bochner measurable.
For every k ≥ 1, for every 0 ≤ t ≤ T < ∞, and for \(\mathbb {P}\) -a.e. ω ∈ Ω holds
There exists \(\bar {M}<\infty \) such that
and
Theorem 2 ensures the existence of a unique random entropy solution u(ω;x, t) with finite kth moments for bounded random flux, provided that \(u_0 \in L^k(\varOmega , {\mathscr F}, \mathbb {P}; Z)\).
The deterministic maximum principle (22) and (41) imply, in addition, that \(\mathbb {P}\)-a.e. realization of the random entropy solution u takes values in the state space \(S = [-\bar {M},\bar {M}]\), for \(a.e.\ x\in \mathbb {R}^d\) and for all t > 0.
4 Monte Carlo and Multi-Level Monte Carlo Finite Volume Methods
We present the Multilevel Monte Carlo Finite Volume Method (MLMC-FVM) for scalar conservation laws. We introduce it in several steps: first, we discuss MC sampling of random initial data, second, FV discretization of the samples on the single, fixed triangulation and, finally, its multi-level extension on a hierarchy of possibly unstructured grids.
4.1 Monte-Carlo Method
The MC method for the SCL with random data u 0(ω;x) as in (28)–(31) consists in sampling in the probability space. We also assume (33), i.e., the existence of kth moments of u 0 for some \(k \in \mathbb {N}\), to be specified. We analyze the error in computable numerical approximations of kth order statistical moments of u. For k = 1 we obtain the expected value of the solution random field i.e., \({\mathscr M}^1(u) = \mathbb {E} [u]\). The MC approximation of \(\mathbb {E}[u]\) is defined as the usual statistical sample average: given M independent, identically distributed (“iid” for short) draws of the initial data, \(\widehat {u}_0^i\), i = 1, …, M, the MC estimate of \(\mathbb {E}[u(\cdot ;\cdot ,t)]\) at time t > 0 is the sample average
Here, \(\widehat {u}^i(\cdot ,t)\) denotes the M unique entropy solutions of the M Cauchy Problems (14)–(15) with iid initial data \(\widehat {u}^i_0\). We observe that by
we have from (21)–(23) for M MC samples and for any 0 < t < ∞, for every 1 ≤ p ≤∞, using the triangle inequality,
Using the i.i.d. property of the samples \(\{\widehat {u}^i_0\}^M_{i=1}\) of the random initial data u 0 and the linearity of the expectation \(\mathbb {E}[\cdot ]\), we obtain for any 1 ≤ p ≤∞ from the assumed strong measurability of u 0 in the Banach space Z defined in (29), the bound
As M →∞, the MC estimates (43) converge in \(L^2(\varOmega ;C([0,T];L^p(\mathbb {R}^d)))\) and the following convergence rate bound holds.
Theorem 3
Assume that in the SCL (14)–(15) the random initial data u 0 satisfies Assumption 1 , items 1–5. In particular, u 0 is with probability one compactly supported in space, i.e., there exists a compact domain \(D \subset \mathbb {R}^d\) such that supp(u 0(ω)) ⊂ D for almost every ω ∈ Ω.
Assume, moreover, that the random initial data u 0 is strongly Bochner measurable taking values in the space \(Z = L^1(\mathbb {R}^d)\cap L^\infty (\mathbb {R}^d) \cap BV(\mathbb {R}^d)\) (cp.(29), (30)), and satisfies
Assume further that (29), (31) hold.
Then for every 0 < t < ∞ holds the a priori bound
The MC estimates E M [u(⋅, t)] in (43) converge, as M →∞, to \({\mathscr M}^1(u(\cdot , t)) = \mathbb {E}[u(\cdot ,t)]\) . For \(M \in \mathbb {N}\) , and for every fixed 0 < t < ∞, there holds the error bound
Under Assumption 1 , item 4, we also have for every 0 < t < T
In (50), C(T) is a time dependent constant that also depends on the bounded domain [−R, R]d on which the random initial data is supported with probability 1.
Proof
Under the assumptions of the theorem, by Theorem 2 there exists a unique random entropy solution u.
For any \(v\in L^1(\mathbb {R}^d)\cap L^\infty (\mathbb {R}^d)\) holds \(\| v \|{ }^2_{L^2(\mathbb {R}^d)} \leq \| v \|{ }_{L^1(\mathbb {R}^d)} \| v \|{ }_{L^\infty (\mathbb {R}^d)}\). For every fixed 0 < t < ∞ we have from (22), (23),
Therefore, for every 0 < T < ∞,
which is finite by assumption (47). From this bound follows the MC error bound (49) by referring to the general MC error bound in Corollary 1, with the observation that Hilbert spaces have type p = 2, and type constant 2C t = 1 or directly from (12).
We show the second part: note that the space \(L^1(\mathbb {R}^d)\) is of type 1. From Corollary 1 we cannot expect a MC convergence rate bound in \(L^1(\mathbb {R}^d)\) without extra assumptions.
Suppose therefore now that Assumption 1, item 4, holds, i.e. all realizations of u
0 have compact support in a common set [−R, R]d. Then the bound (27) of the flux f in 
and the finite propagation property, Proposition 2, imply that for every 0 < t < ∞, and \(\mathbb {P}\)-a.s., that the random entropy solution is likewise compactly supported: from (26) it follows that there holds, for every t > 0,
Then, for \(\mathbb {P}\)-a.e. ω,
Squaring both sides and taking expectations, we find
Using (48) and reasoning as before, we arrive at (50). □
Remark 2
The bound (51) can be generalized to k-point correlation functions \({\mathscr {M}}^{(k)}u = \mathbb {E}(u(\cdot ,t,x_1) \ldots u(\cdot ,t,x_k))\), \(x_1,\ldots ,x_k\in \mathbb {R}^d\) with k > 1 of the random entropy solution: from Jensen’s inequality and Fubini’s theorem,
From Theorem 3 we see that \(L^1(\mathbb {R}^d)\) MC convergence rate bounds can be obtained despite L 1 being a Banach space of type 1; however, as already observed in [13] and the references there, this is only possible by an intermediate bound of samples and, for multilevel MC, for error bounds on FV discretizations in Banach spaces of type 1 < q ≤ 2, as introduced in Definition 1. As observed in [48], Theorem 4.1, the assumption of compactly supported initial data, satisfying (25), and bounded flux (27) which imply (26) at positive time t > 0 does afford intermediate \(L^2_\omega L^2_x\) bounds which in turn allow MC convergence rate bounds.
The properties (20)–(24) also hold for FV discretizations. Accordingly, we aim at analogous results for MC FV methods for the random SCL. We next introduce FV methods; rather than presenting a particular scheme, we state several properties required in the ensuing error analysis which are satisfied by several popular FV methods.
4.2 Finite Volume Method (FVM)
So far, the MC method was prescribed under the assumption that “pathwise” entropy solutions \(\widehat {u}^i(\omega ;x,t) = S(\omega ;t) \,\widehat {u}_0^i(\omega ;x)\) for the Cauchy problem (14)–(15) iid initial data samples \(\hat {u}_0^i = u_0(\omega _i;x)\) are available exactly. In practice, numerical approximations of \(S(t)\hat {u}_0^i\) must be computed and the corresponding discretization errors taken into account.
To analyze MC-FVM approximations we impose sufficient conditions on the FVM to afford the Kuznetsov type error bounds for first order FVM for the deterministic SCL (14)–(15); these will be required for the convergence rate bounds of the MLMC FVM as considered in [46, 48] and also for parametric collocation FVM as in [48, Sec.5] in the subsequent chapters. We review the generic first order, explicit FV schemes considered here, as for example in [15, 37, 42].
Denote the time step by Δt > 0 and a triangulation \({\mathscr T}\) of the spatial domain \(D\subset \mathbb {R}^d\) of interest. We assume that \({\mathscr T}\) is a set of open, convex polyhedra \(K\subset \mathbb {R}^d\) with plane faces such that standard conditions on shape regularity hold: if \(K \in {\mathscr T}\) denotes a generic volume, we define
i.e., the maximum inradius in volume \(\overline {K}\) for \(K\in {\mathscr T}\) and define, in addition, for a generic mesh \({\mathscr T}\), the shape regularity constants (where Δx K := diam K)
The meshwidth of triangulation \({\mathscr T}\) is
For any volume \(K\in {\mathscr T}\), we define the set \({\mathscr N}(K)\) of neighboring volumes
We assume that the triangulation \({\mathscr T}\) are regular in the sense that the support size of the FV “stencil” at any element \(K\in {\mathscr T}\) is uniformly bounded i.e.,
with some bound B which is independent of the particular partition \({\mathscr T}\). The global CFL constant is defined by
for constant time step Δt; we also set t n = nΔt. It is determined by a standard CFL condition (see e.g. [28]) based on the maximum wave speed given by the flux bound (27), see Proposition 2.
We discretize (14)–(15) by an explicit, first order FV scheme on \({\mathscr T}\):
where \(H: \mathbb {R}^{(2 k + 1)^d} \rightarrow \mathbb {R}\), with k denoting the size of the stencil of the FV scheme, is continuous and where \(v_{K}^n\) denotes an approximation to the cell average of u at time t n = nΔt.
In our subsequent developments, we write the FVM in operator form. To this end, we introduce the operator \(H_{\mathscr T}(v)\) which maps a sequence \( \underline {v} = (v_K)_{K\in {\mathscr T}}\) into \(H_{\mathscr T}((v_K)_{K\in {\mathscr T}})\). The time explicit FVM (59) takes the abstract form
For the ensuing convergence analysis, we shall assume and use several properties of the FV scheme (60); these properties are satisfied by many commonly used FVM of the form (60), on regular or irregular meshes \({\mathscr T}\) in \(\mathbb {R}^d\).
To state the assumptions, we introduce further notation: for any initial data \(u_0(x) \in L^1(\mathbb {R}^d)\), we define the FVM approximation at time t = 0, \((v^0_{K})_{K\in {\mathscr T}}\) by the cell averages
Interpreting the vector \( \underline {v} = (v_{K})_{K\in {\mathscr T}} \in \mathbb {R}^{\#{\mathscr T}}\) as cell averages, we associate with \( \underline {v}\) the piecewise constant function \(v_{\mathscr T}(x,t)\) defined a.e. in \(\mathbb {R}^d \times (0,\infty )\) by
We denote space of all piecewise constant functions on \({\mathscr T}\) (i.e., the “simple” or “step” functions on \({\mathscr T}\)) by \(S({\mathscr T})\). Given any \(v_{\mathscr T} \in S({\mathscr T})\), we define the (mesh-dependent) norms:
As in [46, 48], we consider FVM schemes in the MC-FVM algorithms which satisfy the following standard assumptions which are analogous to (22)–(24).
Assumption 2
The abstract FV scheme (60) satisfies
-
1.
Stability: ∀t ≥ 0
$$\displaystyle \begin{aligned} \left\|v_{\mathscr T} (\cdot,t)\right\|{}_{L^\infty(\mathbb{R}^d)} &\le \left\|v_{\mathscr T}(\cdot,0)\right\|{}_{L^\infty(\mathbb{R}^d)}, {} \end{aligned} $$(63)$$\displaystyle \begin{aligned} \left\|v_{\mathscr T} (\cdot,t)\right\|{}_{L^1(\mathbb{R}^d)} &\le \left\|v_{\mathscr T}(\cdot,0)\right\|{}_{L^1(\mathbb{R}^d)}, {} \end{aligned} $$(64)$$\displaystyle \begin{aligned} TV (v_{\mathscr T} (\cdot,t)) &\le TV(v_{\mathscr T} (\cdot,0)), {} \end{aligned} $$(65) -
2.
Lipschitz continuity: For any two sequences \( \underline {v} = (v_{K})_{K \in {\mathscr T}}\) , \( \underline {w} = (w_K)_{K \in {\mathscr T}}\) we have
$$\displaystyle \begin{aligned} \left\|H_{\mathscr T} (\underline{v}) - H_{\mathscr T}(\underline{w})\right\|{}_{L^1({\mathscr T})} \le \left\|\underline{v} - \underline{w}\right\|{}_{L^1({\mathscr T})} \end{aligned} $$(66)or, equivalently,
$$\displaystyle \begin{aligned} \left\|H_{\mathscr T} (v_{\mathscr T}) - H_{\mathscr T} (w_{\mathscr T})\right\|{}_{L^1(\mathbb{R}^d)} \le \left\|v_{\mathscr T} -w_{\mathscr T}\right\|{}_{L^1(\mathbb{R}^d)}. \end{aligned} $$(67) -
3.
Convergence: If in the CFL bound (58) the CFL constant \(\lambda = \varDelta t/\varDelta x({\mathscr T})\) is kept constant as \(\varDelta x({\mathscr T}) \rightarrow 0\) , the approximate solution \(v_{\mathscr T}(x,t)\) generated by (59)–(62) converges to the unique entropy solution u of the scalar conservation laws (14)–(15) at \(L^1(\mathbb {R}^d)\) -rate 0 < s ≤ 1: there exists C > 0 independent of Δx such that, as Δx → 0, for every \(\overline {t}\) and for \((\varDelta t)^s \le \overline {t} \le T\) , it holds
$$\displaystyle \begin{aligned} \|u (\cdot, \overline{t}) - v_{\mathscr T}(\cdot, \overline{t})\|{}_{L^1(\mathbb{R}^d)} \le \|u_0 - v_{\mathscr T}^0 \|{}_{L^1(\mathbb{R}^d)} + C \, \overline{t} \,TV (u_0) \,\varDelta x^s\,. \end{aligned} $$(68)
Let us mention that (63)–(65) hold in particular for monotone schemes on Cartesian meshes, see [28, 37]. The classical error analysis of Kuzsnetsov, see e.g. [15], imply the convergence rate s = 1/2 in (68). In case of monotone schemes on general FV meshes, one might lose the bound on the total variation of the approximations, and the convergence rate, i.e., the rate s in (68) is correspondingly reduced, see [8].
The error bound (68) contains an initial data approximation error \(\|u_0 - v_{\mathscr T}^0 \|{ }_{L^1(\mathbb {R}^d)}\). This error vanishes for step function initial data on \({\mathscr T}\) (as, e.g., in the solution of Riemann problems). More generally, this error can be bounded by Δx s provided that u 0 has appropriate regularity: under Assumption 2, for \(u_0 \in BV(\mathbb {R}^d)\) and for the cell-average projection \(v^0_{\mathscr T}\) in (61), we obtain
as s ≤ 1 in (68). Here, the constant C(κ, σ) depends on the stencil size constant σ and the shape regularity constant κ in (57), and (54), respectively.
Explicit FV schemes (59), (60) subject to the CFL stability condition (58) exhibit a discrete finite domain of dependence result analogous to Proposition 2.
Proposition 3 (Discrete Finite Dependence Domain)
Under Assumption 2 and the assumptions of Proposition 2 , in particular under the compact support assumption (25) on the random initial data u 0 , for the explicit FV scheme (53), (61) there holds:
-
1.
the projection of the initial data on triangulation \({\mathscr T}\) , \(v^0_{{\mathscr T}}\) , defined in (61), (62), has compact support independently of \({\mathscr T}\) : there exists c > 0 such that, for all \(0< h({\mathscr T}) \leq 1\) , and with probability 1, holds
$$\displaystyle \begin{aligned} \mathrm{supp}(v^0_{\mathscr T}) \subset [-(1+c)R,(1+c)R]^d \;. \end{aligned} $$(70) -
2.
the discrete solutions satisfy a dependence domain result: with probability 1 and with the constant c > 1 from (70) for every t > 0 holds
$$\displaystyle \begin{aligned} \mathrm{supp}(v_{\mathscr T}(\cdot,t)) \subset [-(1+c)(R + tB) , (1+c)(R + tB)]^d\;, \end{aligned} $$(71)where B denotes the bound (27) on the flux, and where c > 1 is as in (70).
We refer to [42, Chapter 3.6] for a detailed discussion.
Let us finally mention that the work for the realization of scheme (59)–(62) on a bounded domain \(D \subset \mathbb {R}^d\) scales as (using the CFL stability condition (58), i.e., \(\varDelta t / \varDelta x({\mathscr T}) \le \lambda = \mathrm {const.})\)
with the constant implied in \(\mathscr {O}\left ( \cdot \right )\) depending on on the support domain D of the solution.
4.3 MC-FVM
In the Monte Carlo Finite Volume Methods (MC-FVMs), we combine MC sampling of the random initial data with the FVM (60). In the convergence analysis of these schemes, we shall require the application of the FVM (60) to random initial data \(u_0 \in L^\infty (\varOmega ; (L^1\cap L^\infty \cap BV)(\mathbb {R}^d))\): given a draw u 0(x;ω) of u 0, the FVM (60)–(62) produces a family \(v_{\mathscr T}(x,t; \omega )\) of random step functions on \({\mathscr T}\).
Proposition 4
Consider the FVM (60)–(62) for the approximation of the entropy solution corresponding to a draw u 0(ω;x) of the random initial data, satisfying Assumption 1.
Then, if the FVM satisfies Assumption 2 , and provided that u 0 ∈ L k(Ω;Z), the random grid functions \(\varOmega \ni \omega \mapsto v_{\mathscr T} (\omega ;x,t)\) defined by (58)–(62) satisfy, for every \(0 < \overline {t} < \infty \) , 0 < Δx < 1, and every \(k \in \mathbb {N} \cup \{\infty \}\) , the stability bounds
We also have error bounds
Remark 3
-
1.
In order for \( \left \|TV(u_0(\cdot ;\cdot ))\right \|{ }_{L^k(\varOmega )}\) in (75) to be meaningful, a sufficient condition is that \(u_0:\varOmega \to BV(\mathbb {R}^d)\) be strongly measurable, which we assumed in (31).
-
2.
The initial data approximation error term \( \left \|u_0(\cdot ;\cdot ) - v_{\mathscr T}^0(\cdot ;\cdot )\right \|{ }_{L^k(\varOmega ;L^1(\mathbb {R}^d))}\) in (75) can be bounded as in (69) provided that the random initial data u 0 has sufficient regularity: if u 0 : Ω → Z is strongly measurable, and if u 0 ∈ L k(Ω;Z), then (69) implies
$$\displaystyle \begin{aligned} \| u_0 - v_{\mathscr T}^0\|{}_{L^k(\varOmega; L^1(\mathbb{R}^d))} \leq C\varDelta x\;. \end{aligned} $$(76)
This approximation error bound holds without assumption of bounded support on u 0.
4.3.1 Definition of the MC-FVM Scheme
We consider once more the SCL (14)–(15) with random data u 0 and with flux f satisfying (28)–(33). We assume the moment condition u 0 ∈ L k(Ω;Z) for sufficiently large \(k \in \mathbb {N}\). The MC-FVM scheme for the MC estimation of the mean (i.e., the ensemble average) of the random entropy solution is as follows.
Definition 3 (MC-FVM Scheme)
Generate a sample of \(M \in \mathbb {N}\) i.i.d. realizations \(\{\widehat {u}_0^i\}^M_{i=1}\) of initial data, approximated on the triangulation \({\mathscr T}\) by cell average projections (61).
Let \(H_{\mathscr T}(\cdot )\) be a FVM scheme (59)–(62) satisfying Assumption 2. Then the MC-FVM approximations of \({\mathscr M}^k(u(\cdot ,t))\) are defined as statistical estimates from the ensemble
obtained by (60) from the FV approximations \(\widehat {v}^i_{\mathscr T}(\cdot ,0)\) of the M i.i.d initial data samples \(\{\widehat {u}^i_0(x)\}^M_{i=1}\) by (61): specifically, the first moment of the random solution u(ω;⋅, t) at time t > 0, is approximated by the sample average of FV solutions,
4.3.2 Convergence Rates for MC-FVM
We next address the convergence of \(E_M [v_{\mathscr T}]\) to the mean \(\mathbb {E}(u)\).
Theorem 4
Assume that all realizations of the random initial data u 0 are supported on one common, bounded domain \([-R,R]^d \subset \mathbb {R}^d\) for some 0 < R < ∞ and satisfy (28)–(32). Assume further given a FVM (59)–(62) such that (58) holds and such that Assumption 2 is satisfied; in particular, assume that the deterministic FVM scheme converges at rate s > 0 in \(C([0,T]; L^1(\mathbb {R}^d))\) for every 0 < T < ∞, i.e.(68) holds.
Then, the MC estimate \(E_M[v_{\mathscr T} (\cdot ,t)]\) defined in (79) satisfies, for every M, the error bound
where C > 0 depends on the final time T and the domain D, in which the initial data is supported \(\mathbb {P}\) -a.s. but is independent of M and of Δx as M →∞ and as λΔx = Δt ↓ 0.
Proof
The proof of the above theorem proceeds along the lines of the proof of [46, Thm. 4.6]. However, we point out that there was an error in the argument of the proof of [46, Theorem 4.6] due to the incorrect derivation of a direct MC sampling convergence rate in the type one Banach space \(L^1(\mathbb {R}^d)\). On the other hand and as mentioned in the previous section, we may use the local support assumptions on the initial data, and the finite speed of propagation implied by hyperbolicity, to obtain FV convergence rate bounds in the type 2 space \(L^2(\mathbb {R}^d)\) from which follows the claimed convergence rate.
For fixed t > 0, we have
Term I is a MC error which can be bounded by (50).
Term II is essentially a discretization error bound. By the (pathwise) FV error bounds (68) and by (21)–(24) and Assumption 2 by the triangle inequality that
□
The initial data approximation error \(\|u_0 - v_{\mathscr T}^0\|{ }_{L^2(\varOmega ; L^1(\mathbb {R}^d))}\) can be bounded by Δx as indicated in Remark 3, item 2.
4.3.3 Work Estimates
To calculate the error versus computational work, we estimate the asymptotic complexity of computing the estimators along the lines of [48]. In doing this, we assume that the computational domain \(D \subset \mathbb {R}^d\) is bounded and suitable boundary conditions are specified on ∂D. In this bounded, computational domain D, the work for one time step (59), (60) is of order \(\mathscr {O}\left (\varDelta x^{-d}\right )\)(with \(\mathscr {O}\left (\cdot \right )\) depending on the size of the domain and on the size of stencil employed in the FV scheme) we find from the CFL condition (58) that the total computational work to obtain \(\{v_{\mathscr T}(\cdot ,t)\}_{0 < t \le T}\) in D is by (72)
The work for the computation of the MC estimate \(E_M[v_{\mathscr T}(\cdot ,t)]\) is assumed to scale as
The bound (80) allows to infer convergence order estimates in terms of work. To derive these, we choose M −1/2 ∼ Δx s in (80). Setting the implied constant equal to one results in M = ⌈Δt −2s⌉. Inserting in (82) yields
so that we obtain from (80)
Regarding the convergence rate in the estimate (84), for the deterministic FV scheme holds
The bound on the FV error, (68), becomes when written in terms of work, equal to
Ignoring initial data approximation errors, which are negligible in comparison to the computational work for the time marching, the exponent − s/(d + 1) for the deterministic FVM as compared to − s/(d + 1 + 2s) for the MC-FVM. For low order FV schemes (i.e., for small values of the convergence rate s) and in space dimensions d = 2, 3, we observe a considerably reduced rate of convergence of the MC-FVM. For high order FV schemes, we recover in (84) the MC rate 1/2 of the error in terms of work.
4.4 Multilevel MC-FVM
Next, we present and analyze a scheme that allows us to achieve a better accuracy versus work bound for the random initial data u 0, compared to the standard MC-FVM error bound (84). The Multilevel Monte Carlo Finite Volume (MLMC-FVM) scheme is based on MC sampling with level dependent sample sizes M ℓ on different levels ℓ of resolution of the FVM. Throughout, we assume the explicit FV scheme satisfies Assumption 2 and the CFL stability condition (58). To define the MLMC-FVM, we start by reviewing notation as used in [48].
4.4.1 Notation
The MLMC-FVM is defined as a multilevel discretization in x and t with level dependent numbers M ℓ of samples. To this end, we assume we are given a family \(\{{\mathscr T}_\ell \}^\infty _{\ell = 0}\) of nested triangulations of \(\mathbb {R}^d\) such that the mesh width
where K denotes a generic FV cell \(K\in {\mathscr T}\). We also assume the family \({\mathfrak M} = \{{\mathscr T}_\ell \}_{\ell = 0}^\infty \) of meshes to be shape regular; if \(K \in {\mathscr T}_\ell \) denotes a generic cell, we recall, for a generic mesh \({\mathscr T} \in {\mathfrak M}\), the shape regularity constants \(\kappa ({\mathscr T})\) defined in (54). We say that the family \({\mathfrak M}\) of meshes is κ-shape regular, if there exists a constant \(\kappa ({\mathfrak M})<\infty \) such that with ρ K denoting the diameter of the largest ball inscribed into K
For a mesh hierarchy \({\mathfrak M} = \{{\mathscr T}_\ell \}_{\ell =0}^\infty \), we denote
4.4.2 MLMC-FVM
The MLMC FVM consists in estimates of \(\mathbb {E}[u(\cdot ,t)]\) obtained by replacing u(⋅, t) by a FV discretization, on a sequence \(\mathfrak {M}\) of discretizations \(\{ {\mathscr T}_\ell \}_{\ell \in \mathbb {N}_0}\) which we assume to be nested. We denote in the present section the FV approximation \(v_{\mathscr T}\) on triangulation \({\mathscr T}\in {\mathfrak M}\) by v ℓ (⋅, t). On \({\mathscr T}_\ell \in {\mathfrak M}\), the CFL condition (58) takes the form
We assume the CFL constant λ > 0 to be independent of ℓ and of the input realization ω; this will allow for deterministic error vs. work bounds; we refer to [49] for a discussion of error vs. work of MLMC for nonuniform (log-gaussian) random inputs.
As the FV scheme is CFL stable, we may generate a sequence \(\{v_\ell (\cdot ,t)\}^\infty _{\ell = 0}\) of stable FV approximations on triangulation \({\mathscr T}_\ell \) for time steps of sizes Δt ℓ which satisfy the CFL condition (89) with respect to mesh \({\mathscr T}_\ell \in {\mathfrak M}\). We set in what follows v −1(⋅, t) := 0. Then, given a target (finest) level \(L \in \mathbb {N}\) of spatial resolution, we may use the linearity of the expectation operator to write, as is customary in MLMC analysis (see, e.g., [27])
We next estimate each term in the sum (90) by a Monte-Carlo method with a level-dependent number of samples, M ℓ , to obtain the MLMC-FVM estimator,
Here, \(E_M[v_{\mathscr T}(\cdot ,t)]\) is the standard MC estimator defined in (79), and v ℓ (⋅, t) denotes the FV solution on \({\mathscr T}_\ell \), computed under the CFL assumption (89), with Δt ℓ ≤ λΔx ℓ where \(\varDelta x_\ell := \varDelta x({\mathscr T}_\ell )\) denotes the meshwidth at mesh level ℓ (see (55)) and where the CFL constant λ > 0 is independent of ℓ. We emphasize that the form of the estimator (90) implies that the same draw of the random initial data should be approximated on two successive meshes in the hierarchy.
4.4.3 Convergence Analysis
The MLMC-FVM mean field error
for 0 < t < ∞ and \(L \in \mathbb {N}\) was analyzed in [46] for the SCL (13) with random initial data and deterministic flux. Analogous results for the more general SCL with random fluxes was shown in [48]. The choice of the sample sizes \(\{M_\ell \}^\infty _{\ell =0}\) is such that, for every \(L \in \mathbb {N}\), the MLMC error (92) is of order (Δx L )s, where s is the order of convergence in the Kuznetsov type error bound (68). The design of MLMC-FVM is based on a judicious choice of MC sample numbers \(\{M_\ell \}^\infty _{\ell =0}\) at the discretization levels ℓ. To derive it, we observe that for each L, the error bound (92) holds with work bounded by
The MLMC convergence analysis in [46] used incorrectly a MC convergence estimate for the space \(L^1(\mathbb {R}^d)\) which is a Banach space of type 1. This error was rectified in a recent paper [48], where the following bound on the variance of the FV details was shown:
Theorem 5 ([48, Thm. 4.7])
Suppose that Assumption 1 , items 1–5 hold, and that, moreover, (28)–(32) and (87)–(89) are valid. Then, for any sequence \(\{M_\ell \}^\infty _{\ell = 0}\) of MC sample numbers at mesh level ℓ, we have for the MLMC-FVM estimate E L[u(⋅, t)] in (91) the error bound
where C is a constant that depends on the final time T < ∞, the initial data and on the bounded domain D which contains, according to (52), the support of u(t) with probability one, but is independent of L.
Proof
We calculate for any t ∈ [0, T]
In complete analogy with the estimation of term II in proof of Theorem 4, the term I in the above estimate can be readily estimated in terms of the spatio-temporal discretization error of the FV scheme at the finest mesh resolution with diameter Δx L as follows,
To estimate term II in the above estimate, we use the discrete finite dependence domain result, Proposition 3, and the bounded support assumption (32) on the random initial data and proceed as follows,
In the final estimate, we used the compact support assumption (50) and in the final step, we used the standard Hilbert space MC estimate (12) for the detail v ℓ − v ℓ−1. Accordingly, we need to bound the variance of the details v ℓ − v ℓ−1 in the (Hilbert) space \(L^2(\mathbb {R}^d)\) according to
Note that the use of the (Hilbertian) \(L^2(\mathbb {R}^d)\) norm in the error bound entails the convergence rate s/2 of the FV detail v ℓ − v ℓ−1, where 0 < s ≤ 1 denotes the \(L^1(\mathbb {R}^d)\) convergence rate of the (deterministic) FV approximation. Substituting the above in the estimate for term I and using the stability of the numerical solution at the coarsest level of discretization Δx 0, we arrive at (95). □
The error bound (95) is then used to select MC sample numbers M ℓ at discretization level ℓ to achieve a prescribed tolerance \(\varepsilon \sim \varDelta x_L^{s}\), with minimal computational work.
A (standard in MLMC by now) Lagrange multiplier argument (see, e.g., Giles [27] and references therein) allows to solve the corresponding constrained minimization problems results in sample number choices obtained, for example, in [48] for 0 < s < d + 1,
with ∼ denoting equivalence uniform with respect to L and ℓ.
As in [46], we use the sample numbers M ℓ in (97) to obtain the following error estimate in terms of work
The complexity estimate (98) shows that the MLMC FVM can be more efficient than the MC FVM (84), in terms of computational work that needs to be performed for obtaining the same error. However, to achieve a comparable error in \(L^2(\varOmega ;L^1(\mathbb {R}^d))\), the MLMC method is more expensive than a single deterministic solve.
Remark 4
The above discussion on random entropy solutions and (ML)MC methods considered the simplest case of a scalar conservation law with random initial data. These notions and methods were extended to the case where the flux function in a scalar conservation law is random. In a recent paper [48], where the appropriate notion of random entropy solutions were defined and shown to exist, provided that the uncertainty in the flux satisfied certain assumptions, which ensure the random flux to be Bochner measurable and \(\mathbb {P}\)-a.s. separably valued in the space of Lipschitz continuous flux functions. Both the MC-FV and MLMC-FV methods were analyzed in this context and the MLMC-FV method was shown to satisfy the same error vs computational work i.e., (98) as in the case of deterministic fluxes and random data. Consequently, the MLMC method is significantly more efficient than the corresponding MC-FV method. We refer to [48] for details.
5 Statistical Moments
The error bounds for the MLMC-FVM obtained up to this point addressed the numerical estimation of the “ensemble average”, or mean-field. Here, we briefly comment on efficient numerical approximation of 2- and k-point correlation functions of random solutions. When the physical problem is posed in d spatial variables, spatial k-point correlation functions of random or of statistical solutions can be represented (under the provision of sufficient regularity) as deterministic functions of kd variables.
The “natural”, FV approximation of k-point spatial correlations of random entropy solutions as well as of correlation margins of statistical EMV solutions introduced in [17, 18], will involve k-fold (algebraic) tensorisation of (finite dimensional, by the bounded support assumption (32) on the random initial data, and by the corresponding bounded support property (71) of FV approximations implied by the uniform hyperbolicity of the SCL). This can increase computational complexity due to the low convergence rate 1/2 of MC sampling, and to the so-called “curse of dimensionality”, which entails complexity \(\mathscr {O}\left (\varDelta x^{-kd-1}\right )\) in k-point correlation estimation. This can be prohibitive, in particular in space dimension d = 3, even for two-point correlations where k = 2. Two algorithmic strategies are next presented which allow, to some extent and under appropriate regularity conditions, to reduce the computational complexity: first, the MC statistical estimation of kth central statistical moments in the physical dimension D as analyzed recently in [3], and second, k-fold sparse tensor products of FV solutions in the physical domain \(D\subset \mathbb {R}^d\) as proposed in [46]. They render k-point correlations in \(D^k\subset \mathbb {R}^{kd}\) numerically accessible in \(\mathscr {O}\left (\varDelta x^{-d-1}|\log \varDelta x|{ }^{k-1}\right )\) operations.
5.1 Estimation of kth Order Central Statistical Moments
Given a random entropy solution u, a “natural” MC estimator based on M iid samples for the kth central moment of u(⋅;x, t) reads
assuming availability of exact solution samples u i of the random entropy solution. The estimator (99) is to be interpreted pointwise w.r. to x ∈ D and t ∈ [0, T]. It is, however, well-known to be a statistically biased estimator. Unbiased estimators are known. For example,
are unbiased estimators of \({\mathscr {M}}^2(u)\) and \({\mathscr {M}}^3(u)\). For k ≥ 4, unbiased estimators \(\tilde {S}^k_M[u]\) can be obtained as polynomial expressions of \(S^r_M[u]\) for r = 1, …, K which are, however, not unique. We refer to [3, Lemma 3] for details.
A MLMC estimator of \({\mathscr {M}}^k(u)(x,\ldots ,x;t)\) is introduced and analyzed in [3, Theorem 1].
As the corresponding algorithms only access the FV solver through iid samples of the random initial data and random flux, respectively, they are nonintrusive and embarrasingly parallel. Operating only in the physical domain \(D\subseteq \mathbb {R}^d\), they do not require additional data structures for tensorization of FV solutions. Central statistical moments \({\mathscr {M}}^k(u)(x,\ldots ,x;t)\) can, however, also be numerically approximated as “diagonals” of statistical k-point correlations \({\mathscr {M}}^k(u)\). We discuss this next.
5.2 Estimation of k-Point Spatial Correlations
The work to form a single tensor product over a bounded computational domain \(D\subset \mathbb {R}^d\) (such as, e.g., the support domain of the solution at time t in (26)) grows, ignoring timestepping, as O(Δx −kd) which may entail a computational effort that is, for moment orders k ≥ 2, prohibitive. To reduce the complexity of k-point correlation function estimation, a so-called “sparse grid” or “sparse tensor product” approach was proposed in [2, 46, 62]. We refer to [31, 53, 58] and the references there for general presentations of sparse tensor product spaces.
5.2.1 k-Point Correlation Estimation by Sparse Tensorization of FV Solutions
As is standard in multi-resolution analysis, the cell-average projections \(P_\ell : L^1(\mathbb {R}^d)\rightarrow S_\ell \), defined in (88), (104), allow us to introduce spaces of increments or details in the FV mesh hierarchy \({\mathfrak M} = \{{\mathscr T}_\ell \}_{\ell =0}^\infty \):
where P −1 := 0 so that W 0 = S 0. Then, for any \(L\in \mathbb {N}_0\), we have the multilevel decomposition
The k-point correlations (v L (⋅, t))(k) of FV solutions at time t > 0 belong to the (algebraic) tensor product space
In the numerical realization of 2- and k point correlation functions and correlation margins of measure valued solutions, the computational realization of approximations in the tensor product space (S L )(k) is necessary. To formulate it, we introduce the k-fold algebraic tensor products of the FV cell-average projections by
In the case that N L := dimS L < ∞ (as e.g. when the spaces S ℓ are only defined on a bounded domain \(D\subset \mathbb {R}^d\) such as the “support box” (26) in Proposition 2) then \(\mathrm {dim}((S_L)^{(k)}) = N_L^k\) which is prohibitive. Sparse Tensor approximations of k-point correlation functions, (v(⋅, t))(k) are “compressed” FV approximations which involve FV spaces of piecewise constant functions on coarser meshes. They are defined in terms of the increment space W ℓ in (101) by
where \(| \underline {\ell }|{ }_1 := \ell _1+\ldots +\ell _k\) and where algebraic tensor products are implied. Note that a realization of the sparse tensor product space \(\widehat {(S_L)}^{(k)}\) according to its definition (105) requires construction of explicit bases for W ℓ in (101); on unstructured, simplicial triangulations \({\mathscr T}\) as in our Assumption 2 such bases can be numerically constructed by agglomeration, see, e.g. [1]. A one-scale FV solution on the finest mesh \({\mathscr T}_L\) can be converted to a ML representation in O(N L ) operations by the so-called pyramid scheme (see, e.g., [5, pp. 225–294]). If the mesh family \({\mathfrak M}\) used in the pathwise FV approximation (see Assumption 2) is generated by recursive dyadic refinements of the initial triangulation \({\mathscr T}_0\), when N L = dimS L < ∞ (as is the case e.g. on bounded domains \(D\subset \mathbb {R}^d\)) it holds (see, e.g. [53, 58])
Having at hand the sparse tensor product space \(\widehat {(S_L)}^{(k)}\) in (105), we also define the sparse tensor projection
We refer to [31, 58] and the references there, from where we briefly recapitulate approximation properties of sparse tensor product projections: for any function U(x 1, …, x k ) which belongs to \((W^{s,1}(\mathbb {R}^d))^{(k)}\) being the space of functions of k variables \(x_1,\ldots ,x_d \in \mathbb {R}^d\) which are, with respect to each variable, in \(W^{s,1}(\mathbb {R}^d)\), it holds
where C > 0 is independent of Δx L (it depends only on k, d and the shape regularity of the family \({\mathfrak M}\) of triangulations, but is independent of Δx L ).
5.2.2 Sparse MLMC-FVM Estimator
The MLMC sparse FV estimator is based on a sparse tensor product FV approximation for each MC sample. To define it, we recall that E M [⋅] denotes the MC estimate based on M samples): for a given sequence \(\{M_\ell \}_{\ell =0}^L\) of MC sample numbers at level ℓ = 0, …, L, the sparse tensor MLMC estimate of \({\mathscr M}^k[u(\cdot ,t)]\) is, for 0 < t < ∞, defined by
We observe that (109) is identical to (103) except for the sparse formation of the k-point correlation functions of the FV solutions corresponding to the initial data samples \(\hat {u}_0^{i}\). In bounded domains, this reduces the work for the formation of the k-point correlation function from \(N_L^k\) to O(N L (log2 N L )k−1) per sample at mesh level L. As is well known (see, e.g. [31, 58]) use of sparse rather than full tensor products essentially preserves (i.e., up to logarithmic w.r. to Δx terms) the order s of FV convergence of sparse tensor product k point correlation function approximations.
5.2.3 Combination Formula
Sparse tensor products are particularly easy to realize when the FV scheme already produces FV solutions to SCLs in MRA format. Such schemes are nonstandard, but available even on unstructured meshes as we admit in Assumption 2, in a development [25, 50] originating in the seminal work of A. Harten [1, 4]. Often, however, only single-level (one-scale) numerical FV approximations on triangulations \({\mathscr T}_\ell \), ℓ = 0, …, L are available. In order to realize the MLMC-FV estimator (109), for each realization the approximations must be converted to a MR representation. This can be achieved also on unstructured meshes in linear complexity by the so-called pyramid scheme (see, e.g., [52] for a definition and an algorithm).
An alternative approach which obviates MR based numerical methods is the so-called combination formula, as proposed for this purpose (in a different context) in [32, Lemma 12, Thm. 13]. For the projector \(\widehat {(P_L)}^{(k)}\) in (107), the combination identity
holds. The combination identity (110) implies that sparse tensor MC-FV approximations of k-point correlation functions can be numerically built from (pointwise) products of standard, one-scale FV approximations of the SCL (13)–(15) with iid samples of the random initial data u 0 on mesh levels \( \underline {\ell } := (\ell _1,\ldots ,\ell _k)\). When inserted into (109), the combination identity (110) provides an explicit realization of the MLMC-FVM estimator of k-point correlations of random entropy solutions, based exclusively on (parallel) standard FV solves on all mesh levels.
5.2.4 Error Bounds and Complexity Analysis
We can now generalize Theorems 4 and 5 to sparse tensor MLMC-FV estimates for the kth moments of random entropy solutions; it also applies to estimates of correlation measures of entropy statistical solutions as introduced in [19].
Theorem 6
Assume that the random initial data u 0 satisfies Assumption 1 , items 1–4 and that the FV scheme satisfies Assumption 2 , items 1–3. In particular, assume that the deterministic FV scheme converges at rate s > 0 according to (68) and that for u 0 , the bounded support Assumption 2 , item 4, (32) holds.
Assume further that the FV scheme satisfies the CFL condition (58) and that the random initial data u 0 is Bochner-integrable of order 2k in the spaces \(Z=(L^1\cap L^\infty \cap BV)(\mathbb {R}^d)\) and in \(W^{s,1}(\mathbb {R}^d)\) , i.e.
Then, MLMC-FVM estimator \(\widehat {E^{L,(k)}}[u(\cdot ,t)]\) defined in (109) satisfies, for every sequence \(\{M_\ell \}_{\ell =0}^L\) of MC samples, the error bound
Here, the constant implied in \(\lesssim \) depends on the order k of the moment to be estimated, on the physical space dimension d, and on the support size constant R > 0 in the bounded support assumption (32).
Then, the total work to compute the MLMC estimates \(\widehat {E^{L,(k)}}[u(\cdot \,;t)]\) is bounded by (with O(⋅) depending on the size of D)
Based on Theorem 6, we infer that the choice (97) of numbers M ℓ of MC samples at level ℓ should also be used in the MLMC estimation of k-point correlation functions for k > 1, provided the order s of the underlying deterministic FVM scheme (59)–(61) satisfies
In particular, in a bounded domain \(D\subset \mathbb {R}^d\) containing the bounded support in (52),
for any 0 < s′ < s (with constant growing as 0 < s′→ s ≤ 1). The computational domain D can, in particular, contain the bounded support domains of the exact and discrete solutions at time t > 0, as indicated in (71), (52).
6 Monte Carlo and Multi-Level Monte Carlo Methods for Systems of Conservation Laws
6.1 General Considerations
We consider the general system of conservation laws (1), with random initial data in (115b) as well as possibly random coefficients and random flux functions in (115a). A notion of random entropy solutions can be defined for this general case, analogous to Definition 2 for scalar conservation laws. We refer to [47] for details. However, there are no well-posedness results for random entropy solutions for systems as even the underlying deterministic problem may not be well-posed, particularly in several space dimensions [6]. One approach to developing numerical approximations in this case is to assume existence of random entropy solutions and to design efficient methods for numerical approximations of their solutions:
It is fairly straightforward to extend the MCFV scheme, given in Sect. 4.3.1, to general, nonlinear hyperbolic systems of conservation laws with random inputs. A convergence rate estimate, analogous to (80) can be proved, provided that one postulates a convergence rate, analogous to (68), for the underlying spatio-temporal FV discretization, see [47]. Similarly, the MLMC method, as described in Sect. 4.4 can also be readily extended to this general case and a convergence rate estimate, similar to (95), once the underlying spatio-temporal discretization converges like in (68) or at least a estimate of the type (96) holds. Consequently, a complexity estimate as (98) can be shown under these assumptions, demonstrating that the MLMC-FV method is more efficient than the MC-FV method.
6.2 Numerical Experiments
We present a few numerical experiments involving systems of conservation laws to illustrate the robustness of the MLMC method and its comparison with the Monte Carlo method.
6.2.1 Uncertain Orszag-Tang Vortex
This test is taken from [47], section 6.2. The system of conservation laws under consideration are the ideal magnetohydrodynamics (MHD) equations of plasma physics. We consider the ideal MHD equations on the two-dimensional domain [0, 1]2 with periodic boundary conditions. The random initial data is an uncertain version of the well-known Orszag-Tang benchmark test problem. We consider a random initial data with 8 sources of uncertainty, namely in the amplitudes of the initial density and pressure, phases of the initial sinusoidal velocity fields and the phases and amplitude of the initial solenoidal magnetic fields. The mean and the variance of the density, computed at time T = 1.0 with an MLMC-FV method, with eight levels of resolution, a finest mesh of 40962 and with four samples at the finest level, with the underlying FV method using a HLLC Riemann solver, a second-order WENO reconstruction and upwind treatment of the Godunov-Powell source term [23], are shown in Fig. 1. In this case, one computes a reference solution with the above configuration and calculates the L 2(Ω, L 1(D)) error for both the mean and variance, with MC and MLMC methods (of both first and second order spatio-temporal discretizations). The errors for the mean and variance are plotted in Figs. 2 and 3, respectively. They show that in this example, the MLMC FV method is at least 50–60 times faster than the single-level MC FV method for the mean and 10–20 times faster for the variance, to achieve a prescribed error tolerance in the engineering range of accuracy. Thus, this justifies the complexity estimates, described here, at least for this example.
Uncertain Orszag-Tang vortex solution at t = 1.0 using MLMC-FVM (8 sources of uncertainty). Left: Convergence of the sample mean of random density. Right: Convergence of the sample variance of the random density. Reproduced from [57]
Convergence of sample mean in the uncertain Orszag-Tang vortex simulation (8 sources of uncertainty). Left: Error vs. Mesh resolution. Right: Error vs. Runtime. Reproduced from [57]
Convergence of sample variance in the uncertain Orszag-Tang vortex simulation (8 sources of uncertainty). Left: Error vs. Mesh resolution. Right: Error vs. Runtime. Reproduced from [57]
6.2.2 A Random Kelvin-Helmholtz Problem
This numerical example is taken from a recent paper [18] and the MLMC computations are presented in [45]. We consider the compressible Euler equations in the two-dimensional domain [0, 1]2 with periodic boundary conditions. The uncertainty arises due to the initial data being a (very small) random perturbation of the classic Kelvin-Helmholtz problem, see [18], with 20 sources of uncertainty in the initial data. The mean and variance of the density, computed with a Monte Carlo method, on a Cartesian 10242 grid and with 400 MC samples are shown in Fig. 4 (Top Row). The underlying FV scheme is the third-order entropy stable TeCNO scheme of [16]. Surprisingly for this test case, the variance of the solution is at least three orders of magnitude higher than the variance of the initial data. This amplification of variance is due to the generation of structures at smaller and smaller scales, when the shear flow interacts with the contact discontinuity. In this particular case, the MLMC method provides no gain in computational efficiency over the standard Monte Carlo method. This is depicted in Fig. 4 (Bottom row, Left), where the L 1 difference in the mean of the density, computed with the MLMC and MC methods, at the same grid resolution for the finest grid and the same number of samples at the finest grid resolution of MLMC, with respect to an MC reference solution computed with 1024 samples, is compared. The results show that error due to MLMC is comparable to the error due to the MC calculation, provided that the number of samples at the finest grid level of the MLMC calculation is the same as the number of MC samples. Thus, in this case, the coarse levels of the MLMC method do not increase the accuracy of the computation and are redundant. Given this observation, it is clear that an error estimate of the form (95) cannot hold for this particular example. In fact, even an error estimate of the form (68) for the underlying spatio-temporal discretization, does not hold for this example. We see this from Fig. 4 (Bottom row, Right) where the difference in L 1 between two successive mesh resolutions for a single sample is shown. This figure show that the error remains constant with respect to resolution and the underlying FV scheme does not converge for this particular test case. It was also shown in [45] that even weaker convergence bounds, such as the variance of the difference between successive resolutions (96), does not hold for this particular problem, as structures at even smaller scales are generated upon mesh refinement.
UQ for the random Kelvin-Helmholtz problem. Top Row: Density at time T = 2 computed with MC method and TeCNO3 scheme with the algorithm proposed in [18] Left: Convergence of the sample mean, Right: Convergence of the sample variance. Bottom Row Left: Comparison between MC and MLMC method with respect to error in mean of the density with respect to a reference solution (Reproduced from [45]). Bottom Right: Lack of convergence for a single sample for the density (reproduced from [45])
7 Measure-Valued and Statistical Solutions
It is interesting to note that the Monte Carlo and Multi-level Monte Carlo methods converge for the previous numerical experiment, as shown in Fig. 4 (bottom left), even though the underlying spatio-temporal discretization may not converge in L 1, as shown in Fig. 4 (bottom right). What exactly do the (ML)MC-FV computations converge to in this case?
7.1 Measure-Valued Solutions
This question was partially answered in recent papers [17, 18] and references therein. There, the authors proved that a Monte Carlo based algorithm, together with an entropy stable scheme such as the TeCNO scheme of [16], converges to an entropy measure valued solution of the underlying system of conservation laws (1). Measure valued solutions were first proposed by DiPerna [14] and are in fact Young measures i.e., space-time parametrized probability measures on the phase space \(\mathbb {R}^N\) of the system (1). Let \(D \subset {\mathbb {R}}^d\) be the domain and \(D_t := D \times {\mathbb {R}}_+\), we define Young measure from D
t
to \({\mathbb {R}}^N\) as a map which associates to each point (x, t) ∈ D
t
a probability measure on \({\mathbb {R}}^N\). More precisely, a Young measure is a weak* measurable map 
, meaning that the mapping
The set of all Young measures from D
t
into \({\mathbb {R}}^N\) is denoted by 
. Given this notation for Young measures, one can rewrite the following system of N- conservation laws,
in terms of the following measure-valued Cauchy problem,
with possibly Young measure-valued initial data σ x . The above system (116) has to hold in the sense of distributions. Entropy (admissibility) conditions can be imposed by interpreting an associated entropy inequality in the Young measure sense [14]
Global existence of measure-valued solutions was shown recently in [17, 18] and references therein, by proving convergence of the following Monte Carlo based ensemble averaging algorithm.
Algorithm 1.
Let the initial data for an underlying time-dependent PDE (116) be given as a Young measure \(\sigma \in {\mathbf Y}(D,{\mathbb {R}}^N)\) i.e., a Young measure \(D \mapsto \mathscr {P}({\mathbb {R}}^N)\).
-
Step 1: Let \(u_0: \varOmega \mapsto L^{p} ({\mathbb {R}}^d)\) be a random field on a probability space \((\varOmega ,\varSigma ,\mathbb {P})\) with law σ, i.e., \(\sigma (E)=\mathbb {P}(u_0(\omega )\in E)\).
-
Step 2: Evolve the initial random field by applying a suitable numerical scheme, with solution map \({\mathscr S}^{\varDelta }_{t}\), to the initial data u 0(ω) for every ω ∈ Ω, obtaining an approximate random field \(u^\varDelta (\omega ; \cdot ,t) := {\mathscr S}^{\varDelta }_t u_0(\omega ;\cdot )\).
-
Step 3: Define the approximate measure-valued solution ν Δ as the law of u Δ with respect to \(\mathbb {P}\), i.e. for all Borel sets \(E \subset {\mathbb {R}}^N\),
$$\displaystyle \begin{aligned}\nu^{\varDelta}_{x,t} (E) = \mathsf{\mathbb{P}}\left(u(\omega; x,t) \in E\right). \end{aligned}$$
It was shown in [18, Appendix A.3.1] that ν Δ are indeed Young measures. The existence of a random field u 0 with a given law σ, as required in Step 1, is guaranteed by proposition A.3 of [18].
The numerical method in Step 2 of Algorithm 1, can be appropriate structure preserving Finite Volume Methods, such as the arbitrary high-order entropy stable TeCNO schemes of [16]. The last ingredient in our numerical approximation of measure-valued solutions is to find, and approximate, the random field u 0(ω;x) which appears in Algorithm 1, resulting in the following algorithm.
Algorithm 2.
Let Δ = (Δx 1, …, Δx d ) denote the grid size parameter and let \(M\in {\mathbb {N}}\). Let further \(\sigma ^{\varDelta }\in {\mathbf Y}({\mathbb {R}}^d,{\mathbb {R}}^N)\) denote the initial Young measure.
-
Step 1: For some probability space \((\varOmega ,\varSigma ,\mathbb {P})\), draw M i.i.d. random fields \(u_0^{\varDelta ,1},\dots ,u_0^{\varDelta ,M}:\varOmega \times {\mathbb {R}}^d \to {\mathbb {R}}^N\), with [the same] law σ Δ.
-
Step 2: For each k and for a fixed ω ∈ Ω, use a suitable numerical scheme to numerically approximate the conservation law (115a) with initial data \(u_0^{\varDelta ,k}(\omega )\). Denote \(u^{\varDelta ,k}(\omega ;\cdot ,t) = {\mathscr S}^{\varDelta }_tu_0^{\varDelta ,k}({\omega ;\cdot })\) as the computed solutions.
-
Step 3: Define the approximate measure-valued solution
$$\displaystyle \begin{aligned} \nu^{\varDelta,M}_{x,t} := \frac{1}{M}\sum_{k=1}^M \delta_{u^{\varDelta,k}({\omega;x,t})}. \end{aligned} $$(117)
Note that, as in any Monte Carlo method, the approximation ν Δ, M depends on the choice of ω ∈ Ω, i.e. on the choice of seed in the random number generator. However, one can prove that the convergence rate of approximation is independent of this choice, P-almost surely.
The approximate solutions ν Δ, M were proved to converge to an entropy measure-valued solution of (116) as (Δ, M) → (0, ∞) in [18]. This convergence is in the weak-∗ topology on Young measures that amounts to convergence of one-point statistical quantities of interest such as the mean, variance, point statistics and probability density functions etc. Thus, the results of Fig. 4 are justified, mathematically. Furthermore, the computations of [18] also demonstrated that the measure-valued solution may not be atomic even if the initial data is an atomic young measure concentrated on a L 1 function. Thus, there seems to be no fully deterministic version of multi-dimensional systems of conservation laws and the initial value problem for (115), hitherto considered deterministically, should in fact be considered as a problem in uncertainty quantification (UQ).
Measure-valued solutions for (116) exist for all times ([17] and references therein) and are able to capture limits of numerical approximation of systems of conservation laws (115). They also serve as an UQ framework within which the random initial data is represented as a Young measure (or point probability distribution). However, measure-valued solutions are not necessarily unique, particularly when the initial data is non-atomic. This holds true even for scalar conservation laws, see for instance example 9.1 in [17], even for the one-dimensional Burgers’ equation. Thus, measure-valued solutions need to be augmented with additional constraints in order to recover uniqueness. This is consistent with the observations, reported in [17, 18], that the computed measure valued solution when realized as a limit of the MC-FV algorithm, is stable with respect to the choice of numerical method and with respect to perturbations of the underlying random initial data. We refer to [40] for numerical approximation of EMV solutions and convergence analysis for a combined MC FV method for the velocity formulation of the incompressible Euler equations.
7.2 Statistical Solutions
An attempt to constrain measure-valued solutions in order to recover uniqueness has been made recently in [19]. In this paper, the authors propose a concept of statistical solutions of systems of conservation laws as a suitable solution paradigm as well as computational UQ framework. Statistical solutions of the Navier-Stokes equations in the sense of Foias and Prodi [20] are time-parametrized families of probability measures on a L p function space. We refer to the surveys [21, 41] for their mathematical theory for the incompressible Navier-Stokes equations.
In these references, statistical solutions are time-dependent probability measures on divergence free L 2 functions that evolve based on either Cylindrical moments (Liouville equation) or Characteristic functionals (Hopf equation) resulting in a functional differential equation on an infinite-dimensional space.
Although a viable concept for viscous flows such as the incompressible Navier-Stokes equations, it is unclear how the statistical solutions in the sense of [21] can be extended to inviscid problems such as systems of conservation laws (115). Moreover, probability measures on L p spaces are non-local and local statistical quantities such as one-point statistics or multi-point correlations are hard to interpret in this setting. Hence, the linkage between statistical solutions (in the sense of [21] or of the closely related notion of statistical solutions introduced by Vishik and Fursikov in [61]) and measure-valued solutions is unclear.
These difficult issues were tackled in a recent paper [19] in which the authors were able to localize probability measures on infinite-dimensional function spaces by relating them to Young measures as described below.
7.2.1 Correlation Measures
Let \(\mathbf {U} = {\mathbb {R}}^N\) and D k := D ×⋯ × D denote the k-fold cartesian product of D. In [19], the authors defined correlation measures as a collection ν = (ν 1, ν 2, … ) of maps \(\nu ^k : D^k \to {\mathscr P}(\mathbf {U}^k)\) satisfying the following properties:
-
(i)
Weak-∗ measurability: Each map \(\nu ^k : D^k \to {\mathscr P}(U^k)\) is weak-∗ measurable, in the sense that the map \(x \mapsto \left \langle \nu ^k_x,\, f\right \rangle \) from x ∈ D k into \({\mathbb {R}}\) is Borel measurable for all f ∈ C 0(U k) and \(k\in {\mathbb {N}}\). In other words, ν k is a Young measure from D k to U k.
-
(ii)
L p -boundedness: ν is L p-bounded, in the sense that
$$\displaystyle \begin{aligned}\int_{D} \left\langle \nu^1_x,\, |\xi|{}^p\right\rangle\,dx < +\infty.\end{aligned}$$ -
(iii)
Symmetry: If σ is a permutation of {1, …, k} and \(f\in C_0({\mathbb {R}}^k)\) then \(\left \langle \nu ^k_{\sigma (x)},\, f(\sigma (\xi ))\right \rangle = \left \langle \nu ^k_x,\, f(\xi )\right \rangle \) for a.e. x ∈ D k. Here, we denote \(\sigma (x) = \sigma (x_1,x_2,\ldots , x_k) = (x_{\sigma _1},x_{\sigma _2},\ldots ,x_{\sigma _k})\).
-
(iv)
Consistency: If f ∈ C 0(U k) is of the form f(ξ 1, …, ξ k ) = g(ξ 1, …, ξ k−1) for some g ∈ C 0(U k−1), then \(\left \langle \nu ^k_{x_1,\dots ,x_k},\, f\right \rangle = \left \langle \nu ^{k-1}_{x_1,\dots ,x_{k-1}},\, g\right \rangle \) for almost every (x 1, …, x k ) ∈ D k.
-
(v)
Diagonal continuity (DC): If \(B_r(x) := \left \{y\in D\ :\ |x-y|<r\right \}\) then
$$\displaystyle \begin{aligned} \lim_{r\to0}\int_D\frac{1}{|B_r(0)|}\int_{B_r(x)}\left\langle \nu^2_{x,y},\, |\xi_1-\xi_2|{}^p\right\rangle\,dy\,dx = 0. \end{aligned} $$(118)
Each element ν k is called a correlation marginal. The consistency property implies that the kth correlation marginal ν k determines all ν l, l ≤ k. Thus, the family of correlation marginals is a hierarchy of young measures. The equivalence between correlation measures and probability measures on L p is described by the following result, which is [19, Thm. 2.7]:
For every correlation measure ν defined as above, there exists a unique probability measure \(\mu \in \mathscr {P}(L^p(D))\) satisfying
such that, for all \(\ k\in {\mathbb {N}}\) and for every g ∈ L 1(D k : C 0(U k)): there holds
(where u(x) denotes the vector (u(x 1), …, u(x k ))). Conversely, for every probability measure \(\mu \in {\mathscr P}(L^p(D))\) with finite L p bound, there exists a unique correlation measure ν satisfying (120). The relation (120) is also valid for any measurable \(g:D\times \mathbf { U}\to {\mathbb {R}}\) such that |g(x, ξ)|≤ C|ξ|p for a.e. x ∈ D.
Moreover, it was also shown in [19] (Theorem 2.20) that the probability measure μ (equivalently the associated correlation measure ν) was uniquely determined in terms of moments or correlation functions of the correlation measure ν given by
Here, U
⊗k refers to the tensor product space 
(repeated k times), and ξ
1 ⊗⋯ ⊗ ξ
k
is a functional defined by its action on the dual space \(\left (\mathbf {U}^{\otimes k}\right )^* = \mathbf {U}^{\otimes k}\) through
7.2.2 Definition of Statistical Solutions
Once it is established that probability measures on L p are completely characterized by moments (correlation functions) of the associated correlation measure, one can evolve an initial probability measure on L p(D) in time by writing evolution equations for these correlation functions. Following [19], we define statistical solution of (115a) with an initial data \(\bar {\mu }\in \mathscr {P}\big (L^1\big ({\mathbb {R}}^d,{\mathbb {R}}^N\big )\big )\) as a weak*-measurable mapping \(t \mapsto \mu _t\in \mathscr {P}\big (L^1\big ({\mathbb {R}}^d,{\mathbb {R}}^N\big )\big )\) such that the corresponding correlation measures \((\nu ^k_t)_{k\in {\mathbb {N}}}\) satisfy the following equations in the sense of distributions,
Note that the first equation in the hierarchy for k = 1 precisely agrees with the definition of measure-valued solutions (116). Thus, a statistical solution is a measure-valued solution that includes information about the evolution of all possible multi-point correlations in the underlying functions. Hence, statistical solutions are considerably more constrained than measure-valued solutions providing some hope for uniqueness. Moreover, statistical solutions reduce to standard weak solutions as long as the initial data and the resulting statistical solution are atomic i.e., \(\bar {\mu } = \delta _{\bar {u}}, \mu _t = \delta _{u(t)}\) with \(\bar {u},u(t) \in L^p(D)\). On the other hand, a non-atomic initial probability measure \(\bar {\mu }\) can be used to model input uncertainty. Hence, statistical solutions provide a UQ framework [19].
Currently, well-posedness results for statistical solutions are only available for scalar conservation laws. In [19], a concept of entropy statistical solutions was proposed for scalar conservation laws, Definition 4.3 therein. This concept generalizes Kružkhov entropies to probability measures on L 1. Well-posedness of entropy statistical solutions for scalar conservation laws was shown in [19, Thm. 4.7]. These entropy statistical solutions were also shown to satisfy a non-expansive property with respect to the 1-Wasserstein metric on probability measures on L 1. The mathematical analysis of the convergence of the MC-FV algorithms 1, 2, in the sense of [18], for scalar conservation laws is currently in progress. Some (preliminary) findings are as follows: the same Monte Carlo ensemble averaging algorithm 2, proposed in [18], also converges, under additional assumptions, to a statistical solution of the underlying nonlinear, hyperbolic system as will be shown in a forthcoming paper. Thus, statistical solutions may provide a suitable mathematical and numerical solution framework for multi-dimensional systems of conservation laws as well as of computational uncertainty quantification for them.
The algorithms proposed in [17, 18] are Monte Carlo based. A MLMC version of this algorithm was designed and shown to converge to an entropy measure valued solution in a recent paper [45]. Moreover, it was shown in [45] that if the variance of the details, similar to (96), converge at an algebraic rate i.e. if s > 0 in (96), then the MLMC algorithm for approximating entropy measure-valued solutions will be more efficient than the Monte Carlo version. However, such an estimate may not hold as shown in Fig. 4 and the MC and MLMC versions will be comparable (see Fig. 4 bottom left).
Currently, computation of k-point correlation functions within the framework of statistical solutions uses a full tensor format. This can be prohibitively expensive for even moderate k.
The adaptation of the sparse-tensor algorithms from [46] as described in Sect. 4.4 to this framework in order to accelerate the computations of multi-point statistical quantities of interest is currently under development.
References
R. Abgrall, A. Harten, Multiresolution representation in unstructured meshes. SIAM J. Numer. Anal. 35(6), 2128–2146 (electronic) (1998). https://doi.org/10.1137/S0036142997315056
A. Barth, C. Schwab, N. Zollinger, Multi-level Monte Carlo finite element method for elliptic PDEs with stochastic coefficients. Numer. Math. 119(1), 123–161 (2011). https://doi.org/10.1007/s00211-011-0377-0
C. Bierig, A. Chernov, Estimation of arbitrary order central statistical moments by the multilevel Monte Carlo method. Stoch. Partial Differ. Equ. Anal. Comput. 4(1), 3–40 (2016). https://doi.org/10.1007/s40072-015-0063-9
B.L. Bihari, A. Harten, Multiresolution schemes for the numerical solution of 2-D conservation laws. I. SIAM J. Sci. Comput. 18(2), 315–354 (1997). https://doi.org/10.1137/S1064827594278848
H. Bijl, D. Lucor, S. Mishra, C. Schwab, Uncertainty Quantification in Computational Fluid Dynamics. Lecture Notes in Computational Science and Engineering, vol. 92 (Springer, Cham, 2013). https://doi.org/10.1007/978-3-319-00885-1
E. Chiodaroli, C. De Lellis, O. Kreml, Global ill-posedness of the isentropic system of gas dynamics. Commun. Pure Appl. Math. 68, 1157–1190 (2015)
B. Cockburn, C.W. Shu, TVB Runge-Kutta local projection discontinuous Galerkin finite element method for conservation laws. II. General framework. Math. Comput. 52, 411–435 (1989)
B. Cockburn, F. Coquel, P.G. LeFloch, Convergence of the finite volume method for multidimensional conservation laws. SIAM J. Numer. Anal. 32(3), 687–705 (1995). https://doi.org/10.1137/0732032
S. Cox, M. Hutzenthaler, A. Jentzen, J. van Neerven, T. Welti, Convergence in Hölder norms with applications to Monte Carlo methods in infinite dimensions. Technical Report 2016-28, Seminar for Applied Mathematics, ETH Zürich, 2016
G. Da Prato, J. Zabczyk, Stochastic Equations in Infinite Dimensions. Encyclopedia of Mathematics and its Applications, vol. 44 (Cambridge University Press, Cambridge, 1992). https://doi.org/10.1017/CBO9780511666223
C.M. Dafermos, Hyperbolic Conservation Laws in Continuum Physics. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 325, 3rd edn. (Springer, Berlin, 2010). https://doi.org/10.1007/978-3-642-04048-1
T. Daun, S. Heinrich, Complexity of Banach space valued and parametric integration, in Monte Carlo and Quasi-Monte Carlo Methods 2012. Springer Proceedings in Mathematics & Statistics, vol. 65 (Springer, Heidelberg, 2013), pp. 297–316. https://doi.org/10.1007/978-3-642-41095-6_12
T. Daun, S. Heinrich, Complexity of parametric initial value problems in Banach spaces. J. Complexity 30(4), 392–429 (2014). https://doi.org/10.1016/j.jco.2014.01.002
R.J. DiPerna, Measure-valued solutions to conservation laws. Arch. Ration. Mech. Anal. 88, 223–270 (1985)
R. Eymard, T. Gallouët, R. Herbin, Finite volume methods, in Handbook of Numerical Analysis, vol. VII (North-Holland, Amsterdam, 2000), pp. 713–1020
U. Fjordholm, S. Mishra, E. Tadmor, Arbitrarily high-order accurate entropy stable essentially nonoscillatory schemes for systems of conservation laws. SIAM J. Numer. Anal. 50(2), 544–573 (2012). https://doi.org/10.1137/110836961
U.S. Fjordholm, S. Mishra, E. Tadmor, On the computation of measure-valued solutions. Acta Numer. 25, 567–679 (2016). https://doi.org/10.1017/S0962492916000088
U. Fjordholm, R. Kappeli, S. Mishra, E. Tadmor, Construction of approximate entropy measure valued solutions for systems of conservation laws. J. Found. Comput. Math 17(3), 763–827 (2017). https://doi.org/10.1007/s10208-015-9299-z
U.S. Fjordholm, S. Lanthaler, S. Mishra, Statistical solutions of hyperbolic conservation laws I: Foundations. Arch. Ration. Mech. Anal. 226, 809–849 (2017)
C. Foiaş, G. Prodi, Sur les solutions statistiques des équations de Navier-Stokes. Ann. Mat. Pura Appl. (4) 111, 307–330 (1976)
C. Foias, O. Manley, R. Rosa, R. Temam, Navier-Stokes Equations and Turbulence (Cambridge University Press, Cambridge, 2001)
P.K. Friz, B. Gess, Stochastic scalar conservation laws driven by rough paths. Ann. Inst. H. Poincaré Anal. Non Linéaire 33(4), 933–963 (2016). https://doi.org/10.1016/j.anihpc.2015.01.009
F. Fuchs, A. McMurry, S. Mishra, N.H. Risebro, K. Waagan, Approximate Riemann solver based high-order finite volume schemes for the MHD equations in multi-dimensions. Commun. Comput. Phys. 9, 324–362 (2011). https://doi.org/10.4208/cicp.171109.070510a
G. Geraci, P.M. Congedo, R. Abgrall, G. Iaccarino, A novel weakly-intrusive non-linear multiresolution framework for uncertainty quantification in hyperbolic partial differential equations. J. Sci. Comput. 66(1), 358–405 (2016). https://doi.org/10.1007/s10915-015-0026-3
N. Gerhard, S. Müller, Adaptive multiresolution discontinuous Galerkin schemes for conservation laws: multi-dimensional case. Comput. Appl. Math. 35(2), 321–349 (2016). https://doi.org/10.1007/s40314-014-0134-y
B. Gess, B. Perthame, P.E. Souganidis, Semi-discretization for stochastic scalar conservation laws with multiple rough fluxes. SIAM J. Numer. Anal. 54(4), 2187–2209 (2016). https://doi.org/10.1137/15M1053670
M.B. Giles, Multilevel Monte Carlo methods. Acta Numer. 24, 259–328 (2015). https://doi.org/10.1017/S096249291500001X
E. Godlewski, P.A. Raviart, Hyperbolic Systems of Conservation Laws. Mathématiques & Applications (Paris) [Mathematics and Applications], vol. 3/4 (Ellipses, Paris, 1991)
E. Godlewski, P.A. Raviart, Numerical Approximation of Hyperbolic Systems of Conservation Laws. Applied Mathematical Sciences, vol. 118 (Springer, New York, 1996)
S. Gottlieb, C. Shu, E. Tadmor, High order time discretizations with strong stability property. SIAM Rev. 43, 89–112 (2001)
M. Griebel, H. Harbrecht, A note on the construction of L-fold sparse tensor product spaces. Constr. Approx. 38(2), 235–251 (2013). https://doi.org/10.1007/s00365-012-9178-7
H. Harbrecht, M. Peters, M. Siebenmorgen, Combination technique based k-th moment analysis of elliptic problems with random diffusion. J. Comput. Phys. 252, 128–141 (2013). https://doi.org/10.1016/j.jcp.2013.06.013
A. Harten, B. Engquist, S. Osher, S.R. Chakravarty, Uniformly high order accurate essentially non-oscillatory schemes. J. Comput. Phys. 71, 231–303 (1987)
A. Hiltebrand, S. Mishra, Entropy stable shock capturing streamline diffusion space-time discontinuous Galerkin (DG) methods for systems of conservation laws. Numer. Math. 126(1), 103–151 (2014)
H. Holden, N.H. Risebro, Front Tracking for Hyperbolic Conservation Laws. Applied Mathematical Sciences, vol. 152 (Springer, New York, 2011). https://doi.org/10.1007/978-3-642-23911-3. First softcover corrected printing of the 2002 original
U. Koley, N.H. Risebro, C. Schwab, F. Weber, A multilevel monte carlo finite difference method for random scalar degenerate convection diffusion equations. J. Hyperbolic Diff. Equ. 14(3), 415–454 (2017)
D. Kröner, Numerical Schemes for Conservation Laws. Wiley-Teubner Series Advances in Numerical Mathematics (Wiley, Chichester, 1997)
M. Ledoux, M. Talagrand, Probability in Banach Spaces. Classics in Mathematics (Springer, Berlin, 2011). Isoperimetry and processes, Reprint of the 1991 edition
P.G. LeFloch, Hyperbolic Systems of Conservation Laws. Lectures in Mathematics ETH Zürich (Birkhäuser, Basel, 2002). https://doi.org/10.1007/978-3-0348-8150-0. The theory of classical and nonclassical shock waves
F. Leonardi, A projection method for the computation of admissible measure valued solutions of the incompressible Euler equations. Technical Report 2017-06, Seminar for Applied Mathematics, ETH Zürich, 2017
F. Leonardi, S. Mishra, C. Schwab, Numerical approximation of statistical solutions of planar, incompressible flows. Math. Models Methods Appl. Sci. 26(13), 2471–2524 (2016). https://doi.org/10.1142/S0218202516500597
R.J. LeVeque, Finite Volume Methods for Hyperbolic Problems. Cambridge Texts in Applied Mathematics (Cambridge University Press, Cambridge, 2002). https://doi.org/10.1017/CBO9780511791253
P.L. Lions, B. Perthame, P.E. Souganidis, Scalar conservation laws with rough (stochastic) fluxes. Stoch. Partial Differ. Equ. Anal. Comput. 1(4), 664–686 (2013)
P.L. Lions, B. Perthame, P.E. Souganidis, Scalar conservation laws with rough (stochastic) fluxes: the spatially dependent case. Stoch. Partial Differ. Equ. Anal. Comput. 2(4), 517–538 (2014). https://doi.org/10.1007/s40072-014-0038-2
K. Lye, Multilevel Monte-Carlo for measure valued solutions. Technical Report 2016-51 (revised), Seminar for Applied Mathematics, ETH Zürich, 2016
S. Mishra, C. Schwab, Sparse tensor multi-level Monte Carlo finite volume Methods for hyperbolic conservation laws with random initial data. Math. Comput. 81, 1979–2018 (2012). https://doi.org/10.1090/S0025-5718-2012-02574-9
S. Mishra, C. Schwab, J. Sukys, Multi-level monte carlo finite volume methods for nonlinear systems of conservation laws in multi-dimensions. J. Comput. Phys. 231(8), 3365–3388 (2012). https://doi.org/10.1016/j.jcp.2012.01.011
S. Mishra, N.H. Risebro, C. Schwab, S. Tokareva, Numerical solution of scalar conservation laws with random flux functions. SIAM/ASA J. Uncertain. Quantif. 4(1), 552–591 (2016). https://doi.org/10.1137/120896967
S. Mishra, C. Schwab, J. Šukys, Multi-level Monte Carlo finite volume methods for uncertainty quantification of acoustic wave propagation in random heterogeneous layered medium. J. Comput. Phys. 312, 192–217 (2016). https://doi.org/10.1016/j.jcp.2016.02.014.
S. Müller, Multiresolution schemes for conservation laws, in Multiscale, Nonlinear and Adaptive Approximation (Springer, Berlin, 2009), pp. 379–408. https://doi.org/10.1007/978-3-642-03413-8_11
N.H. Risebro, C. Schwab, F. Weber, Multilevel monte carlo front-tracking for random scalar conservation laws. BIT Numer. Math. (2016). https://doi.org/10.1007/s10543-015-0550-4
G. Schmidlin, C. Schwab, Wavelet Galerkin BEM on unstructured meshes by aggregation, in Multiscale and Multiresolution Methods. Lecture Notes in Computational Science and Engineering, vol. 20 (Springer, Berlin, 2002), pp. 359–378 https://doi.org/10.1007/978-3-642-56205-1_12
C. Schwab, C.J. Gittelson, Sparse tensor discretizations of high-dimensional parametric and stochastic PDEs. Acta Numer. 20, 291–467 (2011). https://doi.org/10.1017/S0962492911000055.
C. Schwab, S. Tokareva, High order approximation of probabilistic shock profiles in hyperbolic conservation laws with uncertain initial data. ESAIM: Math. Model. Numer. Anal. 47(3), 807–835 (2013). https://doi.org/10.1051/m2an/2012060
C.W. Shu, S. Osher, Efficient implementation of essentially non-oscillatory schemes - II. J. Comput. Phys. 83(1), 32–78 (1989)
J. Smoller, Shock Waves and Reaction-Diffusion Equations. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 258, 2nd edn. (Springer, New York, 1994)
J. Sukys, Robust multi-level monte carlo finite volume methods for systems of conservation laws with random input data. Ph.D. thesis, ETH Zürich, 2014
R.A. Todor, A new approach to energy-based sparse finite-element spaces. IMA J. Numer. Anal. 29(1), 72–85 (2009). https://doi.org/10.1093/imanum/drm041
J. Tryoen, O. Le Maître, M. Ndjinga, A. Ern, Intrusive Galerkin methods with upwinding for uncertain nonlinear hyperbolic systems. J. Comput. Phys. 229(18), 6485–6511 (2010). https://doi.org/10.1016/j.jcp.2010.05.007.
J. van Neerven, Stochastic evolution equations. Lecture Notes, ISEM (2007/8)
M.I. Višik, A.V. Fursikov, Solutions statistiques homogènes des systèmes differentiels paraboliques et du système de Navier-Stokes. Ann. Scuola Norm. Sup. Pisa Cl. Sci. (4) 4(3), 531–576 (1977)
T. von Petersdorff, C. Schwab, Sparse finite element methods for operator equations with stochastic data. Appl. Math. 51(2), 145–180 (2006). https://doi.org/10.1007/s10492-006-0010-1
J. Wehr, J. Xin, Front speed in the Burgers equation with a random flux. J. Stat. Phys. 88(3–4), 843–871 (1997). https://doi.org/10.1023/B:JOSS.0000015175.70862.77
Acknowledgements
The work of CS was supported in part by ERC grant no. 247277. SM acknowledges partial support from ERC STG NN. 306279 SPARCCLE. CS and SM acknowledge also partial support from ETH grant no. CH1-03 10-1.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG, part of Springer Nature
About this chapter
Cite this chapter
Mishra, S., Schwab, C. (2017). Monte-Carlo Finite-Volume Methods in Uncertainty Quantification for Hyperbolic Conservation Laws. In: Jin, S., Pareschi, L. (eds) Uncertainty Quantification for Hyperbolic and Kinetic Equations. SEMA SIMAI Springer Series, vol 14. Springer, Cham. https://doi.org/10.1007/978-3-319-67110-9_7
Download citation
DOI: https://doi.org/10.1007/978-3-319-67110-9_7
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-67109-3
Online ISBN: 978-3-319-67110-9
eBook Packages: Mathematics and StatisticsMathematics and Statistics (R0)