Numerical Aspects of Model Order Reduction for Gas Transportation Networks

Abstract

The chapter focuses on the numerical solution of parametrized unsteady Eulerian flow of compressible real gas in pipeline distribution networks. Such problems can lead to large systems of nonlinear equations that are computationally expensive to solve by themselves, more so if parameter studies are conducted and the system has to be solved repeatedly. The stiffness of the problem adds even more complexity to the solution of these systems. Therefore, we discuss the application of model order reduction methods in order to reduce the computational costs. In particular, we apply two-sided projection via proper orthogonal decomposition with the discrete empirical interpolation method to exemplary realistic gas networks of different size. Boundary conditions are represented as inflow and outflow elements, where either pressure or mass flux is given. On the other hand, neither thermal effects nor more involved network components such as valves or regulators are considered. The numerical condition of the reduced system and the accuracy of its solutions are compared to the full-size formulation for a variety of inflow and outflow transients and parameter realizations.

1 Introduction

Gas as an energy source is being transported from producer or supplier to consumer along pipelines via short or long distances. Size and complexity of these transportation networks will thus vary notably. Maybe the most typical question with regard to such gas transportation problems is if the supply can satisfy consumer demands. Often this question is coupled with the goal to operate the network efficiently and to account for variations either in supply, demand or in the network properties itself. The latter problem might, e.g., result from the difficulty to measure pipeline properties such as roughness exactly. Since gas is compressible such that the network may hold strongly varying amounts, transient effects can become important.

All these questions and goals can in principle be answered by numerical simulation provided that the method of simulation is accurate enough while being efficient at the same time. Efficiency and computational costs depend on network size, nonlinearity, and stiffness of the underlying equations. In order to manage size while dealing with nonlinearity we demonstrate how a nonlinear model order reduction method can be applied, which is tailored to the problem in that the general form of the original equations is respected in the reduced order systems.

Certain important assumptions are made in order to simplify the problem, the most prominent of which is the neglect of all network elements except for simple pipelines, junctions, inflow and outflow elements. Moreover, we assume a single phase of an ideal gas flowing through the pipes, disregard most temperature effects, and make further assumptions that allow us to rewrite the problem as a system of ordinary differential equations. Some of these assumptions are made in favor of a simple exposition of the topic, while others originate from numerical considerations.

Transient simulation of gas networks is a very active field of research. Model order reduction for this system is treated on a more basic level by [3]. Many different approaches on how to efficiently compute transient behavior are known in the literature [6, 9, 10]. The main goal of this chapter is to introduce the reader to basic concepts of model order reduction involving its practical application. Thus we present three example networks of different complexity that form the foundation of a comprehensive treatment of a nonlinear reduced order method, including numerical tests with a focus on stiffness, accuracy, and computational cost.

How the laws of continuum mechanics can be applied to model gas flow through a network of pipes is explained in Section 2, including three different example problems to be used in later sections. Basic notions and definitions of stiffness are discussed in Section 3 with the application and example problems in mind. Section 4 introduces basic concepts of model order reduction with a focus on nonlinear methods suitable for gas transport networks, while Section 5 presents and discusses results for the example cases. The final section of this chapter summarizes the main topics and touches further interesting questions.

2 Problems in Network Simulation

We consider the simulation of gas flowing through a system of branching pipelines with influx and outflux defined at determined locations. First the network model itself is described, including continuum mechanics for the flow through a single pipe and mass conservation at pipeline junctions. Subsequently, we present example networks later used to empirically analyze the simulation of resulting full and reduced order systems.

2.1 Pipe Network Modeling

A gas transportation network can be described as a directed graph $\mathcal{G} = (\mathcal{E},\mathcal{N})$, where $\mathcal{N}$ is the set of nodes and $\mathcal{E}$ is the set of directed edges. Those edges are denoted by tuples of nodes. We distinguish between so-called supply nodes $\mathcal{N}_{s}$, demand nodes $\mathcal{N}_{d}$, and interior nodes $\mathcal{N}_{0}$, where $\mathcal{N} = \mathcal{N}_{s} \cup \mathcal{N}_{0} \cup \mathcal{N}_{d}$. If we choose not to consider more involved components, each edge represents a pipe and can thus be specified by length, width, and roughness. Nodes, on the other hand, can be imagined as the points where pipes start, end, or meet. The physics of a fluid moving through a single pipe can be modeled by the isothermal Euler equations averaged over the pipe’s cross-section $A = \frac{\pi } {4}D^{2}$ with inner pipe diameter D, see [11].

Now several simplifications are applied. Discarding terms related to kinetic energy, we first get

$$\displaystyle\begin{array}{rcl} \partial _{t}\rho + \partial _{x}q& =& 0,{}\end{array}$$

(1a)

$$\displaystyle\begin{array}{rcl} \partial _{t}q + \partial _{x}p + g\rho \partial _{x}h = -\frac{\lambda (q)} {2D}\rho v\vert v\vert,& &{}\end{array}$$

(1b)

$$\displaystyle\begin{array}{rcl} p& =\gamma (T)z(p,T)\rho.&{}\end{array}$$

(1c)

Here ρ denotes the fluid’s density, p the pressure, and q the volumetric flux. Together they form the set of unknown dynamical variables and depend on space and time (t, x). Velocity is denoted by $v = \frac{q} {\rho }$. The system consists of three equations, two for mass and momentum conservation (1a,1b) and one that specifies material properties (1c). Momentum conservation (1b) includes a term on the left-hand side to incorporate gravity g as a conservative body force depending on height h, as well as a friction term on the right-hand side.

As an approximation to the friction coefficient λ(q), we use

$$\displaystyle{\lambda = \left (2\log \left (\frac{D} {\kappa } \right ) + 1.138\right )^{-2},}$$

where D is again the diameter of the pipe and κ a parameter describing its roughness. Notice that this approximation, called the Swamee-Jain equation [12], neglects the dependence of friction on flux q if we assume, for simplicity again, that roughness κ does not depend on q. The field γ = RT embodies gas properties by its dependence on a given gas temperature T and on the universal gas constant R. For further simplification we assume that the temperature T ≡ T ₀ is constant in time and space and that we deal with an ideal gas (i.e., z ≡ 1). Thus, γ = RT ₀ is constant and we can rewrite the constitutive assumption as p = γ ρ.

