Two Ways to Treat Time in Reduced Basis Methods

Abstract

In this chapter, we compare two ways to treat the time within reduced basis methods (RBMs) for parabolic problems: Time-stepping and space-time variational based methods. We briefly recall both concepts and review well-posedness, error control and model reduction in both cases as well as the numerical realization. In particular, we highlight the conceptual differences of the two approaches.

We provide numerical investigations focussing on the performance of the RBM in both variants regarding approximation quality, efficiency and reliability of the error estimator. Pro’s and Con’s of both approaches are discussed.

1.1 Introduction

Parametrized partial differential equations (PPDEs) often occur in industrial or financial applications. If simulations are required for many different values of the involved parameters (“multi-query”), fine discretizations that are needed for a good approximation may resolve in high dimensional systems and thus in (for many applications too) long computation times. The reduced basis method (RBM) is by now a well-known model reduction technique, which allows one to efficiently reduce the numerical effort for many PPDEs by precomputing a reduced basis in an offline phase (using a detailed model, sometimes called “truth”) and evaluating the reduced model (for new parameter values) highly efficient in the online phase.

Here, we focus on time-dependent problems of parabolic type in variational formulation and describe two different approaches. The maybe more standard one is based upon a time-stepping scheme in the offline phase. The reduced basis is then usually formed by the POD-Greedy method [3, 5], which results in a reduced time-stepping system for the offline phase. The second approach that we wish to discuss, is based upon the space-time variational formulation of the parabolic problem, in which the time is taken as an additional variable for the variational formulation. This results in a Petrov-Galerkin problem in d + 1 dimensions (if d denotes the spatial dimension). The reduced basis is then formed by a standard Greedy approach resulting in a reduced space-time Petrov-Galerkin method [13, 14].

The aim of this paper is to provide a comparison of these two methods in order to identify similarities and conceptual differences of the two approaches. It complements and completes a recent similar comparison in [2] for discrete instationary problems.

The remainder of this chapter is organized as follows. We start in Sect. 1.2 by reviewing both variational formulations of parabolic PDEs. A brief survey of the RBM is contained in Sect. 1.3. Section 1.4 is devoted to the description of the POD-Greedy/time-stepping method for the RBM, whereas Sect. 1.5 contains the space-time RBM. Our numerical experiments as well as the comparisons are presented in Sect. 1.6. We finish with some conclusions in Sect. 1.7.

1.2 Variational Formulations of Parabolic Problems

Let V ↪ H be separable Hilbert spaces with continuous and dense embedding. The inner products and induced norms are denoted by (⋅ , ⋅ ) _H , (⋅ , ⋅ ) _V and ∥⋅ ∥ _H , ∥⋅ ∥ _V , respectively. We identify H with its dual yielding a Gelfand triple V ↪ H ↪ V ^′.

Let 0 < T < ∞ be the final time, I: = (0, T) the time interval and $\varOmega \subset \mathbb{R}^{d}$ an open spatial domain. We consider a linear, bounded operator $A \in \mathcal{L}(V,V ^{{\prime}})$ induced by a bilinear form $a(\cdot,\cdot ): V \times V \rightarrow \mathbb{R}$ as $\langle A\phi,\psi \rangle _{V ^{{\prime}}\times V } = a(\phi,\psi )$.¹ We require the bilinear form to satisfy the following properties

$$\displaystyle\begin{array}{rcl} \begin{array}{rclrcl} \vert a(\phi,\psi )\vert & \leq M_{a}\|\phi \|_{V }\|\psi \|_{V },\quad \phi,\psi \in V &&(\text{boundedness})\end{array} & &{}\end{array}$$

(1.1a)

$$\displaystyle\begin{array}{rcl} \begin{array}{rclrcl} a(\phi,\phi ) + \lambda _{a}\|\phi \|_{H}^{2} & \geq \alpha _{a}\|\phi \|_{V }^{2},\qquad \qquad \phi \in V &&(\mbox{G$\mathring{\mathrm{a}}$} \text{rding inequality})\end{array} & &{}\end{array}$$

(1.1b)

with constants M _a < ∞, α _a > 0, λ _a ≥ 0. Then, we consider the parabolic initial value problem of finding u(t) ∈ V, t ∈ I a.e., such that

$$\displaystyle{ \dot{u}(t) + Au(t) = g(t),\,\text{ in }V ^{{\prime}},\quad u(0) = u_{ 0}\text{ in }H, }$$

(1.2)

where g ∈ L ₂(I; V ^′) and u ₀ ∈ H are given.

1.2.1 Semi-variational Formulation

The maybe more standard approach consists of multiplying (1.2) with a test function ϕ ∈ V and form the inner product in H (i.e., in space only). This leads to an evolution problem in V ^′, i.e.,

$$\displaystyle{ \text{find }u(t) \in V:\,\, (\dot{u}(t),\phi )_{H} + a(u(t),\phi ) = (g(t),\phi )_{H},\quad \phi \in V,\,t \in I\text{ a.e.} }$$

(1.3)

It is well-known that (1.3) is well-posed thanks to (1.1), see e.g. [15, Theorem 26.1]. Since the variational formulation is w.r.t. space only, we call it semi-variational.

1.2.2 Space-Time Variational Formulation

We now follow [12] for the description of a variational formulation of (1.2) w.r.t. space and time. This approach leads to a variational problem with different trial and test spaces $\mathbb{X}$ and $\mathbb{Y}$, both being Bochner spaces, namely

