Entropy–Based Methods for Uncertainty Quantification of Hyperbolic Conservation Laws

Abstract

Using standard intrusive techniques when solving hyperbolic conservation laws with uncertainties can lead to oscillatory solutions as well as non-hyperbolic moment systems. Entropy-based Stochastic Galerkin methods, on the other hand, guarantee hyperbolicity and entropy decay. A key challenge facing these methods is computational cost, since they require repeatedly solving a non-linear optimization problem. Furthermore, the spatial and temporal discretization needs to preserve realizability, meaning that the existence of a unique solution to the optimization problem must be ensured. We review strategies to guarantee realizability, which use a special choice of the numerical flux while considering errors from the optimization solve. Most importantly, we indicate how intrusive entropy-based closures can be made competitive. We show several numerical test cases and discuss the advantages and disadvantages of several uncertainty propagation methods.

1 Introduction

Hyperbolic equations play an important role in various research as well as industrial areas. The most common equations of this kind model the behavior of liquids, gases and plasmas and are thus widely used in the automotive and aerospace industry. Because of this popularity, many highly efficient and robust implementations for these models are available. The respective codes have shown to, for example, simulate the airflow around an airfoil very precisely, but only if the provided input data is identical or at least extremely close to the experimental setup. Any arising uncertainties in the input parameters, originating from e.g. measurement tolerances, imperfect information or modeling assumptions cannot be represented and thus lead to differences in the results of experiments and simulations. Therefore, propagating these uncertainties through complex partial differential equations has become an important topic in the last decades.

We consider a parameterized system of hyperbolic equations of the form

$$\begin{aligned} \partial _t \boldsymbol{u}(t,\boldsymbol{x},\boldsymbol{\xi }) + \nabla \cdot \boldsymbol{f}(\boldsymbol{u}(t,\boldsymbol{x},\boldsymbol{\xi }))= & {} \boldsymbol{0} \text { in } D\;,\end{aligned}$$

(1a)

$$\begin{aligned} \boldsymbol{u}(t=0,\boldsymbol{x}, \boldsymbol{\xi })= & {} \boldsymbol{u}_{\text {IC}}(\boldsymbol{x},\boldsymbol{\xi }) \end{aligned}$$

(1b)

with state variable $\boldsymbol{u} \in \mathcal {D}\subset \mathbb {R}^{m}$ depending on time $t \in \mathbb {R^+}$, spatial position $\boldsymbol{x} \in D \subset \mathbb {R}^d$ and uncertain parameter $\boldsymbol{\xi }\in \Theta \subseteq \mathbb {R}^p$. The physical flux is given by $\boldsymbol{f}:\mathcal {D} \rightarrow \mathbb {R}^{d \times m}$. Note, that for ease of notation, the uncertainties $\boldsymbol{\xi }$ here only enter through the initial condition, i.e. only the initial data is subject to randomness. Boundary conditions are omitted for now as they are specific to the studied problem and will be supplied for the individual test cases in the later sections. We assume that all random parameters are independent with a joint probability density function $f_{\Xi } = \prod ^{p}_{i=1} f_{\Xi ,i}(\xi _i)$.

As the solution of (1a) is now subject to randomness, one is often interested in determining the statistical moments of the solution, where the first and second order moments, i.e. the mean and variance of $\boldsymbol{u}$, given by

$$\begin{aligned} \text {E}[\boldsymbol{u}] = \langle \boldsymbol{u} \rangle ,\qquad \text {Var}[\boldsymbol{u}] = \langle \left( \boldsymbol{u}-\text {E}[\boldsymbol{u}]\right) ^2\rangle \end{aligned}$$

are usually most interesting. We define the bracket operator above as

$$\begin{aligned} \langle \cdot \rangle :=\int _\Theta \cdot f_{\Xi }(\boldsymbol{\xi })\;d\xi _1\dots d\xi _p. \end{aligned}$$

Generally, the methods of Uncertainty Quantification (UQ) can be divided into two groups, intrusive and non-intrusive, meaning the methods either require an intrusive change of an existing deterministic solver, or the existing code can be repurposed in a black-box manner. Several textbooks on UQ have appeared in recent years [5, 10, 27, 28, 35, 40], and we refer the reader to these textbooks for a general overview and references to the original works. In this paper, we nevertheless want to shed some light on how these methods can be expected to perform when applied to hyperbolic conservation laws. We will also make some general statements that we believe are not well-known in some part of the literature. As it has been shown [33], the stochastic Galerkin method cannot be applied directly to conservation laws because it is prone to yield oscillatory solutions that might result in the loss of hyperbolicity and e.g. negative densities. We then discuss in detail the Intrusive Polynomial Moment (IPM) method [33], which can be seen as a generalization to the stochastic Galerkin method. This method is based on entropy minimization, and choosing a suitable entropy guarantees hyperbolicity. On the other hand, the method comes at the cost of solving an optimization problem at every point in time for every spatial cell.

The IPM method has been inspired by entropy-based closures in kinetic theory. In fact, the moment closure problem for a kinetic equation in velocity space is very similar to treating uncertain parameters [20]. In the case of kinetic equations, the techniques to put entropy-based closures into practice have been refined in a series of papers [1,2,3, 9, 14, 29], and the application to UQ draws from this experience. In this paper, we discuss realizability-preserving spatial discretizations, and acceleration techniques to solve the IPM system more efficiently. This review is based on the papers [19, 20, 23].

2 Why Galerkin-Type Intrusive Methods?

For the following discussion, we assume that we want to approximate the expected value

$$\begin{aligned} \text {E}[\boldsymbol{u}] = \langle \boldsymbol{u} \rangle = \int _\Theta \boldsymbol{u} f_{\Xi }\;d\xi _1\dots d\xi _p \end{aligned}$$

of the solution $\boldsymbol{u}$ at a given time t as a function of $\boldsymbol{x}$. Since the expected value is an integral of the solution against the probability density function, all non-intrusive UQ methods can be understood and analyzed as numerical quadrature rules

$$\begin{aligned} \text {E}[\boldsymbol{u}](t,x) \approx \sum _{k=1}^N w^k \boldsymbol{u}(t,\boldsymbol{x},\boldsymbol{\xi ^k})\;. \end{aligned}$$

• Monte-Carlo (MC) methods sample $\boldsymbol{\xi ^k}$ from the probability density function $f_{\Xi }$ and take $w^k = \frac{1}{N}$.

• Number-theoretic/Quasi-Monte Carlo (QMC) methods for uniformly distributed random variables use a low-discrepancy sequence for $\boldsymbol{\xi ^k}$ and again $w^k = \frac{1}{N}$.

• Tensorized quadrature rules take one-dimensional (e.g. Gaussian) quadrature rules for each random input $\xi _i$. The grid for the $\boldsymbol{\xi ^k}$ is defined as a Cartesian product of the one-dimensional grids and the weights are products of the one-dimensional weights.

• Sparse grid quadrature rules use nodes $\boldsymbol{\xi ^k}$ on a (e.g. Smolyak) sparse grid and weights that come from nested quadrature rules (e.g. Clenshaw-Curtis).

In the UQ literature, these methods are discussed based on their error formulas, and the so-called curse of dimensionality is often mentioned. If $\boldsymbol{u}$ denotes the true expected value and $\boldsymbol{u}_N$ its approximation with N nodes/samples, then the methods behave in the following way:

• The MC error is determined by the root mean square error $E[(\boldsymbol{u}-\boldsymbol{u}_N)^2]^{1/2} = V_{MC}(\boldsymbol{u}) N^{-1/2}$.

• Multi-level Monte Carlo (MLMC) methods use control variates to make the constant $V(\boldsymbol{u})$ smaller [11].

• The QMC error typically behaves like $|\boldsymbol{u}-\boldsymbol{u}_N|\le V_{QMC}(\boldsymbol{u}) (\log N)^p N^{-1}$ [6].

• The tensorized grid error has the form $|\boldsymbol{u}-\boldsymbol{u}_N|\le V_{\text {tens}}(\boldsymbol{u}) N^{-\alpha /p}$.

• The sparse grid quadrature error behaves like $|\boldsymbol{u}-\boldsymbol{u}_N|\le V_{\text {sparse}}(\boldsymbol{u}) (\log N)^p N^{-\beta }$.