Without change of notation, volumetric flux is now substituted by mass flux q ← Aq. Along with the relation $v = \frac{q} {\rho }$ the simplified isothermal Euler equations take the form

$$\displaystyle\begin{array}{rcl} \partial _{t}\rho + \frac{1} {A}\partial _{x}q = 0,& &{}\end{array}$$

(2a)

$$\displaystyle\begin{array}{rcl} \frac{1} {A}\partial _{t}q + \partial _{x}p + g\rho \partial _{x}h = - \frac{\lambda } {2DA^{2}} \frac{q\vert q\vert } {\rho },& &{}\end{array}$$

(2b)

$$\displaystyle\begin{array}{rcl} p =\gamma \rho,& &{}\end{array}$$

(2c)

or substituting ρ according to (2c),

$$\displaystyle\begin{array}{rcl} \partial _{t}p& =& - \frac{\gamma } {A}\partial _{x}q, \\ \partial _{t}q& =& -A\partial _{x}p -\frac{Ag} {\gamma } p\partial _{x}h - \frac{\lambda \gamma } {2DA} \frac{q\vert q\vert } {p}.{}\end{array}$$

(3)

Within the pipe network, (3) is valid for each edge. Any edge stands for a pipe parametrized along its given length L, which means the interval [0, L] establishes the domain of definition of the according partial differential equation. The full system of equations additionally encompasses consistency conditions for each demand node as well as input in terms of supply pressures given at supply nodes.¹ If we assemble all pipes that end in node i into the set I _R ⁱ and, accordingly, all pipes that start in node i into the set I _L ⁱ, then the demand consistency conditions are given by

$$\displaystyle\begin{array}{rcl} 0 =\sum _{l\in I_{L}^{i}}q_{l}(L_{l},t) -\sum _{k\in I_{R}^{i}}q_{k}(0,t) + d_{i}(t)& &{}\end{array}$$

(4)

for every node i.² If

$$\displaystyle\begin{array}{rcl} d_{i}(t) \equiv 0,& &{}\end{array}$$

(5)

this condition reduces to the well-known Kirchhoff law and is valid at any junction of pipes. Strictly speaking, (4) holds for all nodes in $\mathcal{N}_{0} \cup \mathcal{N}_{d}$, whereas for nodes in $\mathcal{N}_{0}$ we additionally have (5).

Let n _E be the number of edges and assume they are ordered such that every edge has an index in $[1,2,\ldots,n_{E}]$. Once we discretize (3) following [4] and add given supply pressures, the resulting overall differential algebraic system of equations is given by

$$\displaystyle\begin{array}{rcl} \partial _{t}\frac{p_{R}^{k} + p_{L}^{k}} {2} & =& - \frac{\gamma } {A_{k}} \frac{q_{R}^{k} - q_{L}^{k}} {L_{k}} \quad \forall k \in [1,\ldots,n_{E}],{}\end{array}$$

(6a)

$$\displaystyle\begin{array}{rcl} \partial _{t}\frac{q_{R}^{k} + q_{L}^{k}} {2} & =& -A_{k}\frac{p_{R}^{k} - p_{L}^{k}} {L_{k}} -\frac{A_{k}g} {2\gamma } (p_{R}^{k} + p_{ L}^{k})\frac{h_{R}^{k} - h_{ L}^{k}} {L_{k}} \\ & & - \frac{\lambda _{k}\gamma } {4D_{k}A_{k}} \frac{(q_{R}^{k} + q_{L}^{k})\vert q_{R}^{k} + q_{L}^{k}\vert } {p_{R}^{k} + p_{L}^{k}} \quad \forall k \in [1,\ldots,n_{E}],{}\end{array}$$

(6b)

$$\displaystyle\begin{array}{rcl} 0& =& \sum _{l\in I_{L}^{i}}q_{R}^{\ell} -\sum _{ k\in I_{L}^{i}}q_{L}^{k} - d_{ i}(t)\quad \forall i \in \mathcal{N}_{0} \cup \mathcal{N}_{d},{}\end{array}$$

(6c)

$$\displaystyle\begin{array}{rcl} 0 = p_{i}(t) - s_{i}(t)\quad \forall i \in \mathcal{N}_{s}.& &{}\end{array}$$

(6d)

The vector q _R is the vector of fluxes at the end of the pipes, and the vector q _L is the vector of fluxes at the beginning of the pipes. Except for those at the beginning and end, we do not take any values along the pipes. This means, if the numerical error by this discretization exceeds our needs because the pipes are too long, we have to add artificial nodes (junctions) to the network such that all pipes are short enough to yield accurate enough results.

For a more compact description, we write the system in matrix notation

$$\displaystyle\begin{array}{rcl} \vert B_{S}^{T}\vert \partial _{ t}p_{s} + \vert B_{0}^{T}\vert \partial _{ t}p_{d}& =& -M_{L}^{-1}q_{ -},{}\end{array}$$

(7a)

$$\displaystyle\begin{array}{rcl} \partial q_{+}& =& M_{A}(B_{S}^{T}p_{ s} + B_{0}^{T}p_{ d}) + g(q_{+},p_{s},p_{d}),{}\end{array}$$

(7b)

$$\displaystyle\begin{array}{rcl} 0& =& B_{0}q_{+} + \vert B_{0}\vert q_{-}- d(t),{}\end{array}$$

(7c)

$$\displaystyle\begin{array}{rcl} 0& =& p_{s} - s(t),{}\end{array}$$

(7d)

where

$$\displaystyle\begin{array}{rcl} M_{L}& =& \mathrm{diag}(\ldots \frac{L_{k}A_{k}} {4\gamma } \ldots ),{}\end{array}$$

(8)

$$\displaystyle\begin{array}{rcl} M_{A}& =& \mathrm{diag}(\ldots -\frac{A_{k}} {L_{k}}\ldots ),{}\end{array}$$

(9)

and the k-th component of the function g is given by