$$\displaystyle\begin{array}{rcl} \begin{array}{rclrcl} \mathbb{X}&:=&L_{2}(I;V ) \cap H^{1}(I;V ^{{\prime}}) =\{ v \in L_{2}(I;V ):\, v,\dot{v} \in L_{2}(I;V ^{{\prime}})\},&\mathbb{Y}&:=&L_{2}(I;V ) \times H,\end{array}& & {}\\ \end{array}$$

with norms $\|w\|_{\mathbb{X}}^{2}:=\| w\|_{L_{2}(I;V )}^{2} +\|\dot{ w}\|_{L_{2}(I;V ^{{\prime}})}^{2}$, $w \in \mathbb{X}$, and $\|v\|_{\mathbb{Y}}^{2}:=\| v_{1}\|_{L_{2}(I;V )}^{2} +\| v_{2}\|_{H}^{2}$, $v = (v_{1},v_{2}) \in \mathbb{Y}$. Since $\mathbb{X}\hookrightarrow C(I;H)$, see, e.g. [15, Theorem 25.5], u(0) ∈ H is well-defined for $u \in \mathbb{X}$.

The space-time variational formulation arises by multiplying (1.2) with test functions $v \in \mathbb{Y}$ and integrating w.r.t. time and space. This yields the linear operator $B \in \mathcal{L}(\mathbb{X}, \mathbb{Y}^{{\prime}})$ defined as $\langle Bu,v\rangle _{\mathbb{Y}^{{\prime}}\times \mathbb{Y}} = b(u,v)$ by (we omit the dependency on t in the integrands in the sequel)

$$\displaystyle{ b(u,v):=\int _{I}\langle \dot{u} + Au,v_{1}\rangle _{V ^{{\prime}}\times V }dt + (u(0),v_{2})_{H},\quad u \in \mathbb{X},v = (v_{1},v_{2}) \in \mathbb{Y}, }$$

i.e., $b(\cdot,\cdot ): \mathbb{X} \times \mathbb{Y} \rightarrow \mathbb{R}$ and the right-hand side $f \in \mathbb{Y}^{{\prime}}$ is defined by

$$\displaystyle{ \langle \,f,v\rangle _{\mathbb{Y}^{{\prime}}\times \mathbb{Y}}:=\int _{I}\langle g,v_{1}\rangle _{V ^{{\prime}}\times V }dt + (u_{0},v_{2})_{H},\quad v = (v_{1},v_{2}) \in \mathbb{Y}. }$$

Then, the space-time variational formulation of (1.2) reads

$$\displaystyle{ \text{find }u \in \mathbb{X}:\,\,\langle Bu,v\rangle _{\mathbb{Y}^{{\prime}}\times \mathbb{Y}} =\langle \, f,v\rangle _{\mathbb{Y}^{{\prime}}\times \mathbb{Y}},\quad \forall \ v \in \mathbb{Y}. }$$

(1.4)

Again, (1.1) yields well-posedness, e.g. [12, Theorem 5.1]. In fact, the operator B is boundedly invertible. The injectivity of the operator B is equivalent to

$$\displaystyle{ \beta _{b}:=\inf _{w\in \mathbb{X}}\sup _{v\in \mathbb{Y}} \frac{\vert b(w,v)\vert } {\|w\|_{\mathbb{X}}\,\|v\|_{\mathbb{Y}}}> 0,\quad (\text{inf-sup condition}). }$$

(1.5)

1.3 Parametrized Problems and the RBM

We introduce a general notation here, which will then be specified for both variational formulations. Let $\mathcal{X},\mathcal{Y}$ be Hilbert spaces, $\mu \in \mathcal{P}\subset \mathbb{R}^{P}$ a parameter and consider parametric forms $c: \mathcal{X}\times \mathcal{Y}\times \mathcal{P}\rightarrow \mathbb{R}$ as well as $h: \mathcal{Y}\times \mathcal{P}\rightarrow \mathbb{R}$. Then, the parameterized Petrov-Galerkin problem reads

$$\displaystyle{ \text{find }u(\mu ) \in \mathcal{X}:\,\, c(u(\mu ),v;\mu ) = h(v;\mu )\quad \forall \ v \in \mathcal{Y}. }$$

(1.6)

This framework obviously also includes the elliptic case, where $\mathcal{Y} = \mathcal{X}$. We briefly review the main ingredients of the RBM and refer to [6, 11] for recent surveys.

It is always assumed that a detailed discretization is available in the following sense: Let $\mathcal{X}^{\mathcal{N}}\subset \mathcal{X}$ and $\mathcal{Y}^{\mathcal{N}}\subset \mathcal{Y}$ be subspaces of finite, but large, dimension $\mathcal{N}$. The detailed problem (sometimes called “truth”) then reads

$$\displaystyle{ \text{find }u^{\mathcal{N}}(\mu ) \in \mathcal{X}^{\mathcal{N}}:\,\, c(u^{\mathcal{N}}(\mu ),v^{\mathcal{N}};\mu ) = h(v^{\mathcal{N}};\mu )\quad \forall \ v^{\mathcal{N}}\in \mathcal{Y}^{\mathcal{N}}. }$$

(1.7)

The “truth” solution $u^{\mathcal{N}}(\mu )$ is always assumed to be sufficiently close to u(μ). For well-posedness and stability of (1.7), a uniform inf-sup condition is required, e.g.  [9].