In the latter two cases, $\alpha$ and $\beta$ are related to the differentiability of $\boldsymbol{u}$ with respect to $\boldsymbol{\xi }$. All error constants V depend on $\boldsymbol{u}$ and certain of its derivatives. For instance, in the case of sparse grids, $\boldsymbol{u}$ has to be in a certain Sobolev space with mixed higher-order derivatives. For an overview and a critical discussion of the assumptions on the solution we refer the reader to the excellent paper [38]. In the mathematical UQ literature, the curse of dimensionality is usually defined as an effective decay of the convergence rate when it is measured in the total number of nodes N and when the dimension p is increased. This is clearly the case for tensorized grids. But one should also note that for both QMC and sparse grid quadrature the decaying term dominates the $\log$ term only if $N\gg 2^p$ ($N\gg 2^{p/\beta }$ respectively). These methods therefore only mitigate the curse. Finally, one often finds the statement that MC methods do not suffer from the curse, because the convergence rate is independent of the dimension p. However, MC methods might be impractical in high dimensions. This can be seen from the simple example (that every reader can easily try) of approximating the volume of the unit sphere in p dimensions: Draw a uniform sample in $[-1,1]^p$ and determine if the sampled node is inside the unit sphere. Then the ratio of the points inside the sphere to the total number of samples converges to the volume divided by $2^p$. For $p=20$, MC with 100 million samples will not produce any significant digit. The reason is that the volume of the sphere becomes so small that it becomes almost impossible to draw a sample within the sphere. In other words, the error constant increases rapidly with dimension p. It should be noted, however, that all of these methods are embarrassingly parallel because uncoupled problems need to be solved.

Intrusive methods on the other hand do not rely on any form of quadrature, but rather derive a system of equations that describes the time evolution of the moments directly. The resulting system can then be solved with classical numerical methods for deterministic equations. In contrast to non-intrusive methods this does not decouple the problem. In the stochastic Galerkin (SG) method, the solution $\boldsymbol{u}$ is expanded in a series of polynomial basis functions $\varphi _{i}:\Theta \rightarrow \mathbb {R}$, such that for the multi-index $i = (i_1,\cdots ,i_p)$ we have $|i| := \sum _{k = 1}^p |i_k| \le N$. The usual choice for these functions $\varphi _i$ are orthonormal polynomials with respect to the probability distribution function, i.e. $\langle \varphi _i \varphi _j \rangle =\prod _{n=1}^p\delta _{i_nj_n}$. This yields the so called generalized polynomial chaos (gPC) expansion

$$\begin{aligned} \mathcal {U}(\boldsymbol{\hat{u}};\boldsymbol{\xi }):= \sum _{|i|\le N} \boldsymbol{\hat{u}}_i\varphi _i(\boldsymbol{\xi }) = \boldsymbol{\hat{u}}^T\boldsymbol{\varphi }(\boldsymbol{\xi })\;. \end{aligned}$$

(2)

The unknown, but deterministic expansion coefficients $\boldsymbol{\hat{u}}_i\in \mathbb {R}^m$ are called moments. For a more compact notation, we collect these moments in the moment matrix $\boldsymbol{\hat{u}}$. This matrix holds all moments for which $|i|\le N$ holds. Therefore, $\boldsymbol{\hat{u}}$ is defined as $\boldsymbol{\hat{u}}:=(\boldsymbol{\hat{u}}_i)_{|i|\le N}\in \mathbb {R}^{M\times m}$ with corresponding basis functions $\boldsymbol{\varphi }:=(\varphi _i)_{|i|\le N}\in \mathbb {R}^{M}$. The total number of basis functions for which $|i|\le N$ holds is

$$\begin{aligned} M:=\begin{pmatrix} N+p \\ p \end{pmatrix}\;. \end{aligned}$$

When the gPC approximation (2) is known, statistical quantities of interest can be computed as

$$\begin{aligned} \text {E}[\mathcal {U}(\boldsymbol{\hat{u}})] = \boldsymbol{\hat{u}}_0\;,\quad \text {Var}[\mathcal {U}(\boldsymbol{\hat{u}})] = \text {E}[\mathcal {U}(\boldsymbol{\hat{u}})^2] - \text {E}[\mathcal {U}(\boldsymbol{\hat{u}})]^2 = \left( \sum _{i = 1}^N \hat{u}_{\ell i}^2\right) _{\ell = 1,\cdots ,m}\;. \end{aligned}$$

The SG moment system is obtained by plugging the gPC ansatz (2) into the stochastic problem (1a) and projecting the resulting residual to zero (Galerkin projection), which yields the system

$$\begin{aligned} \partial _t \boldsymbol{\hat{u}}_i(t,\boldsymbol{x}) + \nabla \cdot \langle \boldsymbol{f}(\mathcal {U}(\boldsymbol{\hat{u}})) \varphi _i\rangle= & {} \boldsymbol{0}\;, \end{aligned}$$

(3a)

$$\begin{aligned} \boldsymbol{\hat{u}}_i(t=0,\boldsymbol{x})= & {} \langle \boldsymbol{u}_{\text {IC}}(\boldsymbol{x})\varphi _i\rangle \;. \end{aligned}$$

(3b)

As mentioned previously, the main caveat of the method is that the moment system is not necessarily hyperbolic and thus not applicable to every problem. We will investigate this thoroughly in the following sections, but at this point we want to discuss why one should be interested in an intrusive method like SG at all. Putting SG into practice requires working with the model and new code. Additionally, the trivial parallelism of non-intrusive methods is lost. A statement one often finds in the UQ literature is that one should use SG because it has spectral convergence. This means that the convergence rate of the method only depends on the smoothness of the function. Moreover, if this smoothness is large or even infinite (i.e. the solution possesses derivatives of orders up to infinity) then the curse of dimensionality can be overcome. However, both Gauss and Clenshaw-Curtis quadrature also show spectral convergence [39], so if a function is smooth enough those methods can be used as well.

On the plus side, because sparse grids rely on nested quadrature rules, and similar to modal versus nodal DG methods, SG reaches the same formal accuracy with fewer unknowns. Furthermore, in many cases the expected value of a solution of a hyperbolic system is more smooth and does not have shocks (examples can be found in Sect. 6). Although this is not true in general [37], one often does not have to use a high-resolution shock-capturing scheme. Two further advantages will be utilized in this paper: Whereas collocation methods use a global grid in the uncertain parameters, for intrusive methods one can enrich the discretization of the parameter space adaptively. Furthermore, especially for the IPM method one can iterate faster into steady state. Given these potential advantages we argue that although intrusive methods have shortcomings it is worthwhile to study them, especially in the context of hyperbolic conservation laws.

3 Hyperbolic Conservation Laws and the IPM Method

After introducing hyperbolic conservation laws and the concept of entropy, this section is focused on the derivation of the IPM method.

3.1 Hyperbolic Conservation Laws and Entropy Variables

Our numerical discretization of the random space should preserve certain properties of hyperbolic equations. Although they are well-known, we briefly summarize them in the following to fix notation. Ignoring uncertainties for the time being, to characterize hyperbolicity we put the conservative form (1a) into its quasi-conservative form. Defining the flux Jacobians $\boldsymbol{A}_j := \nabla _{\boldsymbol{u}} \boldsymbol{f}_j\in \mathbb {R}^{m\times m}$, the system (1a) can be rewritten as

$$\begin{aligned} \partial _t \boldsymbol{u} + \sum _{j=1}^d \boldsymbol{A}_j(\boldsymbol{u}) \partial _{x_j} \boldsymbol{u} = \boldsymbol{0}\;. \end{aligned}$$

(4)

Denoting the flux Jacobian into direction $\boldsymbol{w}\in \mathbb {R}^d$ by

$$\begin{aligned} \boldsymbol{A}(\boldsymbol{u},\boldsymbol{w}) := \sum _{j=1}^d \boldsymbol{A}_j w_j\;, \end{aligned}$$

we call a system hyperbolic, if the flux Jacobian $\boldsymbol{A}(\boldsymbol{u}, \boldsymbol{w})$ has only real eigenvalues $\lambda _k(\boldsymbol{u}, \boldsymbol{w})$ for $k=1,\cdots ,m$ with a complete family of eigenvectors $\boldsymbol{r}_k(\boldsymbol{u}, \boldsymbol{w})$ for all states $\boldsymbol{u}\in \mathcal {D}$ and every direction $\boldsymbol{w}\in \mathbb {R}^d$ with $\Vert \boldsymbol{w} \Vert = 1$. Note that for one spatial dimension, i.e. $d=1$, the direction is $w=1$ and therefore hyperbolicity holds if the flux Jacobian $\nabla _{\boldsymbol{u}} \boldsymbol{f}$ is diagonalizable with real eigenvalues.

Hyperbolic problems tend to form shocks, in which case the original system can no longer be solved. Therefore, the concept of weak solutions has been introduced, which tests the original problem against smooth basis functions with compact support and then moves derivatives from the solution onto these basis functions [24, Chapter 3.4]. Unfortunately, weak solutions are not unique and can show non-physical behavior. Hence, one is left with having to pick physical meaningful solutions from possible weak solution candidates. This motivates a further concept, called the entropy solution [24, Chapter 3.8.1]. Note that in the case of scalar equations, the entropy solution is actually unique under certain smallness assumptions [16, Chapter 2.4]. Let us first introduce the entropy:

Definition 1

Let $\mathcal {D}$ be convex. Then a convex function $s:\mathcal {D}\rightarrow \mathbb {R}$ is called an entropy for the conservation Eqs. (1a) if there exist d functions $\tilde{F}_j:\mathcal {D}\rightarrow \mathbb {R}$, called entropy fluxes, which fulfill the integrability condition