$$\displaystyle\begin{array}{rcl} g_{k}(q_{+},\rho _{d},\rho _{s})& =& -\frac{A_{k}g} {2\gamma } \ell_{k}(p_{d},p_{s})\frac{h_{R}^{k} - h_{L}^{k}} {L_{k}} - \frac{\lambda _{k}\gamma } {4D_{k}A_{k}} \frac{(q_{+}^{k})\vert q_{+}^{k}\vert } {\ell_{k}(\rho _{d},\rho _{s})},{}\end{array}$$

(10)

where ℓ _k is the k-th entry of the vector-valued function ℓ

$$\displaystyle{\ell(p_{d},p_{s}) = \vert B_{0}^{T}\vert p_{ d} + \vert B_{S}^{T}\vert p_{ s}.}$$

Both matrices M _L and M _A are diagonal and invertible. The matrix

$$\displaystyle{B = \left [\begin{array}{*{10}c} B_{0} \\ B_{S} \end{array} \right ]}$$

denotes the incidence matrix of the underlying directed graph, where B ₀ corresponds to the demand nodes and junctions and B _S corresponds to the supply nodes. In addition, the notation $q_{-} = q_{R} - q_{L}$ and $q_{+} = q_{R} + q_{L}$ has been introduced here. To eliminate q ₋, we multiply (7a) by | B ₀ | M _L and then use (7c) to substitute | B ₀ | q ₋,

$$\displaystyle\begin{array}{rcl} & & \vert B_{S}^{T}\vert \partial _{ t}p_{s} + \vert B_{0}^{T}\vert \partial _{ t}p_{d} = -M_{L}^{-1}q_{ -} {}\\ \Rightarrow \quad & &\vert B_{0}\vert M_{L}\vert B_{S}^{T}\vert \partial _{ t}p_{s} + \vert B_{0}\vert M_{L}\vert B_{0}^{T}\vert \partial _{ t}p_{d} = -\vert B_{0}\vert q_{-} {}\\ \Rightarrow \quad & &\vert B_{0}\vert M_{L}\vert B_{S}^{T}\vert \partial _{ t}p_{s} + \vert B_{0}\vert M_{L}\vert B_{0}^{T}\vert \partial _{ t}p_{d} = B_{0}q_{+} - d(t). {}\\ \end{array}$$

We also replace p _s according to (7d) to obtain

$$\displaystyle\begin{array}{rcl} \vert B_{0}\vert \,M_{L}\,\vert B_{0}^{T}\vert \partial _{ t}p_{d}& =& B_{0}q_{+} - d(t) -\vert B_{0}\vert \,M_{L}\,\vert B_{S}^{T}\vert \partial _{ t}s(t),{}\end{array}$$

(11a)

$$\displaystyle\begin{array}{rcl} \partial _{t}q_{+}& =& M_{a}B_{0}^{T}p_{ d} + g(q_{+},s(t),p_{d}) + M_{a}B_{S}^{T}s(t){}\end{array}$$

(11b)

with g as in (10). The structure that (11) implies can be seen more clearly in block matrix notation

$$\displaystyle\begin{array}{rcl} \left [\begin{array}{*{10}c} \vert B_{0}\vert M_{L}\vert B_{0}^{T}\vert & 0 \\ 0 &M_{a}^{-1} \end{array} \right ]\left [\begin{array}{*{10}c} \partial _{t}p_{d} \\ \partial _{t}q_{+} \end{array} \right ]& =& \left [\begin{array}{*{10}c} 0 &B_{0} \\ B_{0}^{T}& 0 \end{array} \right ]\left [\begin{array}{*{10}c} p_{d} \\ q_{+} \end{array} \right ] + \left [\begin{array}{*{10}c} -d(t) -\vert B_{0}\vert M_{L}\vert B_{S}^{T}\vert \partial _{t}s \\ M_{a}^{-1}g + B_{S}^{T}s \end{array} \right ].{}\end{array}$$

(12)

Compare this derivation of an ordinary differential equation to the very similar approach of [4], where more details are conveyed. From now on we consider (12) of the size $\vert \mathcal{N}\vert -\vert \mathcal{N}_{s}\vert + n_{E}$ (the number of nodes minus the number of supply nodes plus the number of edges). It is an ordinary differential equation in descriptor form where the matrix E,

$$\displaystyle{E = \left [\begin{array}{*{10}c} \vert B_{0}\vert M_{L}\vert B_{0}^{T}\vert & 0 \\ 0 &M_{a}^{-1} \end{array} \right ],}$$

is positive definite and symmetric. Furthermore, the equation depends on several parameters given by pipe lengths L, diameters D, friction coefficients λ, height differences Δ h, and gas properties γ totaling 4 × n _E + 1-many parameters.

Remark 1.

We are now dealing with an ordinary differential equation of the form

$$\displaystyle\begin{array}{rcl} E\dot{x} = Tx + f(x,u) + Ku.& & {}\\ \end{array}$$

This means we have been able to decouple the system in such a way that it is no longer written in the form of a differential algebraic equation. During the process of reformulation, the time derivative of the input signal s, which is the pressure at the supply nodes, has been introduced. Since this pressure is usually given explicitly as a slowly changing function of time we can calculate its derivative in most practical applications.

2.2 Example Problems

In this chapter we are going to numerically analyze three example networks. The first consists in a single pipe, the second in a small connected network of 57 pipes, and the third in a larger network with a higher number of elements forming several connected components, the largest of which includes 669 pipes. Network topology is given by a graph which is mainly defined by a list of edges, i.e., ordered tuples of nodes indicating the direction of the edge. For simplicity, the total set of N _N  nodes is just described by their numbering, i.e., by a set of integers of the form $\left \{n \in \mathbb{N}:\, n \leq N_{N}\right \}$. The set of edges given as a list automatically implies a numbering of the edges which we later make use of to set up our equations. Length, height difference, width, and roughness are given as a parameter vector for each pipe. Furthermore, one or several demand fluxes are provided by functions of time. Similarly, one or several time-dependent supply pressures are given.

The topologies of the three networks are visualized in Figures 1, 2 and 3. Supply nodes are marked by triangles, and nodes with nonzero demand are marked by rectangles. Tables 1 and 4 show the corresponding parameter vectors.

Fig. 1

Network 1, a single pipe divided into subsections of different properties

Fig. 2

Network 2, a small network with several supply and demand notes

Fig. 3

Connected component of network 3, of larger scale