The next step is the computation of a reduced basis formed by “snapshots” $\xi ^{i}:= u^{\mathcal{N}}(\mu ^{i})$, $1 \leq i \leq N \ll \mathcal{N}$, where the snapshot parameters $\mu ^{i} \in \mathcal{P}$ are e.g. determined by a Greedy procedure w.r.t. an efficiently computable error estimate Δ _N (μ). The reduced trial space is then defined as $\mathcal{X}_{N}:= \text{span}\{\xi ^{1},\ldots,\xi ^{N}\}$ and one needs some stable (possibly parameter-dependent) test space $\mathcal{Y}_{N}(\mu )$. The reduced problem reads

$$\displaystyle{ \text{find }u_{N}(\mu ) \in \mathcal{X}_{N}:\,\, c(u_{N}(\mu ),v_{N};\mu ) = h(v_{N};\mu )\quad \forall \ v_{N} \in \mathcal{Y}_{N}(\mu ). }$$

(1.8)

In the above setting, it is easy to derive an error estimate which also results in the required error estimator Δ _N (μ) defined by

$$\displaystyle{ \|u^{\mathcal{N}}(\mu ) - u_{ N}(\mu )\|_{\mathcal{X}}\leq \frac{1} {\beta _{c}} \|r_{N}(\cdot;\mu )\|_{\mathcal{Y}^{{\prime}}} =:\varDelta _{N}(\mu ), }$$

(1.9)

where $r_{N}(v;\mu ):= h(v;\mu ) - c(u_{N}(\mu ),v;\mu ) = c(u^{\mathcal{N}}(\mu ) - u_{N}(\mu ),v;\mu )$, $v \in \mathcal{Y}^{\mathcal{N}}$, is the residual and β _c is the inf-sup constant associated with the bilinear form c.

We call (1.8) online efficient if it can be solved with complexity independent of $\mathcal{N}$. In order to reach that goal, the following assumption is crucial: The forms are assumed to be separable in the parameter (sometimes called affine decomposition),

$$\displaystyle\begin{array}{rcl} \begin{array}{rclrcl} c(u,v;\mu ) =\sum _{ q=1}^{Q_{c}}\theta _{q}^{c}(\mu )\,c_{q}(u,v),&&&h(v;\mu ) =\sum _{ q=1}^{Q_{h}}\theta _{q}^{h}(\mu )\,h_{q}(v)\end{array} & &{}\end{array}$$

(1.10)

for some $Q_{c},Q_{h} \in \mathbb{N}$, functions $\theta _{q}^{c},\theta _{q}^{h}: \mathcal{P}\rightarrow \mathbb{R}$ and parameter-independent forms c _q , h _q that can be precomputed in the offline phase. The parameter-dependent functions θ _q ^c, θ _q ^h are assumed to be computable online efficient, i.e., with complexity independent of $\mathcal{N}$.

1.4 Reduced Basis Methods with POD-Greedy

We start from the semi-variational formulation (1.3) and apply a semi-discretization in time, known as Rothe’s method. To this end, set $\varDelta t:= \frac{T} {K}$ for some K > 1, t ^k: = k Δt and we seek some approximation u ^k ≈ u(t ^k), where we omit the μ-dependency to shorten notation. This leads to a sequence of elliptic (time-independent) ordinary differential equations starting with u ⁰: = u ₀. The standard θ-scheme then reads

$$\displaystyle\begin{array}{rcl} \frac{1} {\varDelta t}\big(u^{k+1} - u^{k},v\big)_{ H}& +& a(\theta u^{k+1} + (1-\theta )u^{k},v;\mu ) {}\\ & =& \theta g(v,t^{k+1};\mu ) + (1-\theta )g(v,t^{k};\mu ),\quad v \in V. {}\\ \end{array}$$

“Truth” The next step is a discretization in space by a standard Galerkin method using finite-dimensional spaces V _h ⊂ V with large $\dim (V _{h}) = \mathcal{N}_{h} \in \mathbb{N}$. Then, the detailed or “truth” problem for a given parameter $\mu \in \mathcal{P}$ reads for an initial value $u_{h}^{0}:= \text{Proj}_{V _{h}}u^{0}$ to find u _h ^k+1(μ) ∈ V _h , such that for v _h ∈ V _h ,

$$\displaystyle\begin{array}{rcl} & & (u_{h}^{k+1},v_{ h})_{H} +\varDelta t\theta \,a(u_{h}^{k+1},v_{ h};\mu ) {}\\ & & = (u_{h}^{k},v_{ h})_{H} +\varDelta t(1-\theta )\,a(u_{h}^{k},v_{ h};\mu ) +\theta g(v_{h},t^{k+1};\mu ) + (1-\theta )g(v_{ h},t^{k};\mu ), {}\\ \end{array}$$

for 0 ≤ k ≤ K − 1. If $V _{h} = \text{span}\{\phi _{i}:\, i = 1,\ldots,\mathcal{N}_{h}\}$, the latter equation can be written in matrix-vector form as follows. Let $\underline{M}_{h}^{\text{space}}:= [(\phi _{i},\phi _{j})_{H}]_{i,j=1,\ldots,\mathcal{N}_{h}}$ denote the spatial mass matrix and $\underline{A}_{h}^{\text{space}}:= [a(\phi _{i},\phi _{j})]_{i,j=1,\ldots,\mathcal{N}_{h}}$ the stiffness matrix (we denote matrices and vectors by underlined symbols), then we look for

$$\displaystyle{u_{h}^{k+1} =\sum _{ i=1}^{\mathcal{N}_{h} }\alpha _{i}^{k+1}\,\phi _{ i},\qquad \underline{\alpha }^{k+1}:= (\alpha _{ i}^{k+1})_{ i=1,\ldots,\mathcal{N}_{h}},}$$

such that (g ^k and α ₀ being the expansion coefficients of g(t ^k) and u ₀, respectively)