$$\begin{aligned} \nabla _{\boldsymbol{u}} s(\boldsymbol{u})\nabla _{\boldsymbol{u}}\boldsymbol{f}_j (\boldsymbol{u}) = \nabla _{\boldsymbol{u}} \tilde{F}_j(\boldsymbol{u})\;, \quad j = 1,\cdots ,d\;. \end{aligned}$$

(5)

For classical solutions, the integrability condition ensures conservation of entropy: By multiplying $\nabla _{\boldsymbol{u}} s(\boldsymbol{u})$ from the left with the original Eq. (1a), we get with the integrability condition (5) as

$$\begin{aligned} \partial _t s(\boldsymbol{u}) + \sum _{j=0}^d \partial _{x_j} \tilde{F}_j(\boldsymbol{u}) = 0\;. \end{aligned}$$

(6)

Since (6) is again in conservation form, the entropy is conserved at smooth solutions and the functions $\tilde{F}_j$ are the flux functions of the entropy balance law (6).

If $\boldsymbol{u}$ is a weak solution, which fulfills

$$\begin{aligned} \partial _t s(\boldsymbol{u}) + \sum _{j=0}^d \partial _{x_j} \tilde{F}_j(\boldsymbol{u})\le 0 \end{aligned}$$

(7)

in a weak sense for all admissible entropies s, then $\boldsymbol{u}$ is called an entropy solution. Note that opposed to the entropy used in thermodynamics, the mathematical entropy s is dissipated in time: By integrating (7) over the spatial domain, while assuming that the entropy fluxes are zero at the boundary, we obtain

$$\begin{aligned} \frac{d}{dt} \int _{D} s(\boldsymbol{u}) \,d\boldsymbol{x} \le 0\;. \end{aligned}$$

(8)

The notion of entropy is closely related to hyperbolicity, which can be shown with the help of the entropy variables

$$\begin{aligned} \boldsymbol{v} = \nabla _{\boldsymbol{u}} s(\boldsymbol{u})^T\in \mathbb {R}^{m}\;. \end{aligned}$$

(9)

If s is strictly convex, the mapping $\boldsymbol{v}(\boldsymbol{u})$ is one-to-one and the solution $\boldsymbol{u}$ can be represented in terms of entropy variables as $\boldsymbol{u} : \mathbb {R}^m \rightarrow \mathbb {R}^m$ with $\boldsymbol{u}(\boldsymbol{v}) = \left( \nabla _{\boldsymbol{u}} s \right) ^{-1}(\boldsymbol{v})$.¹ A change from the conserved quantities $\boldsymbol{u}$ to their corresponding entropy variables can be performed to put (1a) in its symmetric form

$$\begin{aligned} \partial _t \boldsymbol{u} (\boldsymbol{v}) + \sum _{j=1}^d \partial _{x_j}\boldsymbol{g}_j (\boldsymbol{v}) = \boldsymbol{0}\;, \end{aligned}$$

(10)

where the flux with respect to the entropy variables has been denoted by $\boldsymbol{g}_j$, i.e.

$$\begin{aligned} \boldsymbol{g}_j(\boldsymbol{v}) := \boldsymbol{f}_j(\boldsymbol{u}(\boldsymbol{v})) \qquad \text {with } j = 1,\cdots ,d\;. \end{aligned}$$

(11)

Our goal is to check hyperbolicity, i.e. (10) needs to be brought into its quasi-conservative form (4). Applying the chain rule results in

$$\begin{aligned} \boldsymbol{H}(\boldsymbol{v}) \partial _t \boldsymbol{v} + \sum _{j=1}^d \boldsymbol{B}_j(\boldsymbol{v}) \partial _{x_j}\boldsymbol{v} = \boldsymbol{0}\;, \end{aligned}$$

(12)

with

$$\begin{aligned} \boldsymbol{H}(\boldsymbol{v})=\nabla _{\boldsymbol{v}} \boldsymbol{u}(\boldsymbol{v})\qquad \text { and } \qquad \boldsymbol{B}_j(\boldsymbol{v}) = \nabla _{\boldsymbol{v}}\boldsymbol{g}_j (\boldsymbol{v})\;. \end{aligned}$$

(13)

Note that $\boldsymbol{H}(\boldsymbol{v}) = \left( \nabla _{\boldsymbol{u}}^2 s(\boldsymbol{u})\right) ^{-1}$, which can be checked by differentiating $\nabla _{\boldsymbol{u}}s(\boldsymbol{u}(\boldsymbol{v})) = \boldsymbol{v}$ with respect to $\boldsymbol{v}$. Therefore, $\boldsymbol{H}(\boldsymbol{v})$ is symmetric positive definite and can therefore be rewritten as $\boldsymbol{Q}\boldsymbol{\Lambda }\boldsymbol{Q}^T$, where $\boldsymbol{Q}\in \mathbb {R}^{m \times m}$ is orthonormal and $\boldsymbol{\Lambda }\in \mathbb {R}^{m \times m}$ is a diagonal matrix with positive entries. Consequently, the regular, symmetric matrix $\boldsymbol{H}^{1/2} := \boldsymbol{Q} \boldsymbol{\Lambda }^{1/2} \boldsymbol{Q}^T$ exists. Multiplying (12) with $\boldsymbol{H}^{-1} = \boldsymbol{H}^{-1/2}\boldsymbol{H}^{-1/2}$ from the left results in the system

$$\begin{aligned} \partial _t \boldsymbol{v} + \sum _{j=1}^d\boldsymbol{H}^{-1/2}\boldsymbol{H}^{-1/2}\nabla _{\boldsymbol{v}}\boldsymbol{g}_j (\boldsymbol{v})\boldsymbol{H}^{-1/2}\boldsymbol{H}^{1/2} \partial _{x_j}\boldsymbol{v} = \boldsymbol{0}\;. \end{aligned}$$

(14)

It remains to check under which conditions the flux Jacobian of this system is diagonalizable with real eigenvalues. Since $\boldsymbol{H}^{-1/2}$ is symmetric, symmetry of $\boldsymbol{B}_j$ suffices to show symmetry of $\boldsymbol{H}^{-1/2}\nabla _{\boldsymbol{v}}\boldsymbol{g}_j (\boldsymbol{v})\boldsymbol{H}^{-1/2}$. Multiplying this matrix with $\boldsymbol{H}^{-1/2}$ from the left and $\boldsymbol{H}^{1/2}$ from the right is a similarity transformation and therefore does not change eigenvalues. Hence when $\boldsymbol{B}_j$ is symmetric, the system (14) is diagonalizable with real eigenvalues and therefore hyperbolic. This can be ensured via the concept of entropy.

Theorem 1

The matrices $\boldsymbol{B}_j$ are symmetric iff the integrability condition (5) holds.

Proof

See e.g. [36].   $\square$

In the case of scalar equations, all convex functions can be used as entropies. In particular, a family of entropies, which is also called the Kružkov entropy [18], given by

$$\begin{aligned} s(u) = \vert u - k \vert \qquad \text { for all } k \in \mathbb {R} \end{aligned}$$

fulfills the integrability condition for the entropy flux

$$\begin{aligned} \tilde{F}_j(u) = \text {sgn}(u-k)(f_j(u)-f_j(k))\;. \end{aligned}$$

This family of entropies can be employed to derive several solution properties for scalar equations. One of these properties is the maximum–principle

$$\begin{aligned} \Vert u(t,\cdot )\Vert _{L^{\infty }(D)} \le \Vert u_{\text {IC}} \Vert _{L^{\infty }(D)}\;, \end{aligned}$$

(15)

which guarantees bounds on the solution imposed by its initial condition.

3.2 The Intrusive Polynomial Moment Method

Let us now consider a system of hyperbolic conservation laws of the form (1a) and move back to the discretization of the random domain. As discussed earlier, the polynomial ansatz of stochastic-Galerkin does not necessarily preserve hyperbolicity. A generalization of stochastic-Galerkin, which ensures hyperbolicity is the Intrusive Polynomial Moment (IPM) method [33], which in the field of kinetic theory is known as an entropy closure, see e.g. [25]. Instead of expanding the conserved variables $\boldsymbol{u}$ with polynomials as done by SG, the IPM method performs such an expansion on the entropy variables (9). Hence, substituting the entropy variables $\boldsymbol{v} = \nabla _{\boldsymbol{u}} s(\boldsymbol{u})^T$ into (1a) yields

$$\begin{aligned} \partial _t \boldsymbol{u}(\boldsymbol{v}(t,\boldsymbol{x},\boldsymbol{\xi })) + \nabla \cdot \boldsymbol{f}(\boldsymbol{u}(\boldsymbol{v}(t,\boldsymbol{x},\boldsymbol{\xi }))) = \boldsymbol{0}\;, \end{aligned}$$

(16)

where again $\boldsymbol{u} : \mathbb {R}^m \rightarrow \mathbb {R}^m$ with $\boldsymbol{u}(\boldsymbol{v}) = \nabla _{\boldsymbol{u}}s(\boldsymbol{u})$. Now, a finite dimensional representation of the entropy variables is obtained by an expansion in terms of gPC polynomials, i.e.