Table 1 Parameters for network 1

Table 2 Supply and demand for network 1

Table 3 Supply for network 2

Table 4 Parameters for network 2

Table 5 Demand for network 2

At the supply nodes a supply function of the following form is given

$$\displaystyle\begin{array}{rcl} s(t)& =& \alpha _{s} \times s(0) \times \left (0.5 \times \left (\cos \left ( \frac{\pi \times (t - T_{1}^{s})} {(T_{2}^{s} - T_{1}^{s})}\right ) - 1\right )\right ) + s(0),{}\end{array}$$

(13)

where α _s is the portion the supply pressure drops during the given time period T ₂ ^s − T ₁ ^s. Tables 2 and 3 show the supply pressures at time zero for all supply nodes. Similarly, the demand functions at nodes with nonzero demand are of the form

$$\displaystyle\begin{array}{rcl} d(t)& =& d(0) + 0.5 \times \alpha _{d} \times \left (1 -\cos \left ( \frac{\pi \times (t - T_{1}^{d})} {(T_{2}^{d} - T_{1}^{d})}\right )\right ) \times d(0),{}\end{array}$$

(14)

where α _d denotes the percentages the demand grows. The corresponding values of d(0), T ₁ ^d, and T ₂ ^d are listed in Tables 2 and 5 for all nodes with nonzero demand. This means that the first example, the single pipe, yields a system of ordinary differential equations of size 14 with 22 parameters, the second network is of size 110 with 29 parameters, and the last network’s largest subnet is of size 1341.

3 Stiffness in Ordinary Differential Equations

A simple idea in principle, stiffness can be conceived as the intuition that stability is more critical than accuracy or, much simpler, that explicit integration methods might fail. To put this into a mathematical framework can become rather difficult, though. As a means to analyze stability, we introduce concepts and definitions of stiffness in linear constant-coefficient ordinary differential equations in the following subsection as well as a discussion of practical implications for three example cases in subsequent subsections.

3.1 Concepts and Definitions

If a linear constant-coefficient ordinary differential equation is given as

$$\displaystyle{\dot{x} = Ax,}$$

stiffness is often quantified via a ratio of the minimum and maximum real part of the eigenvalues under the assumption that all eigenvalues of A be negative. Such a ratio is linked with the behavior of the differential equation for t → ∞ (and can be too liberal a condition). The Lipschitz constant of the linear function, which coincides with the largest singular value of A, gives another (too conservative) criterion of stiffness that is tied to the limit t → t ₀.

A more realistic measure of stiffness for linear systems is suggested by [7] in terms of a pseudo spectral analysis. We do not repeat details here. It is, however, important to realize that the two notions of stiffness differ more strongly from each other the further away A is from a normal matrix, where nonnormality can, e.g., be measured by

$$\displaystyle{\|A^{{\ast}}A - AA^{{\ast}}\|_{ F}.}$$

Here $\|\cdot \|_{F}$ denotes the Frobenius norm. As a consequence, both concepts of stiffness are appropriate for normal matrices. The matrices arising from the systems presented in the following are not normal, though, such that we need to expect different stiffness measures.

The whole issue of stiffness becomes even more complicated once we deal with nonlinear equations and source terms, which are present in the systems that we consider. Linear stiffness theory for constant-coefficient ordinary differential equations can be applied to a linearization of the nonlinear system: Via the Jacobian matrix we get a constant-coefficient linear equation that can be evaluated at a given time t ₀. However, information may get lost in the process of linearization. In the following we empirically evaluate and show the stiffness of the ordinary differential equation (12) for the single pipe and the small network example from Section 2.2.

3.2 Single Pipe System

The single pipe introduced in Section 2.2 comprises segments of varying properties and can hence be written as a system of ordinary differential equations of size 14.

In this first excursion in stiffness we are going to compute the common notions of stiffness that are given by the eigenvalues and the singular values of E ⁻¹ J _f (0, x ₀), where x ₀ denotes a stationary solution at time t = 0. This stationary solution can in principle be chosen arbitrarily and will serve as a starting value later. The Jacobian’s singular values and eigenvalues are plotted in Figure 4. Notice that these plots tend to look very similar for other values of t and x. The analysis of singular values and eigenvalues leads to a liberal stiffness estimate of 4 and a conservative estimate of 1. 6 × 10⁵. Because the difference between both estimates comprises several orders of magnitude we cannot conclude the extent of stiffness, hence the problem at hand might either become rather stiff or only mildly so.

Fig. 4

The eigenvalues and the singular values of the linearized system, network 1

By a simple numerical test we notice, though, that the step size of a regular solver for non-stiff problems (here MATLAB^®;’s ode15) is chosen much smaller than by the corresponding stiff solver (here MATLAB’s ode23s). This difference can be interpreted as a sign of more than only mild stiffness. The step sizes chosen by the different MATLAB solvers are shown in Figure 5, where we can observe a difference of two orders of magnitude for this simple example. Even more important, we must expect that we deal with serious stiffness in this class of gas transportation problems due to the fact that, in spite of those small step sizes, the solution found by MATLAB’s non-stiff ode15 blows up in finite time whereas the solution given by ode23s does not.

Fig. 5

The time steps chosen by MATLAB’s ode23 and ode15s solvers for ordinary differential equations, network 1

3.3 Small Networks

For a network of pipes the stiffness of the system becomes clearer yet. Looking at the eigenvalue and singular value plot of the Jacobian matrix, which is shown in Figure 6, we again see that the stiffness estimates vary strongly by several orders of magnitude, this time between 16 and 1. 1 × 10⁶. As above this result eludes an exact stiffness analysis of the system of equations. Since both estimates grow higher than in the previous example, stiffness can most probably be assumed to increase with the complexity and size of the network. Conducting the same experiment as before, we compare the resulting MATLAB step sizes as in Section 3.2. We do not include a plot as it shows the same peculiarities as Figure 5, only that the time step of the non-stiff method decreases even more, oscillates around 10⁻³ s and therefore differs by four orders of magnitude from the stiff solver.

Fig. 6

The eigenvalues and singular values of the linearized system, network 2

Regarding the first six seconds, the solutions computed via the two different solvers are depicted in Figure 7. We can notice again that these systems seem to require a stiff or, possibly even better, a dedicated solver.