$$\displaystyle\begin{array}{rcl} & & (\underline{M}_{h}^{\text{space}} +\theta \varDelta t\,\underline{A}_{ h}^{\text{space}}(\mu ))\underline{\alpha }^{k+1} \\ & & = (\underline{M}_{h}^{\text{space}} + (1-\theta )\varDelta t\,\underline{A}_{ h}^{\text{space}})\underline{\alpha }^{k} +\varDelta t(\theta \underline{g}^{k+1} + (1-\theta )\underline{g}^{k}),{}\end{array}$$

(1.11)

for 0 ≤ k ≤ K − 1 as well as α ⁰: = α ₀. It is well-known that the θ-scheme is unconditionally stable for $\frac{1} {2} \leq \theta \leq 1$, whereas for $0 \leq \theta <\frac{1} {2}$ the space discretization has to satisfy additional properties, see e.g. [10, Theorem 11.3.1]. The choice $\theta = \frac{1} {2}$ results in the Crank-Nicolson scheme. Note, that (1.11) requires to solve a well-posed elliptic problem for each time step k, which easily follows from the assumption (1.1) on the bilinear form a and coercivity of m(ϕ, ψ): = (ϕ, ψ) _H . In fact, this implies that the matrix M _h ^space + θΔt A _h ^space(μ) is positive definite, e.g. [10, §11.3].

The system (1.11) is offline/online decomposable which is easily seen as long as the forms a and g are separable in the parameter. In fact, the mass inner product m is independent of the parameter.

Reduced Basis via POD-Greedy The reduced basis is computed by the POD-Greedy method shown in Algorithm 1. This is a combination of the standard Greedy algorithm for the parameter search and a Proper Orthogonal Decomposition (POD) in time to select the time step containing the maximal information of the trajectory for the given parameter.

Algorithm 1 POD-Greedy algorithm [5]

Online Phase The POD-Greedy method produces a reduced space V _N ⊂ V of possibly small dimension $N:= N_{\text{POD-G}} \ll \mathcal{N}_{h}$. Then, a reduced basis approximation for a new parameter $\mu \in \mathcal{P}$ is determined by a corresponding time-stepping scheme as follows. The reduced initial value u _N ⁰ ∈ V _N is computed by (u _N ⁰ − u ₀, v _N ) _V = 0 for all v _N ∈ V _N . Then, for 0 ≤ k ≤ K − 1, determine u _N ^k+1(μ) ∈ V _N by

$$\displaystyle{ \frac{1} {\varDelta t} (u_{N}^{k+1} - u_{ N}^{k},v_{ N})_{H} + a(\theta u_{N}^{k+1} + (1-\theta )u_{ N}^{k},v_{ N};\mu ) = f(v_{N};\mu ),\quad v_{N} \in V _{N}. }$$

Obviously, this amounts solving a sequence of K reduced problems online.

Error Estimator/Indicator As in the standard case in Sect. 1.3, an online efficient error estimator is needed both in Algorithm 1 and online for the desired certification of the RB approximation. Of course, such an estimator here also needs to incorporate the temporal evolution. In fact, there are several known choices for Δ _N (μ) in Algorithm 1. A standard estimator (bound) for the error e ^k(μ): = u _h ^k(μ) − u _N ^k(μ) at final time T = t ^K is given by [4, Proposition 3.9]

$$\displaystyle{ \|e^{K}(\mu )\|_{ V } \leq \| e^{0}(\mu )\|_{ V }\left (\frac{\gamma _{\text{UB}}} {\alpha _{\text{LB}}} \right )^{K} +\sum _{ k=0}^{K-1} \frac{\varDelta t} {\alpha _{\text{LB}}} \left (\frac{\gamma _{\text{UB}}} {\alpha _{\text{LB}}} \right )^{K-k-1} \|r_{ N}^{k}(\mu )\|_{ V ^{{\prime}}} =:\varDelta _{ N}^{K}(\mu ). }$$

(1.12)

Here, α _LB is a lower bound for the coercivity constant of the implicit part of the operator, γ _UB an upper bound for the continuity constant of the explicit part and r _N ^k(μ) is the residual at time step t ^k. It can easily be seen that Δ _N ^K is offline/online decomposable. There are some remarks in order.

Remark 1

 

• (i) In our numerical experiments in Sect. 1.6 below, we use a finite element (FE) discretization. In that case, the estimator (1.12) can not be used. In fact, α _LB ≪ γ _UB, in our case Δ _N ^K(μ) ≈ 10¹¹⁹. This shows that Δ _N ^K(μ) grows extremely quickly with increasing K for FE discretizations in V = H ₀ ¹(Ω), which makes (1.12) practically useless. Note, however, that for FV discretizations, one has α _LB = γ _UB = 1, so that the estimator works often quite well.

• (ii) For symmetric differential operators, the above estimate can be sharpened [4, Proposition 3.11]. It allows to extend (1.12) to a μ-dependent norm on the whole trajectory. $\diamond$

According to this remark, we cannot use Δ _N ^K(μ) here. Thus, we follow the analysis in [4] and consider a weighted (sometimes called “space-time”) norm for ω: = (ω _k ) _{k = 0, …, K−1}, ω _k > 0 and ∑ _{k = 0} ^K−1 ω _k = T defined as

$$\displaystyle{ \vert \boldsymbol{e}\vert _{\underline{\omega }}^{2}:=\sum _{ k=0}^{K-1}\omega _{ k}\|e^{k}\|_{ V }^{2},\qquad \boldsymbol{e} = (e^{k})_{ k=0,\ldots,K-1}. }$$

(1.13)