$$\begin{aligned} \boldsymbol{v}(t,\boldsymbol{x},\boldsymbol{\xi }) \approx \boldsymbol{v}_N(t,\boldsymbol{x},\boldsymbol{\xi }) := \sum _{|i|\le N}\boldsymbol{\hat{v}}_i(t,\boldsymbol{x}) \varphi _i(\boldsymbol{\xi }) = \boldsymbol{\hat{v}}(t,\boldsymbol{x})^T\boldsymbol{\varphi }(\boldsymbol{\xi })\;, \end{aligned}$$

(17)

where the entropic expansion coefficients (also called dual variables) $\boldsymbol{\hat{v}}_i \in \mathbb {R}^{m}$ are collected in the matrix $\boldsymbol{\hat{v}}:=(\boldsymbol{\hat{v}}_i)_{i\le |N|}\in \mathbb {R}^{M\times m}$. Replacing the exact entropy variables inside the original problem (16) by this expansion, we obtain

$$\begin{aligned} \partial _t\boldsymbol{u}\left( \boldsymbol{\hat{v}}(t,\boldsymbol{x})^T\boldsymbol{\varphi }(\boldsymbol{\xi })\right) + \nabla \cdot \boldsymbol{f}\left( \boldsymbol{u}\left( \boldsymbol{\hat{v}}(t,\boldsymbol{x})^T\boldsymbol{\varphi }(\boldsymbol{\xi })\right) \right) = \boldsymbol{\tilde{r}}(t,\boldsymbol{x},\boldsymbol{\xi })\;. \end{aligned}$$

(18)

Similar to stochastic-Galerkin, the residual $\boldsymbol{\tilde{r}}$ is again projected to zero, yielding

$$\begin{aligned} \partial _t\left\langle \boldsymbol{u}\left( \boldsymbol{\hat{v}}(t,\boldsymbol{x})^T\boldsymbol{\varphi }\right) \varphi _i\right\rangle + \nabla \cdot \left\langle \boldsymbol{f}\left( \boldsymbol{u}\left( \boldsymbol{\hat{v}}(t,\boldsymbol{x})^T\boldsymbol{\varphi }\right) \right) \varphi _i\right\rangle = \boldsymbol{0} \end{aligned}$$

(19)

for $\vert i\vert \le N$. The moments belonging to the dual variables $\boldsymbol{\hat{v}}$ are now given by

$$\begin{aligned} \boldsymbol{\hat{u}}_i(\boldsymbol{\hat{v}}) = \left\langle \boldsymbol{u}\left( \boldsymbol{\hat{v}}^T\boldsymbol{\varphi }\right) \varphi _i\right\rangle \qquad \text { for } |i| \le N\;. \end{aligned}$$

(20)

This mapping, i.e. $\boldsymbol{\hat{u}} : \mathbb {R}^{M\times m}\rightarrow \mathcal {R} \subset \mathbb {R}^{M\times m}$ is one-to-one, meaning that similar to $\boldsymbol{v}(\boldsymbol{u})$, we can define a function $\boldsymbol{\hat{v}}(\boldsymbol{\hat{u}})$ with $\boldsymbol{\hat{v}} : \mathcal {R}\rightarrow \mathbb {R}^{M\times m}$. Making use of this mapping as well as the definition of the moments in (19) yields the IPM system

$$\begin{aligned} \partial _t \boldsymbol{\hat{u}}_i + \nabla \cdot \left\langle \boldsymbol{f}\left( \boldsymbol{u}\left( \boldsymbol{\hat{v}}(\boldsymbol{\hat{u}})^T\boldsymbol{\varphi }\right) \right) \varphi _i\right\rangle = \boldsymbol{0}\;, \quad \text { for } |i|\le N\;. \end{aligned}$$

(21)

The IPM system posses several desirable properties. Especially, if the entropy $s(\boldsymbol{u})$ fulfills the integrability condition (5), the IPM system is hyperbolic:

Theorem 2

The IPM system can be brought into its symmetric form with symmetric positive definite temporal Jacobian and symmetric spatial Jacobian, if the entropy $s(\boldsymbol{u})$ fulfills the integrability condition (5).

Proof

In its symmetric form, the IPM system (19) reads

$$\begin{aligned}&\boldsymbol{\hat{H}}(\boldsymbol{\hat{v}})\partial _t \boldsymbol{\hat{v}} + \sum _{j=1}^d \boldsymbol{\hat{B}}_j(\boldsymbol{\hat{v}})\partial _{x_j}\boldsymbol{\hat{v}} = \boldsymbol{0}\;, \end{aligned}$$

(22a)

$$\begin{aligned} \text {with }\quad&\boldsymbol{\hat{H}}(\boldsymbol{\hat{v}}) := \left\langle \nabla _{\boldsymbol{v}} \boldsymbol{u} (\boldsymbol{v}_N)\otimes \boldsymbol{\varphi }\boldsymbol{\varphi }^T \right\rangle \;,\end{aligned}$$

(22b)

$$\begin{aligned}&\boldsymbol{\hat{B}}_j(\boldsymbol{\hat{v}}) := \left\langle \nabla _{\boldsymbol{u}}\boldsymbol{f}_j(\boldsymbol{u}(\boldsymbol{v}_N))\nabla _{\boldsymbol{v}}\boldsymbol{u}(\boldsymbol{v}_N)\otimes \boldsymbol{\varphi }\boldsymbol{\varphi }^T\right\rangle \;. \end{aligned}$$

(22c)

Here, we abuse notation by defining the multiplication of $\boldsymbol{\hat{H}}\in \mathbb {R}^{m\cdot M\times m\cdot M}$ with $\boldsymbol{y} \in \mathbb {R}^{M\times m}$ by