Fig. 7

The time steps chosen by MATLAB’s ode23 and ode15s solvers for ordinary differential equations, network 2

4 Model Order Reduction

Seeing that these network problems can become arbitrarily large and stiff, we would be interested in creating a reduced order model which is of small order and hopefully not stiffer than the full system. Since the system is nonlinear, we apply the model order reduction method called proper orthogonal decomposition as this is typically the method of choice for nonlinear systems.

4.1 Proper Orthogonal Decomposition

The model order reduction method called proper orthogonal decomposition (POD) starts with multiple snapshots $\{y_{j}^{k}\}_{j=1}^{m} \subset X$, 1 ≤ k ≤ p, for a given Hilbert space X (typically $\mathbb{R}^{n}$ or a function space like $\mathcal{L}^{2}$). One is interested in finding a subspace spanned by an orthonormal basis $\psi _{1},\ldots,\psi _{\ell}$ within the Hilbert space X that solves the minimization problem

$$\displaystyle\begin{array}{rcl} & & \min \sum _{k=1}^{p}\sum _{ j=1}^{m}\alpha _{ j}\left \|y_{j}^{k} -\sum _{ i=1}^{\ell}\langle y_{ j}^{k},\psi _{ i}\rangle _{X}\psi _{i}\right \|_{X}^{2} \\ & & \qquad \mbox{ s. t. }\{\psi _{i}\}_{i=1}^{\ell} \subset X\mbox{ and }\langle \psi _{ i},\psi _{j}\rangle _{X} =\delta _{ij},\;1 \leq i,j \leq \ell.{}\end{array}$$

(15)

This minimization can also be written as a maximization problem due to the orthogonal nature of the elements ψ _i

$$\displaystyle\begin{array}{rcl} & & \max \sum _{k=1}^{p}\sum _{ j=1}^{m}\alpha _{ j}\sum _{i=1}^{\ell}\langle y_{ j}^{k},\psi _{ i}\rangle _{X}^{2} \\ & & \qquad \mbox{ s. t. }\{\psi _{i}\}_{i=1}^{\ell} \subset X\mbox{ and }\langle \psi _{ i},\psi _{j}\rangle _{X} =\delta _{ij},\;1 \leq i,j \leq \ell.{}\end{array}$$

(16)

Theorem 1.

Let X be a separable Hilbert space, $\mathcal{R}: X \rightarrow X$ a summation operator on X defined by

$$\displaystyle{\mathcal{R}: X \rightarrow X,\quad \mathcal{R}\psi \mapsto \sum _{k=1}^{p}\sum _{ j=1}^{m}\alpha _{ j}\langle \psi,y_{j}^{k}\rangle _{ X}y_{j}^{k}.}$$

The following assertions are all true:

• (a) $\mathcal{R}$ is linear compact self-adjoint and nonnegative.

• (b) A basis of X of eigenfunctions ψ _j exists such that

  $$\displaystyle{\mathcal{R}\psi _{j} =\lambda _{j}\psi _{j}}$$

  and $\lambda _{1} \geq \lambda _{2} \geq \ldots \geq \lambda _{d} >\lambda _{d+1} =\ldots = 0$.

• (c) The first ℓ of these eigenfunctions solve the minimization problem  (15) and the maximization problem  (16).

For a proof of Theorem 1 see [13].

In the remainder of this chapter, let us assume that $X = \mathbb{R}^{n}$ and the inner product is defined by $\langle x,y\rangle _{X} = x^{T}Ey$ for a given positive definite symmetric matrix E. We will denote by Y _k the matrix of snapshots {y _j ^k} _j = 1 ^m. This means Y is an n × m matrix.

Corollary 1.

The eigenvectors of the operator  $\mathcal{R}$ equate to the eigenvectors of the matrix

$$\displaystyle\begin{array}{rcl} \left (Y _{1}DY _{1}^{T} + \cdots + Y _{ p}DY _{P}^{T}\right )E,& &{}\end{array}$$

(17)

where $D = \text{diag}(\alpha _{1},\cdots \,,\alpha _{n})$.

So in order to find the best approximation space of size ℓ for a given set of snapshots, all we have to do is compute the first ℓ eigenvectors of (17). Notice that the matrix (17) is an n × n matrix, the size of the state space X. This matrix is not symmetric. If we, however, knew the eigenvalues and eigenvectors of the following symmetric system

$$\displaystyle{ E^{1/2}\left (Y _{ 1}DY _{1}^{T} + \cdots + Y _{ p}DY _{P}^{T}\right )E^{1/2}, }$$

(18)

we could compute the eigenvectors of (17). In fact, these eigenvectors are obtained if we multiply the eigenvectors of (18) by $E^{-1/2}$. Since E is usually a large matrix and its square root is hard to compute, we are going to describe a faster alternative. The matrix (18) can be written as $\hat{Y }\hat{Y }^{T}$ for

$$\displaystyle{\hat{Y }= \left [\begin{array}{*{10}c} \hat{Y } _{1} & \hat{Y } _{2} & \mathop{\ldots }& \hat{Y } _{p} \end{array} \right ],}$$

where $\hat{Y }_{i} = E^{1/2}Y _{i}D^{1/2}$. Since this matrix is symmetric and positive definite its eigenvalue and singular value decompositions are equivalent. Assuming we know the singular value decomposition of $\hat{Y }$,

$$\displaystyle{ \hat{Y }= USV ^{T}, }$$

(19)

we also know the singular value decomposition of $\hat{Y }\hat{Y }^{T} = US^{2}U^{T}$ and the singular value decomposition of $\hat{Y } ^{T}\hat{Y }= V S^{2}V ^{T}$. This means, if we compute V we can recover U by (19), with $U = \hat{Y } S^{-1}V$. The matrix U is the matrix of singular vectors or eigenvectors of $\hat{Y }\hat{Y }^{T}$ (recall that $\hat{Y }\hat{Y } ^{T}$ equals (18)). Hence, we get the eigenvector matrix of (17) by $E^{-1/2}U = E^{-1/2}\hat{Y } S^{-1}V$. If $\phi _{1},\ldots,\phi _{\ell}$ are the singular vectors of $\hat{Y }\hat{Y }^{T}$ we can, consequently, compute the eigenvectors ψ _i ,