A corresponding error indicator is defined as

$$\displaystyle{ \varDelta _{N,\underline{\omega }}^{\text{PST}}:= \left (\sum _{ k=0}^{K-1}\omega _{ k}\|r_{N}^{k}(\mu )\|_{ V ^{{\prime}}}^{2}\right )^{1/2}. }$$

(1.14)

The term “indicator” means that the error (in whatever norm) cannot be proven to be bounded in terms of $\varDelta _{N,\boldsymbol{\omega }}^{\text{PST}}$ (it is not known to be a bound). However, even though the error of the POD-Greedy scheme cannot be guaranteed to decay monotonically, exponential convergence can be shown under additional assumptions [3].

1.5 Space-Time Reduced Basis Methods

As we have seen in Sect. 1.2, the space-time variational formulation leads to a parameterized Petrov-Galerkin problem. Thus, the form is exactly as in the general RB-framework in (1.6). Note, that both $\mathbb{X} = H^{1}(I) \otimes V$ and $\mathbb{Y} = (L_{2}(I) \otimes V ) \times H$ are tensor products, so that it is convenient to use the same structure for the detailed discretization, i.e., $\mathbb{X}^{\mathcal{N}} = S_{\varDelta t} \otimes V _{h}$ and $\mathbb{Y}^{\mathcal{N}} = (Q_{\varDelta t} \otimes V _{h}) \times V _{h}$,² where V _h ⊂ V is the space discretization as in Sect. 1.4 above and S _Δt ⊂ H ¹(I) as well as Q _Δt ⊂ L ₂(I) are temporal discretizations of step size Δt [14].

Let us denote again by $V _{h} = \text{span}\{\phi _{1},\phi _{2},\ldots,\phi _{\mathcal{N}_{h}}\}$ the detailed space discretization (e.g. by piecewise linear finite elements for V = H ₀ ¹(Ω)). Moreover, let S _Δt = span{σ ⁰, σ ¹, …, σ ^K} and Q _Δt = span{τ ¹, τ ², …, τ ^K} be the bases in time (e.g. piecewise linear σ ⁱ and piecewise constant τ ⁱ on the same temporal mesh, with the additional σ ⁰ for the initial value at t = 0).

The dimension of the arising test and trial spaces coincide, i.e., $\text{dim}(\mathbb{X}^{\mathcal{N}}) = (K + 1)\mathcal{N}_{h} = \text{dim}(\mathbb{Y}^{\mathcal{N}}) =: \mathcal{N}$. Exploiting the structure of the discretized spaces for the detailed solution $u^{\mathcal{N}} =\sum _{ i=1}^{\mathcal{N}_{h}}\sum _{ k=0}^{K}u_{ i}^{k}\sigma ^{k} \otimes \phi _{ i}$ yields

$$\displaystyle\begin{array}{rcl} b(u^{\mathcal{N}},(\tau ^{k} \otimes \phi _{ j},0);\mu )& =& \sum _{i=1}^{\mathcal{N}_{h} }[(u_{i}^{k} - u_{ i}^{k-1})(\phi _{ i},\phi _{j})_{H} + \frac{\varDelta t} {2}(u_{i}^{k} + u_{ i}^{k-1})a(\phi _{ i},\phi _{j};\mu )] {}\\ & =& \underline{M}_{h}^{\text{space}}(u^{k} - u^{k-1}) +\varDelta t\,\underline{A}_{ h}^{\text{space}}(\mu )u^{k-1/2}, {}\\ \end{array}$$

with mass and stiffness matrices M _h ^space, A _h ^space(μ) as above. On the right-hand side, we use a trapezoidal approximation as in [14] on a time grid 0 = t ⁰ < ⋯ < t ^K = T, I ^ℓ: = [t ^ℓ−1, t ^ℓ) = supp{τ ^ℓ}:

$$\displaystyle\begin{array}{rcl} f((\tau ^{\ell} \otimes \phi _{j},0);\mu )& =& \int _{I}\langle g(t;\mu ),\tau ^{\ell} \otimes \phi _{j}(t,.)\rangle _{V ^{{\prime}}\times V }dt =\int _{I^{\ell}}\langle g(t;\mu ),\tau ^{\ell}(t)\phi _{j}\rangle _{V ^{{\prime}}\times V }dt {}\\ & \approx & \frac{\varDelta t} {2}\langle g(t^{\ell-1};\mu ) + g(t^{\ell};\mu ),\phi _{ j}\rangle _{V ^{{\prime}}\times V }. {}\\ \end{array}$$

It turns out that this particular choice for the discretization results (again) in the Crank-Nicolson scheme involving an additional projection of the initial value, which requires a CFL condition to ensure stability. A detailed investigation of stable space-time discretizations can be found in [1].

Since the space-time variational approach yields a standard Petrov-Galerkin problem, the reduced basis trial and test spaces $\mathbb{X}_{N} = \text{span}\{\xi ^{1},\ldots,\xi ^{N}\}$, $\mathbb{Y}_{N}(\mu ):= \text{span}\{\eta ^{1}(\mu ),\ldots,\eta ^{N}(\mu )\}$ can be constructed exactly following the road map in Sect. 1.3. Hence, we end up with a reduced problem of the form (1.8). In matrix-vector form, the resulting system matrix B _N (μ): = [b(ξ ⁱ, η ^j(μ); μ)] _{i, j = 1, …, N} is of small dimension, but not symmetric. Moreover, B _N (μ) is uniformly invertible provided that the inf-sup condition in (1.5) holds for the RB spaces. It is not difficult to show that the arising non-symmetric linear system can also be written as minimization problem or in terms of normal equations (see [8] for details and further applications).