$$\begin{aligned} \left( \boldsymbol{\hat{H}} \cdot \boldsymbol{y}\right) _{li} := \sum _{l'= 1}^m\sum _{i'= 1}^M \hat{H}_{(l-1)m+i,(l'-1)m+i'}y_{l'i'}\;. \end{aligned}$$

The same holds for the multiplication with $\boldsymbol{\hat{B}}_j$. As done for (12), if we can ensure $\boldsymbol{\hat{H}}$ being symmetric positive definite and $\boldsymbol{\hat{B}}_j$ symmetric, we know that the IPM system is hyperbolic. Obviously, $\boldsymbol{\hat{H}}$ is symmetric. Multiplication with $\boldsymbol{\hat{v}} \in \mathbb {R}^{M\times m}$ from both sides gives

$$\begin{aligned} \boldsymbol{\hat{v}}^T\boldsymbol{\hat{H}}\boldsymbol{\hat{v}} = \left\langle \boldsymbol{v}_N^T \nabla _{\boldsymbol{v}} \boldsymbol{u} (\boldsymbol{v}_N)\boldsymbol{v}_N \right\rangle > 0\;, \end{aligned}$$

where we use that $\nabla _{\boldsymbol{v}} \boldsymbol{u} = \boldsymbol{H}$ is symmetric positive definite as done in (12). It remains to show symmetry of $\boldsymbol{\hat{B}}_j$ for all $j=1,\cdots ,d$. Using the definition of $\boldsymbol{B}_j$ from (13), we can rewrite (22c) as

$$\begin{aligned} \boldsymbol{\hat{B}}_j(\boldsymbol{\hat{v}}) := \left\langle \boldsymbol{B}_j(\boldsymbol{v}_N)\otimes \boldsymbol{\varphi }\boldsymbol{\varphi }^T\right\rangle \;. \end{aligned}$$

By Theorem 1, we know that $\boldsymbol{B}_j$ is symmetric, from which we can conclude symmetry of $\boldsymbol{\hat{B}}_j$.    $\square$

Recall that solving the IPM system requires the mapping $\boldsymbol{\hat{v}}(\boldsymbol{\hat{u}})$, i.e. a mapping from the moments to the dual variables. This mapping can be defined by inverting the dual variables to moments map (20). The inverse exists, since the Jacobian of $\boldsymbol{\hat{u}}(\boldsymbol{\hat{v}})$ is $\nabla _{\boldsymbol{\hat{v}}}\boldsymbol{\hat{u}}(\boldsymbol{\hat{v}}) = \boldsymbol{\hat{H}}(\boldsymbol{\hat{v}})$ which is positive definite, i.e. the dual variables to moments map is strictly monotonically increasing. Unfortunately, the inversion can generally not be performed analytically. In this case one needs to determine $\boldsymbol{\hat{v}}$ by solving the non-linear system of equations

$$\begin{aligned} \left\langle \boldsymbol{u}\left( \boldsymbol{\hat{v}}^T\boldsymbol{\varphi }\right) \boldsymbol{\varphi }^T\right\rangle ^T = \boldsymbol{\hat{u}} \end{aligned}$$

(23)

for a given moment vector $\boldsymbol{\hat{u}}$ numerically. This task is commonly performed by reformulating (23) as a root-finding problem

$$\begin{aligned} \mathcal {G}(\boldsymbol{\hat{v}};\boldsymbol{\hat{u}}) {\mathop {=}\limits ^{!}} \boldsymbol{0} \end{aligned}$$

with

$$\begin{aligned} \mathcal {G}(\boldsymbol{w};\boldsymbol{\hat{u}}) := \left\langle \boldsymbol{u}\left( \boldsymbol{w}^T\boldsymbol{\varphi }\right) \boldsymbol{\varphi }^T\right\rangle ^T - \boldsymbol{\hat{u}}\;. \end{aligned}$$

(24)

Here, one often uses Newton’s method to determine the root of $\mathcal {G}$. Then, with $\nabla _{\boldsymbol{w}}\mathcal {G}(\boldsymbol{w};\boldsymbol{\hat{u}}) = {\boldsymbol{\hat{H}}(\boldsymbol{w})}$ a Newton update takes the form $\boldsymbol{d}:\mathbb {R}^{M\times m}\times \mathbb {R}^{M\times m}\rightarrow \mathbb {R}^{M\times m}$ with

$$\begin{aligned} \boldsymbol{d}(\boldsymbol{w},\boldsymbol{\hat{u}}):= \boldsymbol{w}-\boldsymbol{\hat{H}}({\boldsymbol{w}})^{-1}\cdot \mathcal {G}(\boldsymbol{w};\boldsymbol{\hat{u}})\;. \end{aligned}$$

(25)

The function $\boldsymbol{d}$ will in the following be called dual iteration function. Now, the Newton iteration for an input moment vector $\boldsymbol{\hat{u}}$ is given by

$$\begin{aligned} \boldsymbol{w}^{(l+1)} = \boldsymbol{d}(\boldsymbol{w}^{(l)},\boldsymbol{\hat{u}})\;. \end{aligned}$$

(26)

The exact dual state is then obtained by computing the fixed point of $\boldsymbol{d}$, meaning that one converges the iteration (26), i.e. $\boldsymbol{\hat{v}}:=\boldsymbol{\hat{v}}(\boldsymbol{\hat{u}})=\lim _{l\rightarrow \infty }\boldsymbol{d}(\boldsymbol{w}^{(l)},\boldsymbol{\hat{u}})$. To obtain a finite number of iterations, a stopping criterion

$$\begin{aligned} \sum _{i=0}^m\left\| \mathcal {G}(\boldsymbol{w}^{(l)};\boldsymbol{\hat{u}}) \right\| < \tau \end{aligned}$$

(27)

is used, where $\tau >0$ is a user determined parameter.

It remains to discuss the discretization of the spatial and time domain, which for ease of presentation, we perform for a scalar problem as well as a one dimensional spatial domain. When dividing the spatial domain into cells $[x_{j-1/2},x_{j+1/2}]$ with $j = 1,\cdots ,N_x$ and using discrete times $t_n$ with $n = 1,\cdots ,N_t$, we can approximate the i-th order moment by

$$\begin{aligned} \boldsymbol{\hat{u}}_{ij}^n \simeq \frac{1}{\Delta x}\int _{x_{j-1/ 2}}^{x_{j+1/ 2}}\boldsymbol{\hat{u}}_i(t_n,x) dx\;. \end{aligned}$$

The full moment vector in cell j at time $t_n$ is denoted by $\boldsymbol{\hat{u}}_j^n = (\boldsymbol{\hat{u}}_{0j}^n,\cdots ,\boldsymbol{\hat{u}}_{Nj}^n)^T\in \mathbb {R}^{M\times m}$. Furthermore, the corresponding dual variables are denoted by

$$\begin{aligned} \boldsymbol{\hat{v}}_{j}^n := \boldsymbol{\hat{v}}\left( \boldsymbol{\hat{u}}_j^n\right) \;. \end{aligned}$$

(28)

Then, a finite-volume scheme for the IPM system (21) can be written as

$$\begin{aligned} \boldsymbol{\hat{u}}_{j}^{n+1} = \boldsymbol{\hat{u}}_{j}^{n} - \frac{\Delta t}{\Delta x}\left( \boldsymbol{G}^*(\boldsymbol{\hat{v}}_{j},\boldsymbol{\hat{v}}_{j+1})- \boldsymbol{G}^*(\boldsymbol{\hat{v}}_{j-1},\boldsymbol{\hat{v}}_{j})\right) \;, \end{aligned}$$

(29)

where $\boldsymbol{G}^*:\mathbb {R}^{M\times m}\times \mathbb {R}^{M\times m}\rightarrow \mathbb {R}^{M\times m}$ is the numerical flux which needs to be consistent with the physical flux of the IPM system. i.e. we must have $\boldsymbol{G}^*(\boldsymbol{\hat{v}},\boldsymbol{\hat{v}})=\left\langle \boldsymbol{f}\left( \boldsymbol{u}\left( \boldsymbol{\hat{v}}^T\boldsymbol{\varphi }\right) \right) \boldsymbol{\varphi }^T\right\rangle$. In order to evaluate the moments to dual variables map (28), we can use the defined Newton iteration for the input moments $\boldsymbol{\hat{u}}_j^n$. Altogether, this yields the scheme from Algorithm 1.

4 Realizability-Preserving Spatial Discretization

In this section we further describe the concept of realizability and present a realizability-preserving discretization and improved version of Algorithm 1.

4.1 Realizability

As previously discussed, the IPM method and minimal entropy closures in general face several challenges. Besides increased computational costs, the IPM method cannot invert the mapping $\boldsymbol{\hat{u}}: \mathbb {R}^{M\times m}\rightarrow \mathcal {R}\subset \mathbb {R}^{M\times m}$ when the moment vector $\boldsymbol{\hat{u}}$ leaves the so-called realizable set $\mathcal {R}$, which results in a failure of the method [19]. To discuss this issue, we consider a scalar, one-dimensional conservation law of the form

$$\begin{aligned} \partial _t u(t,x,\xi ) + \partial _x f(u(t,x,\xi ))= & {} 0\;, \end{aligned}$$

(30a)

$$\begin{aligned} u(0,x,\xi )= & {} u_{\text {IC}}(x,\xi )\;, \end{aligned}$$

(30b)

i.e. m, p and d are equal to one. The following discussion is however valid for arbitrary dimensions and we make this simplification for ease of exposition. For scalar problems of the form (30), the solution fulfills the maximum–principle [16, Chapter 2.4]

$$\begin{aligned} \min _{x \in D, \xi \in \Theta } u_{\text {IC}}(x, \xi ) \le u(t, x, \xi ) \le \max _{x \in D, \xi \in \Theta } u_{\text {IC}}(x, \xi )\;, \end{aligned}$$

which ideally should be preserved by the discretization of the random domain. The IPM method at least enables one to impose a user-defined lower bound $u_-$ and upper bound $u_+$ on the solution by choosing an entropy s(u), which takes infinite values when $u\notin (u_-,u_+)$. One such entropy is the log-barrier entropy [33]

$$\begin{aligned} s(u) = -\ln (u-u_-)-\ln (u_+-u)\;. \end{aligned}$$

(31)

Then, by the entropy dissipation property (8), the IPM solution $u(v_N)\equiv (s')^{-1}(v_N)$ will remain inside the interval $(u_-,u_+)$. Similarly, for systems such as the Euler equations, certain solution quantities such as positivity of density, energy and pressure can again be achieved by the choice of a suitable entropy. Recall, that the image of the dual variables to moments map (20) has been denoted by $\mathcal {R}$. This set is called realizable set. For entropies imposing solution bounds $u_-$ and $u_+$ it is given by

$$\begin{aligned} \mathcal {R} := \left\{ \left. \boldsymbol{\hat{u}}\in \mathbb {R}^{N+1} \right| \exists u : \Theta \rightarrow (u_-,u_+) \text { such that } \boldsymbol{\hat{u}} = \langle u \boldsymbol{\varphi }\rangle \right\} \;. \end{aligned}$$

(32)

When proposing numerical methods to solve the IPM system (21), it is crucial to prevent the moments generated by this method from leaving this set, since then, the dual variables to moments map cannot be inverted, i.e. the system (23) has no solution. In the following, we propose an algorithm which keeps the moments inside $\mathcal {R}$ and we will refer to this property as preserving realizability.

4.2 Realizability-Preserving Discretization

The presented general Algorithm 1 will not necessarily preserve realizability, i.e. it generates moments $\boldsymbol{\hat{u}}\notin \mathcal {R}$. The two sources for this are the choice of the numerical flux as well as the fact that the system (23) cannot be solved exactly, i.e. the moments to dual variables map has errors. Let us first write down the realizability preserving algorithm presented in [19] and then discuss why it maintains $\boldsymbol{\hat{u}}\notin \mathcal {R}$. When again using $u:\mathbb {R}^{N+1}\rightarrow \mathbb {R}^{N+1}$ with $u(v) = (s')^{-1}(v)$, the chosen numerical flux is the kinetic flux

$$\begin{aligned} \boldsymbol{G}^*(\boldsymbol{\hat{v}}_{\ell },\boldsymbol{\hat{v}}_{r}) = \left\langle f^*(u(\boldsymbol{\hat{v}}_{\ell }^T\boldsymbol{\varphi }),u(\boldsymbol{\hat{v}}_{r}^T\boldsymbol{\varphi })) \boldsymbol{\varphi }\right\rangle \;, \end{aligned}$$

(33)

where $f^*(u_{\ell },u_r)$ is a monotone flux for the underlying deterministic problem. Note that this choice of $\boldsymbol{G}^*$ is common in the field of kinetic theory, see e.g. [8, 13, 31, 32]. We assume that the original, deterministic scheme

$$\begin{aligned} H(u,v,w) = v -\frac{\Delta t}{\Delta x} \left( f^*(v,w) -f^*(u,v)\right) \end{aligned}$$

(34)

keeps the solution inside the bounds $u_-$ and $u_+$, i.e. $H(u_{j-1}^n,u_{j}^n,u_{j+1}^n)\in [u_-,u_+]$ if all inputs are bounded by $u_-,u_+$. This can for example be achieved with monotone schemes or, for high order methods, with bound preserving limiters [4, 7, 12, 26, 41]. Note that since the integral in (33) can generally not be solved analytically, a quadrature rule must be employed to approximate the kinetic flux. It can however be shown that the resulting quadrature error will not influence realizability of the numerical scheme. Then, a realizability preserving implementation is given by

Here, we use and instead of $\boldsymbol{\hat{v}}$ and $\boldsymbol{\hat{u}}$ to stress that these quantities are affected by the inexact Newton iteration. The main difference to Algorithm 1, besides the choice of the numerical flux, is the recalculation of the moment vector from the inexact dual variables in line 9. It can be shown that Algorithm 2 preserves realizability: To simplify notation, let us define the exact and inexact dual states $\Lambda := v_N = \boldsymbol{\hat{v}}^T\boldsymbol{\varphi }$ and . Then, the inexact moments are given by

(35)

and the moment update becomes

(36)

Plugging the definition of the inexact moments (35) into the moment update (36) yields

Now, since the ansatz $u(\Lambda ) = (s')^{-1}(\Lambda )$ only takes values in $[u_-,u_+]$, we have

for all $\xi \in \Theta$. Therefore, the time updated moments belong to an underlying function which is bounded by $u_-$ and $u_+$, i.e. we have $\boldsymbol{\hat{u}}_j^{n+1}\in \mathcal {R}$. The construction of the presented algorithm also guarantees that the CFL condition of the original scheme ensures stability. Note that the presented IPM scheme can be extended to systems, multi-dimensional problems and higher order methods, whenever a bound-preserving scheme (34) exists. Furthermore, when replacing all integrals by quadrature rules, the time updated moments will remain realizable, since they belong to a function which fulfills the prescribed bounds on the quadrature points. The main drawback of this strategy to preserve realizability is that it introduces a non-conservative error by recalculating moments. However, when using a Lipschitz continuous numerical flux $\boldsymbol{G}^*$, the error by recalculating moments is of order $\mathcal {O}(\tau )$ [19]. I.e. by choosing a sufficiently small stopping criterion for Newton’s method the error from the recalculation step becomes negligibly small.

A second strategy, which does not require recomputing moments and therefore does not add such an error is choosing a modified CFL condition. Here, the main idea is to account for effects the error in $\Lambda$ has on the scheme by choosing a smaller time step size. Denoting this error by

a more restrictive CFL condition, which ensures realizability is given by

Theorem 3

Let us assume that the entropy ansatz only takes values in $(u_-, u_+)$ and the underlying numerical flux $f^*$ is monotone. If furthermore, the numerical optimizer enforces the stopping criterion

$$\begin{aligned} \max _{\xi \in \Theta }\left\{ \max _{\Lambda \in \left[ \bar{\Lambda }_{j,\text {min}}^n,\bar{\Lambda }_{j,\text {max}}^n\right] }\frac{ u'(\Lambda (\xi ))}{u'(\Lambda (\xi ) + \Delta \Lambda _j^n(\xi ))}\right\} \le \gamma \;, \end{aligned}$$

(37)

with

the time updated moment vector $\boldsymbol{\hat{u}}^{n + 1}_j$ is realizable under the modified CFL condition

$$\begin{aligned} \gamma \frac{\Delta t}{\Delta x} \max _{u\in [u_-,u_+]} \vert f'(u)\vert \le 1\;. \end{aligned}$$

(38)

The proof of this theorem as well as an implementation strategy can be found in [19]. Due to its simplicity and efficient implementation of different discretization schemes, we will use the strategy of recalculating moments, i.e. Algorithm 2 in the following.

5 Accelerating the IPM Solution

In this section we describe two acceleration techniques, as presented in [23], which reduce the numerical effort of the IPM method.

5.1 Adaptivity

As previously mentioned, in contrast to non-intrusive methods, intrusive methods allow a more fine-grained control over the solution, as the uncertainties or more precisely their respective moments, are directly propagated through time and the corresponding quantities of interest (e.g. mean or variance) are not collected in a secondary step as in e.g. SC or MC methods. Using adaptivity, we try to avoid using high-order moment representations and corresponding high order quadrature rules in portions of the domain, where the quantities of interest are well-represented with low-order moments. As these lower-order moment bases result in non-linear system (23) that are easier to solve, this approach can significantly reduce overall runtimes. We use the discontinuity sensor described in [30] in the UQ context. To do this, the polynomial approximation at refinement level $\ell$ is defined as

$$\begin{aligned} \boldsymbol{\tilde{u}}_{\ell } := \sum _{|i|\le M_{\ell }} \boldsymbol{u}_i \varphi _i\;. \end{aligned}$$

We further define an indicator for a moment vector at level $\ell$ as

$$\begin{aligned} \boldsymbol{S}_{\ell } := \frac{\langle \left( \boldsymbol{\tilde{u}}_{\ell } - \boldsymbol{\tilde{u}}_{\ell -1}\right) ^2\rangle }{\langle \boldsymbol{\tilde{u}}_{\ell }^2\rangle }\;. \end{aligned}$$

(39)

Note, that a similar indicator has been used in [17] for intrusive methods in UQ. We use the first element in $\boldsymbol{S}_{\ell }$, i.e. the density $\rho$, to determine the refinement level. This regularity indicator is therefore computed for every cell at every timestep and the current refinement level is kept if the indicator lies in the interval $I_{\delta }:=[\delta _{-},\delta _{+}]$. If its value falls below $\delta _{-}$, the refinement level is decreased to the next lower refinement level and vice versa if the value exceeds $\delta _{+}$. See [23] for more details on the method.

5.2 One-Shot IPM

The second method is limited to steady state problems. In this case, we are interested in solving

$$\begin{aligned} \nabla \cdot \boldsymbol{f}(\boldsymbol{u}(\boldsymbol{x},\boldsymbol{\xi })) = \boldsymbol{0} \text { in } D \end{aligned}$$

(40)

with adequate boundary conditions. Then, the IPM moment system reads

$$\begin{aligned} \nabla \cdot \langle \boldsymbol{f}(\boldsymbol{u}(\boldsymbol{v}_N(\boldsymbol{x},\boldsymbol{\xi })))\boldsymbol{\varphi }^T\rangle ^T = \boldsymbol{0} \text { in } D\;. \end{aligned}$$

(41)

Steady state problems are usually solved by introducing a pseudo-time and iterating the solution until the condition

$$\begin{aligned} \sum _{j = 1}^{N_x} \Delta x_j \Vert \boldsymbol{\hat{u}}_j^n - \boldsymbol{\hat{u}}_j^{n-1} \Vert \le \varepsilon \;, \end{aligned}$$

(42)

with convergence tolerance $\varepsilon$, is fulfilled. To obtain a more compact notation, let us define the pseudo-time update of the moments by

$$\begin{aligned} \boldsymbol{c}(\boldsymbol{w}_{\ell },\boldsymbol{w}_c,\boldsymbol{w}_r)&:= \langle \boldsymbol{u}(\boldsymbol{w}_c^T\boldsymbol{\varphi })\boldsymbol{\varphi }^T\rangle ^T \\ \nonumber&- \frac{\Delta t}{\Delta x}\left( \langle \boldsymbol{g}(\boldsymbol{u}(\boldsymbol{w}_c^T\boldsymbol{\varphi }),\boldsymbol{u}(\boldsymbol{w}_r^T\boldsymbol{\varphi }))\boldsymbol{\varphi }^T\rangle ^T-\langle \boldsymbol{g}(\boldsymbol{u}(\boldsymbol{w}_{\ell }^T\boldsymbol{\varphi }),\boldsymbol{u}(\boldsymbol{w}_c^T\boldsymbol{\varphi }))\boldsymbol{\varphi }^T\rangle ^T\right) \;. \end{aligned}$$

(43)

Note that the first term of this update recalculates moments from inexact dual variables, i.e. we perform a recalculation step according to Algorithm 2. To indicate the usage of inexact dual states, we again use the notation . Then, the moment iteration of cell j, which is performed until (42) is fulfilled reads

(44)

During each iteration, the dual variables are again obtained by iterating

$$\begin{aligned} \boldsymbol{v}_j^{(l+1)} = \boldsymbol{d}(\boldsymbol{v}_{j}^{(l)};\boldsymbol{\hat{u}}_j^{n}) \end{aligned}$$

until the stopping criterion (27) is fulfilled. A schematic of this method is given in Fig. 1. In the following, we refer to updating the dual variables as the inner loop and the iteration of the moments as the outer loop. The key idea of the One-Shot IPM (osIPM) method is to break up the inner loop and iterate moments and dual variables to their steady state simultaneously. This method is motivated by the One-Shot method in shape optimization [15], which proposes to perform only a single iteration for the primal, dual and design updates. The osIPM method now reads

$$\begin{aligned} \boldsymbol{v}_{j}^{n+1} = \boldsymbol{d}(\boldsymbol{v}_j^{n},\boldsymbol{\hat{u}}_j^{n}) \text { for all j}\;, \end{aligned}$$

(45a)

Note that the dual variables from the One-Shot iteration are written without a bar to indicate that they are not intended to be a solution of the dual problem. It can be shown that the osIPM method converges locally [23]. Numerical studies show that the One-Shot IPM method requires more iterations of the outer loop compared to the general IPM method, but as these iterations are significantly cheaper in terms of computational effort, the method yields a significant boost in the performance [23].

Fig. 1

Left: IPM method for steady state problems. Right: osIPM method. The use of $\Delta$ indicates that all spatial cells of the corresponding quantity are collected in a vector.

6 Results

In order to demonstrate the properties of the presented IPM method and the related acceleration techniques, in this section we show four different test cases for the Burgers and the Euler equations, each highlighting different aspects.

6.1 Burgers’ Equation

In the following, we investigate Burgers’ forming shock testcase from [33], which has also been investigated in [19,20,21,22]. The stochastic Burgers equation for a one-dimensional spatial domain is given by

$$\begin{aligned} \partial _t u(t,x,\xi ) + \partial _x \frac{u(t,x,\xi )^2}{2}= & {} 0\;, \\ u(t=0,x,\xi )= & {} u_{\text {IC}}(x,\xi )\;. \end{aligned}$$

The initial condition is now randomly distributed, i.e. we have

$$\begin{aligned} u_{\text {IC}}(x,\xi ):= & {} {\left\{ \begin{array}{ll} u_L, &{} \text{ if } x< x_0+\sigma \xi \\ u_L+\frac{u_R-u_L}{x_0-x_1} (x_0+\sigma \xi -x), &{} \text{ if } x\in [x_0+\sigma \xi ,x_1+\sigma \xi ]\\ u_R, &{} \text {else } \end{array}\right. }\;. \end{aligned}$$

(46)

The initial condition describes a forming shock with a linear connection from $x_0+\sigma \xi$ to $x_1+\sigma \xi$, i.e. the random variable $\xi$ shifts the forming shock structure to the left and right. We assume a uniformly distributed random variable in the interval $[-1,1]$, i.e. $\xi \sim U([-1,1])$. Furthermore, we use the following parameter values:

$D = [a,b]=[0,3]$	Range of spatial domain
$N_x=2000$	Number of spatial cells
$t_{\text {end}}=0.0909$	End time
$x_0 = 0.5, x_1=1.5, u_L = 12, u_R = 1, \sigma = 0.2$	Parameters of initial condition (46)
$N+1 = 6$	Number of moments
$\varepsilon = 10^{-7}$	Accuracy of Newton’s method

We compare the solution in $\xi$ at a fixed spatial position $x^*$ for time $t_{\text {end}}$ for stochastic-Galerkin and IPM in Fig. 2. The IPM method uses the bounded–barrier entropy

$$\begin{aligned} s(u) = (u-u_-)\ln (u-u_-)+(u_+-u)\ln (u_+-u)\;, \end{aligned}$$

which, in contrast to the log–barrier entropy (31) takes finite values at $u_-$ and $u_+$. Indeed, as seen in Sect. 4.2, it suffices that the ansatz $\left( s'\right) ^{-1}$ only takes values in $[u_-,u_+]$ to enforce such bounds. For the bounded–barrier entropy, we can choose the distance to the exact solution to be zero, i.e. we have $\Delta u := u_R - u_- = u_+ - u_L = 0$. We also show results for the log–barrier entropy with $\Delta u = 0.5$. It can be seen that stochastic-Galerkin oscillates heavily while both IPM solutions maintain the overall shock characteristics. However, the bounded–barrier entropy is able to capture the shock more adequately while maintaining the maximum–principle (15). In the following, we focus on the bounded–barrier entropy and investigate its behavior when approximating expectation value and variance. For this, we let the simulation run until an increased end time $t_{\text {end}}=0.14$ is reached. Expectation value and variance are shown in Fig. 3. While stochastic-Galerkin yields a step-like profile, the IPM method when using the bounded–barrier entropy shows a significantly improved solution. Note, that the log–barrier entropy yields a similar result.

Fig. 2

Solution SG and IPM with bounded–barrier ($\Delta u=0$) and log–barrier ($\Delta u=0.5$) entropies at fixed spatial position $x^* = 1.5$ for time $t_{\text {end}}=0.0909$.

6.2 Euler Equations

A further commonly used test case for intrusive methods is Sod’s shock tube with uncertain shock position, see for example [22, 33, 34]. The stochastic Euler equations in one spatial dimension read

$$\begin{aligned} \partial _t \begin{pmatrix} \rho \\ \rho u \\ \rho e \end{pmatrix} +\partial _x \begin{pmatrix} \rho u \\ \rho u^2 +p \\ u(\rho e+p) \end{pmatrix} =\boldsymbol{0}\;, \end{aligned}$$

where, in our test case, we use the initial condition

$$\begin{aligned} \rho _{\text {IC}}= & {} {\left\{ \begin{array}{ll} \rho _L &{}\text{ if } x< x_{\text {interface}}(\xi ) \\ \rho _R &{} \text{ else } \end{array}\right. }\;, \\ (\rho u)_{\text {IC}}= & {} 0\;, \\ (\rho e)_{\text {IC}}= & {} {\left\{ \begin{array}{ll} \rho _L e_L &{}\text{ if } x < x_{\text {interface}}(\xi ) \\ \rho _R e_R &{} \text{ else } \end{array}\right. }\;. \end{aligned}$$

Here, $\rho$ denotes the density, u is the velocity and e is the specific total energy. One can determine the pressure p from

$$\begin{aligned} p = (\gamma -1)\rho \left( e-\frac{1}{2}u^2\right) \;. \end{aligned}$$

Fig. 3

Expectation value and variance for SG and IPM at time $t_{\text {end}}=0.14$.

The heat capacity ratio is $\gamma$ and has a value of 1.4 for air. We use the random interface position $x_{\text {interface}}(\xi ) = x_0+\sigma \xi$, where $\xi$ is again uniformly distributed in the interval $[-1,1]$. The IPM method again needs to pick a suitable entropy. In this work, we choose the entropy

$$\begin{aligned} s(\rho ,\rho u,\rho e) = -\rho \ln \left( \rho ^{-\gamma }\left( \rho e-\frac{(\rho u)^2}{2\rho }\right) \right) \;, \end{aligned}$$

though more choices are possible. Parameter values which differ from Burgers’ test case are

$D=[a,b]=[0,1]$	Range of spatial domain
$N_x=5000$	Number of spatial cells
$t_{\text {end}}=0.14$	End time
$x_0 = 0.5, \sigma = 0.05$	Interface position parameters
$\rho _L = 1.0,e_L = 2.5, \rho _R = 0.125,e_R = 0.25$	Initial states

When running the simulation, the SG method fails already during the first time update. The reason for this can be seen in Fig. 4. Here, the SG and IPM reconstructions of the gas density $\rho$ are depicted at $t=0\ \text {s}$ at a fixed spatial cell. While the IPM reconstruction maintains positivity, the Gibbs phenomena that result from the polynomial representation of SG lead to negative density values. A similar behavior can be seen for the energy e. Then, the eigenvalues of the Euler equations, which include $v\pm \sqrt{\gamma p/\rho }$ become complex, i.e. the system is no longer hyperbolic.

Fig. 4

Initial density for SG and IPM at fixed spatial position $x^* = 0.46$ when using 6 moments. The view is zoomed to $\xi \in [-1,0]$ and negative regions are marked in red.

Fig. 5

Expectation value and variance for SG and IPM at time $t_{\text {end}}=0.14\ \text {s}$.

As discussed, the IPM method maintains hyperbolicity, meaning that one can run the simulation until the desired end time $t_{\text {end}}=0.14\ \text {s}$ is reached. The resulting expectation values and variances are depicted in Fig. 5. It can be seen that the IPM method yields a satisfactory approximation of the expectation value and variance at the rarefaction wave as well as the contact discontinuity. However, the shock yields discontinuous step-like profiles, similar to the stochastic-Galerkin results for Burgers’ equation.

6.3 2-D Euler Equations with One-Shot

In order to demonstrate the acceleration impact of the aforementioned One-Shot strategy for the steady-state case, we will quantify the effects of an uncertain angle of attack $\phi \sim U(0.75,1.75)$ for a NACA0012 airfoil using the Euler equations in two spatial dimensions. This test-case is taken from [23]. Similar to the 1-D case, the stochastic Euler equations in two dimensions are given by

$$\begin{aligned} \partial _t \begin{pmatrix} \rho \\ \rho u_1 \\ \rho u_2 \\ \rho e \end{pmatrix} +\partial _{x_1} \begin{pmatrix} \rho u_1 \\ \rho u_1^2 +p \\ \rho u_1 u_2 \\ u_1 (\rho e+p) \end{pmatrix} +\partial _{x_2} \begin{pmatrix} \rho u_2 \\ \rho u_1 u_2 \\ \rho u_2^2+p \\ u_2 (\rho e+p) \end{pmatrix} =\boldsymbol{0}\;, \end{aligned}$$

with the closure term for the pressure as

$$\begin{aligned} p = (\gamma -1)\rho \left( e-\frac{1}{2}(u_1^2+u_2^2)\right) \;. \end{aligned}$$

As in the previous test case, the heat capacity ratio is set to $\gamma = 1.4$. For this test case, we apply the Euler slip boundary condition to the airfoil’s boundary as $\boldsymbol{v}^T\boldsymbol{n} = 0$, where $\boldsymbol{n}$ denotes the surface normal. At a sufficiently large distance away from the airfoil, we prescribe a far field flow with a given Mach number of $Ma = 0.8$, pressure $p = 101\;325\ \text {Pa}$ and a temperature of $273.15\ \text {K}$. The uncertain angle of attack $\phi$ is uniformly distributed in the interval of [0.75, 1.75] degrees or in other words $\phi (\xi ) = 1.25 + 0.5\xi$ with $\xi \sim U(-1,1)$. The initial condition in the entire domain is equal to the far field boundary values and thus violates the Euler slip boundary condition at the airfoil. Consequently, we iterate in pseudo-time to correct the flow solution until the expectation value of the density fulfills the criterion (42) with $\varepsilon = 6\cdot 10^{-6}$.

The used computational mesh (see Fig. 6c) consists of $22\;361$ triangular elements and resembles a circular domain of $40\ \text {m}$ diameter, where the airfoil of $1\ \text {m}$ length is located at the very center. The mesh is finely resolved close to the airfoil as we are only interested in effects close to the airfoil and becomes coarser the closer to the far field boundary. In order to be able to measure the quality of the obtained solutions with and without the One-Shot acceleration strategy, we compute a reference solution using stochastic-Collocation with 100 Gauss-Legendre quadrature points (see Fig. 6). We will show the L$^2$-error behavior of the discrete quantity $\boldsymbol{e}_{\Delta }=(\boldsymbol{e}_1,\cdots ,\boldsymbol{e}_{N_x})^T$, where $\boldsymbol{e}_j$ is the cell average of the quantity $\boldsymbol{e}$ in spatial cell j. The discrete L$^2$ norm is denoted by

Fig. 6

Reference solution E$[\rho ]$ and Var$[\rho ]$ and the mesh close to the airfoil which is used in the computation of all presented methods.

Fig. 7

Comparison of the relative L$^2$-error of the density for IPM, osIPM, readosIPM and SC. All IPM related methods are converged to a residual of $\varepsilon =6\cdot 10^{-6}$, whereas SC is converged to a residual of $\varepsilon =1\cdot 10^{-7}$. All computations are performed with 5 MPI threads.

$$\begin{aligned} \Vert \boldsymbol{e}_{\Delta } \Vert _{\Delta } := \sqrt{\sum _{j=1}^{N_x} \Delta x_j \boldsymbol{e}_j^2}\;. \end{aligned}$$

Given the SC reference solution $\boldsymbol{u}_{\Delta }$ and the moments of a compared numerical method $\boldsymbol{\hat{u}}_{\Delta }$, we investigate the relative error

$$\begin{aligned} \frac{\Vert \text {E}[\boldsymbol{u}_{\Delta }] - \text {E}[\mathcal {U}(\boldsymbol{\hat{u}}_{\Delta })] \Vert _{\Delta }}{\Vert \text {E}[\boldsymbol{u}_{\Delta }] \Vert _{\Delta }} \qquad \text { and }\qquad \frac{\Vert \text {Var}[\boldsymbol{u}_{\Delta }] - \text {Var}[\mathcal {U}(\boldsymbol{\hat{u}}_{\Delta })] \Vert _{\Delta }}{\Vert \text {Var}[\boldsymbol{u}_{\Delta }] \Vert _{\Delta }}\;. \end{aligned}$$

As small fluctuations in the large cells of the coarse far field would dominate this error measure, we only compute the error inside a box of one meter height and 1.1 m length around the airfoil. Figure 7 shows the resulting error with respect to the reference solution of IPM, osIPM and SC. The superscript in the figure denotes the number of used quadrature points, whereas the subscript denotes the moment order. We chose a total polynomial order of 9 for all IPM methods, meaning 10 moments are used in the computation and a Clenshaw-Curtis quadrature rule of order 4, resulting in 17 quadrature points. Based on the same quadrature set, all IPM solutions were also compared to a SC solution in order to get a better understanding of the methods convergence behavior and acceleration properties of osIPM. As it can be seen from the presented results, the osIPM yields the same error and almost identical convergence history as IPM, while being significantly faster. In comparison to SC however, the errors for the mean as well as the variance are comparably small, but the SC method reaches the given error level faster in terms of computational time. Only when the One-Shot approach is combined with adaptivity and refinement retardation, as it can be seen for the readosIPM plot in Fig. 7, the IPM method is yields even faster convergence rates than SC. For more information about refinement retardation and adaptivity, see [23]. Also note that the acceleration of the One-Shot approach becomes more dominant when looking at higher dimensional uncertainties, see [23].

6.4 Unsteady 2-D Euler Equations with Adaptivity

To investigate adaptivity, we again use the two dimensional Euler equations. The problem setting is similar to the transient Sod shock tube test case from above. The geometry describes a nozzle similar to a de Laval nozzle (see Fig. 8e), where the initial condition is set to a discontinuity positioned in the middle of the narrow part of the nozzle. The density in the left part is set to $1\ \text {kg}\ \text {m}^{-3}$ and the energy is set to $\rho e = p/(\gamma -1) = 2.5\ \text {J}\ \text {m}^{-3}$ with the pressure p equal to $1\ \text {Pa}$. For the right part of the domain the density is set to $\rho = 0.8\ \text {kg}\ \text {m}^{-3}$ and the pressure $p = 0.125\ \text {Pa}$. The gas in both sides is at rest. For this testcase we inflict the initial condition with one uncertainty, i.e. the shock’s position, which is now modeled as $x_\text {shock}\sim U(-0.5, 0.5)$. The used computational mesh consists of $76\;696$ triangular cells and is refined in the area of the shock and the nozzle opening towards the right side of the domain (see Fig. 8a). The applied boundary conditions are Euler slip conditions for the wall of the nozzle and Dirichlet conditions set to the initial condition for the left and right side of the mesh. The shown results in Fig. 8 resemble a time of $6\ \text {s}$.

As for the previous testcases, the reference solution was computed using stochastic-Collocation (see Figs. 8a, 8b) with a Gauss-Legendre quadrature with 50 quadrature points. As the previously mentioned parameter $\delta _{\pm }$ are user determined, these refinement/coarsening thresholds were set to $\delta _{-} = 1.5E-3$ and $\delta _{+} = 5E-4$ for the presented results in Figs. 8c, 8d. The resulting refinement levels are shown in Fig. 8c and the total order of used moments in combination with the associated quadrature points for each refinement level are given in Table 1. For the quadrature a tensorized Clenshaw-Curtis rule is used.

Table 1 Moment and quadrature setup for the applied refinement levels.

As for the previous test cases, we observe a good agreement between the IPM and the reference solution computed by SC. Due to the lower degree of moments the IPM solution again show a more step-like profile in the emerging shocks. As expected, the presented refinement levels are high in the regions around the shock and lower order moments are started to be used further upstream where the flow becomes more and more constant as time progresses. Further upstream of the shock, the method even uses the lowest refinement level as the shock has not yet reached this part of the nozzle and thus the solution is still equal to the initial condition. All in all the results show that the method chooses high levels of refinement in areas where they are required by the complexity of the solution. Thus, the method is computationally much of efficient in the remainder of the domain.

Fig. 8

Comparison for the mean and variance of the SC reference solution (a, b) and the adaptive IPM method (c, d) with the refinement levels in f. e shows the computational mesh. All computations are performed using 20 MPI threads.