$$\displaystyle{\psi _{i} = \frac{1} {\sqrt{\sigma _{i}}}\left [\begin{array}{*{10}c} Y _{1}D^{1/2},&Y _{2}D^{1/2},&\ldots &Y _{p}D^{1/2} \end{array} \right ]\phi _{i},}$$

where σ _i and ϕ _i are the singular values and singular vectors of $\hat{Y }^{T}\hat{Y }$. The objective function is then given by

$$\displaystyle\begin{array}{rcl} & & \sum _{k=1}^{p}\sum _{ j=1}^{m}\alpha _{ j}\left \|y_{j}^{k} -\sum _{ i=1}^{\ell}\langle y_{ j}^{k},\psi _{ i}\rangle _{X}\psi _{i}\right \|_{X}^{2} {}\\ & & \qquad \qquad =\sum _{ k=1}^{p}\sum _{ j=1}^{m}\alpha _{ j}\left (\|y_{j}^{k}\|_{ X}^{2} - 2\langle y_{ j}^{k},\sum _{ i=1}^{\ell}\langle y_{ j}^{k},\psi _{ i}\rangle _{X}\psi _{i}\rangle +\|\sum _{ i=1}^{\ell}\langle y_{ j}^{k},\psi _{ i}\rangle _{X}\psi _{i}\|_{X}^{2}\right ) {}\\ & & \qquad \qquad =\sum _{ k=1}^{p}\sum _{ j=1}^{m}\alpha _{ j}\left (\|y_{j}^{k}\|_{ X}^{2} -\sum _{ i=1}^{\ell}\langle y_{ j}^{k},\psi _{ i}\rangle _{X}^{2}\right ) {}\\ & & \qquad \qquad =\sum _{ i=1}^{n}\sigma _{ i} -\sum _{i=1}^{\ell}\sigma _{ i} =\sum _{i>\ell}\sigma _{i}. {}\\ \end{array}$$

which follows from the fact that ψ _i are eigenfunctions of the operator $\mathcal{R}$ [13]. Not to mention, this result can be utilized to determine ℓ, i.e., to decide where to cut off eigenvalue computations. In practical applications, a heuristic choice for ℓ can, e.g., be implied by the requirement that $\mathcal{E}\geq 99\,\%$ where

$$\displaystyle\begin{array}{rcl} \mathcal{E} = \frac{\sum _{i=1}^{\ell}\sigma _{i}} {\sum _{i=1}^{n}\sigma _{i}} = \frac{\sum _{i=1}^{\ell}\sigma _{i}} {\sum _{k=1}^{p}\sum _{j=1}^{m}\alpha _{j}\|y_{j}^{k}\|_{X}^{2}}.& &{}\end{array}$$

(20)

We now need to understand how to use the described subspace of X in order to create a reduced order model of a dynamical system given in the form

$$\displaystyle{E\dot{x} = Tx + f(x,u) + Ku,}$$

where the function f depends on the dynamic variable x and the time-dependent input function u. We are now going to briefly address the matter that the system matrices E, T, K, and the function f additionally depend on parameters. The basic idea is to generate snapshots for certain sampled parameter values. This parameter sampling can be picked as a uniform grid. An alternative way to set up a sampling in a semi-optimized way by using a Greedy algorithm is, e.g., described by [5].

In fact, (15) can be seen as the discrete version of a continuous minimization problem. Seen in this light, the objective function would read

$$\displaystyle{\sum _{k=1}^{p}\int _{ 0}^{T}\left \|y^{k}(t) -\sum _{ i=1}^{\ell}\langle y^{k}(t),\psi _{ i}\rangle _{X}\psi _{i}\right \|_{X}^{2},}$$

which, in turn, implies the minimization problem (15) by using a quadrature rule to compute the integral. A classical choice of α _i are trapezoidal weights and the inner product is typically given by $\langle x,y\rangle = x^{T}Ey$ with the inner product matrix denoted by E. This allows us to compute $\psi _{1},\ldots,\psi _{\ell}$ by the methods discussed above and summarized in Algorithm 1. We then determine the matrix W as $W = [\psi _{1},\ldots,\psi _{\ell}]$ and project the large scale system by Galerkin projection onto

$$\displaystyle\begin{array}{rcl} W^{T}EW\dot{\hat{x}} = W^{T}TWx + W^{T}f(W\hat{x},u) + W^{T}Ku,& &{}\end{array}$$

(21)

where W ^T EW = I by the mutual orthogonality of ψ _i with respect to said inner product.

Algorithm 1 POD

4.2 Nonlinearity and Problem Structure

In the following, we are going to describe the rest of the algorithm that is used in the numerical experiments of Section 5. There are mainly two questions left to be answered carefully which were not mentioned in the theoretical derivation of POD.

• 1. Do we need to consider the special structure of the problem when we set up the reduced order model? Pressures and fluxes are not necessarily of a similar magnitude such that a direct application of the POD matrix as in (21) might neglect important effects [8]. We therefore reduce the pressure and the flux vector separately.

• 2. How do we handle the nonlinearity of the function? The term $W^{T}\!f(W\hat{x})$ contributes ℓ-dimensional function values with an ℓ-dimensional vector-valued argument. However, a higher-dimensional vector must be evaluated to compute W ^T​f. To obtain a fast simulation, this evaluation needs to be avoided.

Let us first discuss implications of the special structure of our problem. For the convenience of the reader, the ordinary differential equation (12) is repeated here:

$$\displaystyle\begin{array}{rcl} \left [\begin{array}{*{10}c} \vert B_{0}\vert M_{L}\vert B_{0}^{T}\vert & 0 \\ 0 &M_{a}^{-1} \end{array} \right ]\left [\begin{array}{*{10}c} \partial _{t}p_{d} \\ \partial _{t}q_{+} \end{array} \right ]& =& \left [\begin{array}{*{10}c} 0 &B_{0} \\ B_{0}^{T}& 0 \end{array} \right ]\left [\begin{array}{*{10}c} p_{d} \\ q_{+} \end{array} \right ] + \left [\begin{array}{*{10}c} -d(t) -\vert B_{0}\vert M_{L}\vert B_{S}^{T}\vert \partial _{t}s \\ g(q,p,s) + B_{S}^{T}s \end{array} \right ].{}\\ \end{array}$$