If normal equations are used, no (parameter dependent) reduced test space computation is required: Let $\mathbb{X}^{\mathcal{N}} =\mathrm{ span}\{\varphi _{\ell}:\ell= 1,\ldots,\mathcal{N}\}$ and $\mathbb{Y}^{\mathcal{N}} =\mathrm{ span}\{\psi _{m}: m = 1,\ldots,\mathcal{N}\}$ be the detailed bases, denote by $\underline{Y }^{\mathcal{N}}:= [(\psi _{m},\psi _{m^{{\prime}}})_{\mathbb{Y}}]_{m,m^{{\prime}}=1,\ldots,\mathcal{N}}$ the mass matrix of the test space $\mathbb{Y}^{\mathcal{N}}$ as well as the detailed system matrix by $\underline{B}^{\mathcal{N}}(\mu ):= [b(\varphi _{\ell},\psi _{m};\mu )]_{\ell,m=1,\ldots,\mathcal{N}}$. Next, denote by $\xi ^{j} =\sum _{ \ell=1}^{\mathcal{N}}c_{\ell}^{j}\varphi _{\ell}$, $\underline{C}:= (c_{\ell}^{\,j})_{\ell=1,\ldots,\mathcal{N},\,j=1,\ldots,N} \in \mathbb{R}^{\mathcal{N}\times N}$ the expansion of the RB functions in terms of the detailed basis. Then,

$$\displaystyle{\underline{B}_{N}(\mu ):= \underline{C}^{T}\,\underline{B}^{\mathcal{N}}(\mu )(\underline{Y }^{\mathcal{N}})^{-1}(\underline{B}^{\mathcal{N}}(\mu ))^{T}\,\underline{C},\quad \underline{f}_{ N}(\mu ):= \underline{C}^{T}\,\underline{B}^{\mathcal{N}}(\mu )(\underline{Y }^{\mathcal{N}})^{-1}\underline{f}^{\mathcal{N}}(\mu ),}$$

where $\underline{f}^{\mathcal{N}}(\mu )$ contains the detailed basis coefficients of the right-hand side. The RB approximation u _N (μ) = ∑ _{i = 1} ^N α _i (μ)ξ ⁱ, α(μ): = (α _i (μ)) _{i = 1, …, N} , is then determined by the solution of the linear system of size N, i.e.

$$\displaystyle{ \underline{B}_{N}(\mu )\,\underline{\alpha }(\mu ) = \underline{f}_{N}(\mu ). }$$

(1.15)

One can show that (1.15) admits an online/offline-separation, which is inherited from the separation of the forms a and g (in particular, we have Q _b = Q _a and Q _f = Q _g ). This means that (1.15) can be solved online efficient. Finally, the inf-sup stability of (1.15) is inherited from the detailed discretization.

1.6 Numerical Results

We provide some of our numerical investigations concerning the two approaches described above for a standard diffusion-convection-reaction problem with time dependent right-hand side. Since our focus is on the treatment of the time variable, we restrict ourselves to a 1d problem in space.

1.6.1 Data

Model Problem Let d = 1, Ω = (0, 1) and V: = H ₀ ¹(Ω) ↪ L ₂(Ω) =: H. Consider the time interval I = (0, 0. 3) and the parameter set $\mathcal{P}:= [0.5,1.5] \times [0,1] \times [0,1] \subset \mathbb{R}^{3}$. For a parameter $\mu = (\mu _{1},\mu _{2},\mu _{3})^{T} \in \mathcal{P}$ find u ≡ u(μ) that solves

$$\displaystyle\begin{array}{rcl} \begin{array}{rclrcl} \dot{u} -\mu _{1}u^{{\prime\prime}} +\mu _{2}u^{{\prime}} +\mu _{3}u& = g\qquad \qquad \qquad &&\text{on }I\times \varOmega,\end{array} & &{}\end{array}$$

(1.16a)

$$\displaystyle\begin{array}{rcl} \begin{array}{rclrcl} u(t,x)& = 0\qquad \qquad \qquad &&\forall \ (t,x) \in I \times \partial \varOmega,\end{array} & &{}\end{array}$$

(1.16b)

$$\displaystyle\begin{array}{rcl} \begin{array}{rclrcl} u(0,x)& = u_{0}(x):=\sin (2\pi x)\qquad \qquad \qquad &&\forall \ x \in \varOmega.\end{array} & &{}\end{array}$$

(1.16c)

Set g(t, x): = sin(2πx)((4π ² + 0. 5)cos(4πt) − 4πsin(4πt)) + πcos(2πx)cos(4πt), which corresponds to the solution u(t, x): = sin(2πx)cos(4πt) of (1.16) for the reference parameter $\mu ^{\mathrm{ref}} = (1,0.5,0.5) \in \mathcal{P}$. The parameter-separability is easily seen. We divide both Ω and I into 2⁶ subintervals, i.e., $\mathcal{N}_{h} = 2^{6} - 1$ and K = 2⁶, but we also consider various values for K. The training set $\mathcal{P}_{\text{train}}$ is chosen as 17 equidistantly distributed points in $\mathcal{P}$ in each direction.

“True” Norms For the space-time RBM, the “true” error is measured in the natural discrete space-time norm [13]

$$\displaystyle{ \vert \|v\vert \|_{\mathcal{N}}^{2}:=\|\bar{ v}\|_{ L_{2}(I;V )}^{2} +\|\dot{ v}\|_{ L_{2}(I;V ^{{\prime}})}^{2} +\| v(T)\|_{ H}^{2},\qquad v \in \mathbb{X}^{\mathcal{N}}\subset \mathbb{X}, }$$