For given input functions s(t), d(t), and given parameters, we solve this differential equation within the time interval [0, T] in time steps of size Δ t > 0. This means we obtain pressure values $p(0),p(\varDelta t),\ldots,p(T)$ and flux values $q(0),q(\varDelta t),\ldots,q(T)$, representing snapshots that we assemble into matrices

$$\displaystyle{ Y _{i}^{p}\mbox{ (pressures) and }Y _{ i}^{q}\mbox{ (fluxes)}, }$$

(22)

where i indicates the snapshots of different given parameter values. They are used to calculate projection matrices W _p and W _q separately for pressures and fluxes by Algorithm 1, such that the reduced order system obtained via Galerkin projection of the full order ordinary differential equation onto the matrix

$$\displaystyle{\left [\begin{array}{*{10}c} W_{p}& 0 \\ 0 &W_{q} \end{array} \right ]}$$

reads

$$\displaystyle\begin{array}{rcl} \left [\begin{array}{*{10}c} W_{p}^{T}\vert B_{0}\vert M_{L}\vert B_{0}^{T}\vert W_{p}& 0 \\ 0 &W_{q}^{T}M_{a}^{-1}W_{q} \end{array} \right ]\left [\begin{array}{*{10}c} \partial _{t}p_{d} \\ \partial _{t}q_{+} \end{array} \right ]& =& \\ \left [\begin{array}{*{10}c} 0 &W_{p}^{T}B_{0}W_{q} \\ W_{a}^{T}B_{0}^{T}W_{p}& 0 \end{array} \right ]\left [\begin{array}{*{10}c} p_{d} \\ q_{+} \end{array} \right ]& +& \left [\begin{array}{*{10}c} -W_{p}^{T}d(t) - W_{p}^{T}\vert B_{0}\vert M_{L}\vert B_{S}^{T}\vert \partial _{t}s \\ W_{q}^{T}f(W_{p}p,W_{q}q,s) + W_{p}^{T}B_{S}^{T}s \end{array} \right ].{}\end{array}$$

(23)

Since all involved matrices can be precomputed, the only issue left is the computation of the nonlinear term W _q f(W _p p, W _q q, s). So as to approximate this nonlinear term by a function which no longer requires any higher order operation, the discrete empirical interpolation method (DEIM in short, see [2]) is employed. If we precompute a snapshot matrix F that consists of function evaluations of f at a number of given values of p and q, matrices P and U can be computed via Algorithm 2, such that the resulting reduced (i.e., approximate) nonlinear function evaluation amounts to

$$\displaystyle{W_{q}^{T}f(W_{ p}p,W_{q}q,s) = W_{q}^{T}U(P^{T}U)^{-1}P^{T}f(W_{ p}p,W_{q}q,s).}$$

We immediately see that the matrix W _q ^T U(P ^T U)⁻¹ is of size r ₁ × m, where m is the reduction order for DEIM and r ₁ the reduction order for the flux component in POD. The function P ^T f(W _p p, W _q q, s) is truly a function of order m since the matrix P is a matrix of zeros and ones, where exactly m entries of f are picked. Owing to the structure of the function f, namely the k-th entry only depending on the k-th entry of W _q q and B ₀ ^T W _p p + B _S ^T s, this computation is straightforward.

Algorithm 2 DEIM

5 Numerical Examples

The purpose of the following section is to experimentally show the extent of reduction of the system we can achieve for our three network models (Section 2.2), while still being able to reproduce the general dynamical behavior of the gas within the network.

5.1 The Single Pipe

Our first example is one of the most trivial networks possible and serves as proof of concept. To begin with, a single solution trajectory, which we again call a snapshot, is calculated for the parameters given in Section 2.2. Its singular values are shown in the top panel of Figure 8. By the methods explained in Section 4.2, the snapshot is used to set up a reduced order model. In short, this means we can determine projection matrices W ₁ and W ₂ via POD as well as projection and picking matrices U and P via DEIM. The resulting reduced order model parametrically depends on length, diameter, and friction coefficient of each pipe segment as well as on the field γ that characterizes properties of the gas flowing through it. In order to better understand the behavior of the system for different choices of these parameters, we make use of a Latin hypercube sampling of size 10, where we vary all 22 parameters in a cube of ± 5 % of the original parameter set. In this particular test, the order of the reduced model is 4, which results from the choice $r_{1} = r_{2} = m = 2$. For the different test networks, which only differ by the said parameter values, we compute the reduced order model as well as, for reference, the full model and compute the relative error in the pressure and the absolute error in the flux, displaying the respective maximal error in Table 6. Furthermore, the relative error at a distance from t = 0 is also given as the maximal difference over all pressure and flux components. We also display the error of the reduced order system compared to the full system of the original parameter distribution. This shows that, when we vary the parameters, we still stay within the same order of magnitude of the error.

Table 6 Numerical error, network 1

Figure 8 emphasizes this result. Here we see that the singular value decay in the flux looks similar, whether we have one time series or several time series for several parameters. The difference becomes noticeable in the left column that refers to pressure. However, in both cases the third singular value, after which DEIM cuts off the series of singular values, is of order 10⁻⁸.

Fig. 8

The singular values for one time series as well as for 10 time series, each the result of a different parameter set. The values that are shown along the y-axis are ordered decreasing in size, along the x-axis

Of course, the input and output functions of this problem are not varied. And due to the nature of the problem we cannot expect to find a reduced system of small order representing all possible input and output functions. The difficulty consists in that the partial differential equation describing the physics in the pipe, the isothermal Euler equation, is a transport dominated partial differential equation. Thus shocks might travel through the system and we can, therefore, not expect the solution to lie in a low-dimensional subspace.

The following numerical experiment, however, shows that, if we assume the supply pressures and demand nodes only vary within a certain range of given values, we are able to still use the reduced system. We are now going to repeat the comparison of the full and reduced simulation. Again, we pick 10 simulations, varying the percentage the supply pressure and the demand flux change over time within ± 10 %. Remember the reduced order was created with these values all varying by 2 % only. The relative error plot, where the maximum is taken over all 10 scenarios, is displayed in Figure 9.

Fig. 9

The maximal relative error over the 10 sampled scenarios

5.2 Network of 57 Pipes

Having a manageable size but realistic structure, the following example supports the idea that model order reduction already helps to reduce simulation time and stability of the simulation for networks of smaller scale. We test parameter variations as well as changes of the input function receiving robust and accurate results. The system is first solved for the parameters and input function given in Section 2.2, T = 1 × 10⁶ s ≈ 280 h. We store 100 time steps for a system size of 110, of which 54 dimensions refer to pressure and 56 to flux. By and large, we gather a snapshot matrix of dimension 100 × 110 in this fashion. The singular value decay of YEY ^T is illustrated in the top panel of Figure 10, where the singular values are displayed for the fluxes and the pressures independently again. On the subject of the criteria given in (20), we can conclude that a reduced order of size 1 for pressures and of size 1 for fluxes is sufficient to obtain a “good” approximation in that case with $\mathcal{E}\geq 0.99999$ for the pressures as well as for the fluxes. We, however, select $r_{1} = r_{2} = 3$. Typically, the reduction order for DEIM has to equal at least this reduced order (3 in our case). It turns out that this minimum choice is enough for the example at hand, see the error values listed in Table 7. In fact, $r_{1} = 3,r_{2} = 3,m = 3$ yield a reasonably accurate reduced order system.

Table 7 Numerical error, network 2

Fig. 10

Singular values of the snapshot matrices

The projection matrices are applied to create a parametric reduced order model. The parameter space of this parametrized model possesses a dimension of size 29. We allow this parameter vector to vary in a box around ± 5 % of its given values again. We pick 10 values in that box by Latin hypercube sampling to obtain 10 scenarios. For each scenario we compute the reduced solution and the full solution. We realize here that in order to run MATLAB’s ode solver ode15s we need to have a very accurate starting value for the full model. Therefore, we take the original initial value and compute a truly stationary solution by Newton’s method to be used as initial value. For the reduced order system this step is not necessary, which in turn means that the solution of the full order system becomes even slower in comparison. However, this procedure also implies that the solutions near the initial time are not as close to each other as later because they do not start from the same initial value. We thus compare the maximal relative error only after the first 1000 s have already passed. This error is shown in Table 7. We, furthermore, compare the timings, for the solution of the reduced system and for the solution of the full system, where the identification of a starting value is included as well as the simulation time itself.

With regard to the full solution of the 10 scenarios from above, creating a snapshot matrix as in Section 4.1, we can compute the singular values that are plotted in the middle panel of Figure 10. The singular values show the size of a linear subspace to be used in order to create a good approximation of the space in which the solutions lie.

Furthermore, we have conducted some test with varying input functions. As in the case of the single pipe, we vary the percentages the demand and supply values change during the simulated time in a box of ± 10 %. We can match the general behavior even though the errors between the full and the reduced system can be large. However, measurements often differ from the computed solution even stronger than our reduced model, see, e.g., [1]. We, furthermore, display the singular value decay for the snapshot matrix created by 10 such scenarios (last panel of Figure 10).

5.3 Network of 669 Pipes

A system of 669 elements is rather large such that computations of a single time series can already take from several hours up to weeks with standard solvers (it is possible to accelerate the implementation, though). The goal here is to show that we can predict the behavior of the system with the model order reduction method as described above up to a certain extent. We only compute the solution of this large system for the first 100 s. From the results of this computation we calculate the projection matrix W as well as the DEIM matrices P and U with reduction order $r_{1} = 4,r_{2} = 2,m = 4$. These matrices are needed to set up the reduced system. We then run the reduced system for different values of d(0), which are a random perturbation of the original d(0). We cannot compare the reduced time series to the time series of the full system, as the latter is too expensive to compute. Since we run the reduced system in time until it should arrive at a new stationary solution, we can assess the extent of “stationarity” of our result from the right-hand side of the system. In Table 8 we compare the value of the right-hand side of the reduced system to the value of the right-hand side of the full system at the state we arrived at following the trajectory of the reduced system. Even though these values are not numerically zero, they are reputably closer to zero than if we evaluated the right-hand side at the initial configuration. Compared to the initial configuration, these values are hence better starting values to use a Newton-type method to find a truly stationary solution.

Table 8 Value of the right-hand side, network 3

The simulation time for simulating those reduced order systems amounts to approximately 25 s. If we use the end value obtained from the reduced simulation and apply a Newton method to find a stationary solution such that | f(x _S ) | ≤ 10⁻³, the Newton method takes around 10 to 100 s. Whereas, if we use x ₀ to start our Newton method, it takes about 10, 000 s. So in the presented case, the reduced method can certainly help to speed up the computation of a feasible stationary solution.

6 Conclusions

For gas transportation problems through networks of pipelines, from supplier to consumer, the underlying continuum mechanics, practical simplifications, and a numerical model have been compiled and explained to the reader. Notably, a state-of-the-art transformation of the resulting discretized differential algebraic system of equations to a system of ordinary differential equations has been presented. Among the properties of this system, stiffness has been spotlighted since it affects the choice of suitable numerical solvers strongly. Empirical evidence is shown that stiffness plays an important role and that it even grows with the complexity of the systems.

With the goal of exhaustive studies of varying input and output in mind, we indicate how to apply model order reduction methods for nonlinear systems efficiently, making use of POD with DEIM. Special attention is given to the preservation of the general form of the underlying ordinary differential equation lest pressure and flux values may be mixed. A parameter domain is defined by varying network properties within a limited range to indicate uncertainty. The domain is used to obtain empirical results that illustrate possible gain in simulation speed by order reduction, while the induced loss in accuracy is discussed.

The numerical behavior of three networks of different complexity is examined in this light. Results indicate that a speed-up of 10 to 1000 can be achieved, where we have to anticipate certain inaccuracy within the obtained solutions. In some cases inaccuracy can be of an order of magnitude such as 10 % of the typical solution values. The stiffness of the reduced system has been monitored and not found to be increased by the applied model order reduction technique.

One of the most obvious extensions to the case presented here can be found in the treatment of more types of network elements, as well as in the inclusion of more involved temperature effects. From a numerical point of view, the development of dedicated solvers would probably be interesting.