where $\bar{v}:=\sum \limits _{ k=1}^{K}\tau ^{k} \otimes \bar{ v}^{k} \in L_{2}(I;V )$ and $\bar{v}^{k}:= (\varDelta t)^{-1}\int \limits _{I^{k}}v(t)\,dt \in V$. Note, that $\|\bar{v}\|_{L_{2}(I;V )}$ is an $\mathcal{O}(\varDelta t)$-approximation of $\|v\|_{L_{2}(I;V )}$ (due to the piecewise constant approximation $\bar{v}^{k}$).

For the POD-Greedy strategy, we consider the final time contribution ∥v(T)∥ _V [corresponding to the left-hand side of (1.12)] as well as the “space-time norm” introduced in (1.13) for the specific weights ω _k : = Δt, k = 0, …, K − 1, plus the final time contribution as “true” error, i.e.

$$\displaystyle{\vert v\vert _{\varDelta t}^{2}:= \vert (v(t^{k}))_{ k=0,\ldots,K-1}\vert _{\underline{\omega }}^{2} +\varDelta t\,\|v(T)\|_{ V }^{2} =\sum _{ k=0}^{K}\varDelta t\|v(t^{k})\|_{ V }^{2}.}$$

This means that | v | _Δt is an $\mathcal{O}(\varDelta t^{2})$-approximation of $\|v\|_{L_{2}(I;V )}$.

Remark 2

For later reference, we point out that | v | _Δt is an $\mathcal{O}(\varDelta t^{2})$-approximation of $\|v\|_{L_{2}(I;V )}$, whereas $\|\bar{v}\|_{L_{2}(I;V )}$ is only of the order $\mathcal{O}(\varDelta t)$. This means that it may happen that $\vert w\vert _{\varDelta t}> \vert \|w\vert \|_{\mathcal{N}}$ even though $\|w\|_{\mathbb{X}}>\| w\|_{L_{2}(I;V )}$ for all $0\neq w \in \mathbb{X}$. $\diamond$

Error Estimators/Greedy For the error estimation in the space-time RBM, we use the residual-based error estimator Δ _N (μ) in (1.9) with numerically estimated lower bound for the inf-sup constant, β _LB = 0. 2. Of course, this is a relatively rough bound (independent of μ!) and performing e.g. a Successive Constraint Method (SCM [7]) would improve the subsequent results. For the POD-Greedy scheme, we use the space-time error indicator Δ _N ^PST(μ) that arises from (1.14) by the choice ω _k ≡ Δt for the weights.

We emphasize that Δ _N (μ) bounds the norm in $\mathbb{X} = H^{1}(I) \otimes V \subsetneq L_{2}(I;V )$, whereas Δ _N ^PST(μ) is “only” an indicator, in particular it is not known to be an upper bound for any norm. In view of (1.12), we could expect that ∥e ^K(μ)∥ _V might be a candidate, or—since | ⋅ | _Δt is a discrete L ₂(I; V )-norm—we could consider $\|e\|_{L_{2}(I;V )}$.

Comparison We conclude that a direct and fair comparison is not easy because of the described methodological differences. Table 1.1 collects these differences and our choice for the experiments.

Table 1.1 Differences of space-time RBM and POD-Greedy sampling

1.6.2 Results

Greedy Training Within the framework of Table 1.1, the offline Greedy error decay of both variants is shown in Fig. 1.1. The red lines correspond to the space-time form, whereas the blue lines are for the POD-Greedy. Straight lines indicate the error, dotted ones the error estimator/indicator. The left figure shows the weak Greedy using the error estimators/indicators. We observe exponential decay w.r.t. the RB dimension N in both cases—as predicted by the theory. At a first glance, it seems that the decay of POD-Greedy is much faster than the one for space-time, i.e., the stopping criterium in the Greedy algorithm for tol = 10⁻³ is reached at N _POD-G = 7 and N _ST = 16. Note, however, that the online effort is related to N in a different way for both variants, see below.

Fig. 1.1

RB-Greedy approximation error. Red: Space-Time (ST); blue: POD-Greedy (POD-G). Left: weak Greedy, right: strong Greedy w.r.t. $\vert \vert \vert \cdot \vert \vert \vert _{\mathcal{N}}$. Lines are plotted until the stopping criteria for tol = 10⁻³ are reached in the while-loop (i.e., the error estimators in the next step are below tol)

As mentioned above, the two variants are related to different norms. This is the reason why we performed a strong Greedy using the $\vert \vert \vert \cdot \vert \vert \vert _{\mathcal{N}}$-norm for both variants (right graph in Fig. 1.1). We see a similar behavior—again referring to the different online work load. It is interesting, though, that at least in these experiments, POD-Greedy works very well even for the full norm—without theoretically foundation though. However, we can also see from the results that Δ _N ^PST(μ) is not an error bound since it is below the “exact” error for some N. Recall that Δ _N ^PST(μ) arises from the upper bound Δ _N ^K(μ) in (1.12) by setting involved coercivity and continuity constants to 1. Moreover, note, that in the same spirit, we could easily lower the gap between the two red space-time lines by sharpen β _LB. The prescribed Greedy tolerance of 10⁻³ is reached for N _POD-G = 6 for POD-Greedy and for N _ST = 12 for space-time.

Online Phase We test the RB approximations for two cases, namely for $\mathcal{P}_{\text{test}}^{\text{sym}}:=\{ (\mu _{1},0,0):\,\mu _{1} \in [0.5,1.5]\}$ (symmetric case) and $\mathcal{P}_{\text{test}}^{\text{non}}:=\{ (0.5,\mu _{2},0.75):\,\mu _{2} \in [0,1]\}$ (non-symmetric case). The results are shown in Fig. 1.2, the symmetric case in the top line, the non-symmetric in the bottom one.

Fig. 1.2

RB approximation error on $\mathcal{P}_{\text{test}}$: Full error (red, solid), error estimator/indicator (black, dash-dotted) and the POD-Greedy error measure | ⋅ | _Δt (blue, dashed) for Greedy tolerance tol = 0. 001. Top line: symmetric case (μ ₁, 0, 0); bottom: non-symmetric (0. 5, μ ₂, 0. 75). (a) Space-time, symmetric. (b) POD-Greedy, symmetric. (c) Space-time, non-symmetric. (d) POD-Greedy, non-symmetric

First of all, both variants work as they should in the sense that the respective error measures are below the Greedy tolerance of 10⁻³.

The “true” error (solid red lines) is slightly smaller for the space-time variant in the symmetric case and very close to each other in the non-symmetric case.

We also compare the POD-Greedy error measure | ⋅ | _Δt . It is remarkable that this quantity is almost identical to $\vert \vert \vert \cdot \vert \vert \vert _{\mathcal{N}}$ for space-time. This means that the temporal derivative and the final time components of the solution are very-well approximated. Regarding the result that for POD-Greedy the | ⋅ | _Δt -lines turn out to be above the $\vert \vert \vert \cdot \vert \vert \vert _{\mathcal{N}}$ one, we recall Remark 2.

Finally, the error estimators/indicators are plotted as dash-dotted black lines. We observe, that the effectivities³ are of almost the same size. However, if we rely on the respective theory (i.e. $\vert \vert \vert e\vert \vert \vert _{\mathcal{N}}$ for space-time and ∥e(T)∥ _V for POD-Greedy), the effectivity of space-time improves, see Fig. 1.3.

Fig. 1.3

Greedy error decay (a), space-time (b) and POD-Greedy (c) using the final time for POD-Greedy training and error measure on the symmetric test set

Work Load/Effort We now compare the computational effort as well as the storage amount (offline and online) of both variants, see Table 1.2.

Table 1.2 Offline and online effort of the RBMs

Recall, that the chosen space-time method in the offline phase reduces to the Crank-Nicholson scheme. Hence, the offline complexities and storage requirements for the detailed solution of both variants indeed coincide (both linear in $\mathcal{N}_{h}$; we count $187 \approx 3\mathcal{N}_{h}$ elements). The detailed solution requires K solves (corresponding to the number of time steps) of a sparse system of size $\mathcal{N}_{h}$. However, the space-time precomputations needed to form the online system, rely on the full dimension $\mathcal{N}$.

In the online-phase, POD-Greedy needs to store (for the LTI case) Q _a reduced matrices and KQ _g vectors of size N _POD-G for the time-dependent right-hand side. The RB solution amounts to solve K densely populated reduced systems. In the LTI case, one may reduce this to the computation of one LU-decomposition and then K triangular systems, i.e., $\mathcal{O}(N_{\text{POD-G}}^{3} + KN_{\text{POD-G}}^{2})$ operations.

The space-time method usually requires more storage, either by storing a suitable test space or—as described above—by the setup of the normal equations using the affine decomposition (1.10). The normal equations need memory of size $\mathcal{O}(Q_{b}^{2}N_{\text{ST}}^{2} + Q_{b}Q_{f}N_{\text{ST}})$. The RB-solution requires the solution of one reduced linear system of dimension N _ST.

1.7 Conclusions

We have explained and compared both theoretically and numerically two different techniques to treat the time within the Reduced Basis Method (RBM). It is obvious that a fair and significant numerical comparison is a delicate task. In particular,

• different norms need to be considered;

• the choice of the error estimator/indicator within the POD-Greedy method has a significant impact;

• improving bounds for the involved constants will improve the results;

• we only consider such space-time methods that are equivalent to a time marching scheme (here Crank-Nicholson). If this is not the case, the offline cost for the space-time scheme will significantly increase;

• the number of time steps (K = 64) is moderate. As noted in Table 1.2, the online effort for POD-Greedy grows linearly with K, whereas the online space-time effort is independent of K. The reason is that the number of POD-Greedy basis functions stays the same and just more time steps are needed. The dimension of the space-time reduced system is independent of K. Increasing K (i.e., a higher temporal resolution or longer time horizons keeping Δt the same) will support space-time;

• we only consider LTI-systems. Both the reduction rate and the storage depend on this assumption.

Despite all these, we do think that our study indeed shows some facts, namely:

• 1. The POD-Greedy method allows one to use any time-marching scheme offline. Even if the space-time discretization is chosen in such a way that it coincides with a time-stepping scheme, this variant has an increased offline complexity. If the full space-time dimension is needed, one may have to resort to tensor product schemes [8].

• 2. In the online phase, the space-time method is more efficient concerning effort, whereas POD-Greedy uses less storage.

• 3. If a theoretical justification of an error bound in the full $\mathbb{X}$-norm is needed and Finite Elements shall be used, space-time seems to be the method of choice. If a Finite Volume discretization is chosen, POD-Greedy is more appropriate [5].

From these results, we tend to formulate the following recipe: If online computational time restrictions apply or for long-time horizons, the space-time approach is advisable even in those cases where it might cause an increased offline effort. If online storage restrictions apply or the use of a specific time-marching scheme is necessary, the POD-Greedy approach is advisable.