Multipatch Space-Time Isogeometric Analysis of Parabolic Diffusion Problems

Abstract

We present and analyze a new stable multi-patch space-time Isogeometric Analyis (IgA) method for the numerical solution of parabolic diffusion problems. The discrete bilinear form is elliptic on the IgA space with respect to a mesh-dependent energy norm. This property together with a corresponding boundedness property, consistency and approximation results for the IgA spaces yields a priori discretization error estimates. We propose an efficient implementation technique via tensor product representation, and fast space-time parallel solvers. We present numerical results confirming the efficiency of the space-time solvers on massively parallel computers using more than 100.000 cores.

1 Introduction

The standard discretization methods for parabolic initial-boundary value problems (IBVP) are based on a separation of the discretizations in space and time, i.e., first space, then time, or, vice versa, first time, then space. The former one is called vertical method of lines, whereas the latter one is called horizontal method of lines or Rothe’s method. Both methods use some kind of time-stepping method for time discretization. This is a sequential procedure that needs some smart ideas for the parallelization with respect to time, see [4] for a historical overview of time-parallel methods. Other disadvantages of these approaches are connected with a separation of adaptivity with respect to space and time, and with difficulties in the numerical treatment of moving interfaces and spatial domains. To overcome this curse of sequentiality of time-stepping methods, one should look at the time variable t as just another variable, say, $x_{d+1}$ if $x_1,\ldots ,x_d$ are the spatial variable, and at the time derivative as a strong convection in the direction $x_{d+1}$. In [10], we were inspired by this view at parabolic problems, and proposed upwind-stabilized single-patch space-time IgA schemes for parabolic evolution problems. For comprehensive overview on the literature on different space-time methods for solving parabolic IPVP, we also refer to [10].

In this paper, we generalize the results of [10] from the single-patch to the time dG multi-patch IgA case. As in [10], we consider the linear parabolic IBVP: find $u : \overline{Q} \rightarrow \mathbb {R}$ such that

$$\begin{aligned} \partial _{t} u - \varDelta u = f \; \text {in}\; Q, \; u=0 \; \text {on}\; \varSigma , \; \text {and}\; u=u_0 \; \text {on}\; \varSigma _0, \end{aligned}$$

(1)

as a typical model problem posed in the space-time cylinder $\overline{Q} = \overline{\varOmega } \times [0,T] = Q \cup \varSigma \cup \overline{\varSigma }_0 \cup \overline{\varSigma }_T$ where $\partial _{t}$ denotes the partial time derivative, $\varDelta$ is the Laplace operator, f is a given source function, $u_0$ are the given initial data, T is the final time, $Q = \varOmega \times (0,T)$, $\varSigma = \partial \varOmega \times (0,T)$, $\varSigma _0 := \varOmega \times \{0\}$, $\varSigma _T := \varOmega \times \{T\}$, and $\varOmega \subset \mathbb {R}^{d}$ $(d = 1,2,3)$ denotes the spatial computational domain with the boundary $\partial \varOmega$. The spatial domain $\varOmega$ is supposed to be bounded and Lipschitz. Later we will assume that $\varOmega$ has a single- or multipatch NURBS representation as is used in CAD respectively IgA.

2 Space-Time Variational Formulation

Using the standard procedure and integration by parts with respect to both x and t, we can easily derive the following space-time variational formulation of (1): find $u\in H^{1,0}_0(Q) = \{u \in L_2(Q):\nabla _x u \in [L_2(Q)]^d, u = 0 \; \text {on} \; \varSigma \}$ such that

$$\begin{aligned} a(u,v) = l(v), \quad \forall v \in H^{1,1}_{0,\bar{0}}(Q), \end{aligned}$$

(2)

with the bilinear form

$$\begin{aligned} a(u,v) = -\int _{Q}u(x,t)\partial _t v(x,t)\,dx\,dt+\int _{Q}\nabla _xu(x,t)\,\cdot \,\nabla _x v(x,t)\,dx\,dt \end{aligned}$$

(3)

and the linear form

$$\begin{aligned} l(v) = \int _{Q}f(x,t)v(x,t)\,dx\,dt+\int _{\varOmega }u_0(x)v(x,0)\,dx, \end{aligned}$$

(4)

where . The space-time variational formulation (2) has a unique solution, see, e.g., [8, 9]. In these monographs, beside existence and uniqueness results, one can also find useful a priori estimates and regularity results. For simplicity, we below assume that $u_0=0$.

3 Stable Multi-patch Space-Time IgA Discretization

Let us now assume that the space-time cylinder ${\overline{Q}} = \cup _{n=1}^N \overline{Q}_n$ consists of N subcylinders (patches or time slices) $Q_n = \varOmega \times (t_{n-1},t_n)$, $n=1,\ldots ,N$, where $0=t_{0}< t_1< \ldots < t_{N}=T$ is some subdivision of time interval [0, T]. The time faces between the time patches are denoted by $\overline{\varSigma }_n=\overline{Q}_{n+1}\cap \overline{Q}_n= \overline{\varOmega } \times \{t_n\}$. We obviously have ${\varSigma }_N = {\varSigma }_T$. Every space-time patch $Q_n = \mathbf {\Phi }_n (\widehat{Q})$ in the physical domain Q can be represented as the image of the parameter domain $\widehat{Q} = (0,1)^{d+1}$ by means of a sufficiently regular IgA (B-Spline, NURBS etc.) map $\mathbf {\Phi }_n: \widehat{Q}\rightarrow Q_n$, i.e.,

$$\begin{aligned} \mathbf {\Phi }_n(\xi ) = \sum _{i \in \mathcal {I}_n} \mathbf {P}_{n,i} \widehat{\varphi }_{n,i}(\xi ), \end{aligned}$$

(5)

where $\{\widehat{\varphi }_{n,i}\}_{i\in \mathcal {I}_n}$ are the IgA basis functions, and $\{ \mathbf {P}_{n,i}\}_{i\in \mathcal {I}_n} \subset \mathbb {R}^{d+1}$ are the control points for the patch $Q_n$. The IgA basis functions are usually multivariant B-Splines or NURBS defined on a mesh given by the knot vector wrt to each direction in the parameter domain $\widehat{Q}$, and the underlying polynomial degrees and multiplicities of the knots defining the smoothnesses of the basis functions, see, e.g., [2] or [11] for more detailed information.

Now, we can construct our finite-dimensional IgA (B-Spline, NURBS etc.) space $V_{0h} = \{ v_h: v_n=v_h|_{Q_n} \in V_{0n}, n=1,\ldots ,N\}$, the functions of which are smooth in each time patch $Q_n$ in correspondence to the smoothness of the splines, but in general discontinuous across the time faces $\varSigma _n$, $n=1,\ldots ,N-1$. The smooth IgA spaces $V_{0n}=V_{0h_n}=\text {span}\{\varphi _{n,i}\}_{i\in \mathcal {I}_n} \subset H^{1,1}_0(Q_n)$ are spanned by IgA basis functions $\{\varphi _{n,i}\}_{i\in \mathcal {I}_n}$ that are nothing but the images of the basis functions $\{\widehat{\varphi }_{n,i}\}_{i\in \mathcal {I}_n}$, which were already used for defining the patch $Q_n$, by the map $\mathbf {\Phi }_n$, i.e., $\varphi _{n,i} = \widehat{\varphi }_{n,i} \circ \mathbf {\Phi }_n^{-1}$. The basis functions $\varphi _{1,i}$ should vanish on ${\varSigma }_0$ for all $i\in \mathcal {I}_1$. Therefore, all functions $v_h$ from $V_{0h}$ fulfil homogeneous boundary and initial conditions. The discretization parameter $h_n$ denotes the average mesh-size of the mesh induced by the corresponding mesh in the parameter domain $\widehat{Q}$ via the map $\mathbf {\Phi }_n$. The IgA technology of using the same basis functions for describing the patches of the computational domain (geometry) and for defining the approximation spaces $V_{0h}$ was introduced by Hughes, Cottrell and Bazilevs in 2005 [7] and analyzed in [1], see also monograph [2] for more comprehensive information.

In order to derive our dG IgA scheme for defining the IgA solution $u_h \in {V}_{0h}$, we multiply the parabolic PDE (1) by a time-upwind test function of the form $v_n + \theta _n h_n \partial _t v_n$ with an arbitrary $v_n \in {V}_{0n}$ and a positive, sufficiently small constant $\theta _n$, and integrate over the space-time subcylinder $Q_n$. After integration by parts wrt x, we get

$$\begin{aligned} \nonumber&\int _{Q_n} (\partial _{t} u (v_n + \theta _n h_n \partial _{t} v_n) + \nabla _x u \cdot \nabla _x v_n + \theta _n h_n \nabla _x u \cdot \nabla _x \partial _{t} v_n)\,dxdt \\&\quad - \int _{\partial Q_n} {\mathbf n}_x \cdot \nabla _x u \,(v_n + \theta _n h_n \partial _{t} v_n)\, ds = \int _{Q_n} f (v_n + \theta _n h_n \partial _{t} v_n) \, dx dt. \end{aligned}$$

(6)

We mention that $\partial _{t} v_n$ is differentiable wrt x due to the special tensor product structure of $V_{0n}$. Using the facts that $v_n$ and $\partial _{t} v_n$ are always zero on $\varSigma$, and the x-components ${\mathbf n}_x=(n_1,\ldots ,n_d)^\top$ of the normal ${\mathbf n} = (n_1,\ldots ,n_d,n_{d+1})^\top = ({\mathbf n}_x,n_t)^\top$ are zero on $\varSigma _{n-1}$ and $\varSigma _n$, we observe that the integral over $\partial Q_n$ is always zero. Now, adding to the left-hand side of (6) a consistent time-upwind term for stabilization, and summing over all time patches, we get the identity

$$\begin{aligned} \nonumber&\sum _{n=1}^N \int _{Q_n} (\partial _{t} u (v_n + \theta _n h_n \partial _{t} v_n) + \nabla _x u \cdot \nabla _x v_n + \theta _n h_n \nabla _x u \cdot \nabla _x \partial _{t} v_h)\,dxdt \\&\quad +\sum _{n=1}^N \int _{\varSigma _{n-1}} [|u|] \, v_n \,dx = \sum _{n=1}^N \int _{Q_n} f (v_n + \theta _n h_n \partial _{t} v_n) \, dx dt \end{aligned}$$

(7)

that holds for a sufficiently smooth solution u of our parabolic IBVP, where $[|u|] := u|_{Q_n} - u|_{Q_{n-1}}$ on $\varSigma _{n-1}$ denotes the jump of u across $\varSigma _{n-1}$ that is obviously zero.

The time multipach space-time IgA scheme for solving the parabolic IBVP (1) respectively (2) can now be formulated as follows: find $u_h \in {V}_{0h}$ such that

$$\begin{aligned} a_h(u_h,v_h) = l_h(v_h), \quad \forall v_h \in {V}_{0h}, \end{aligned}$$

(8)

where

$$\begin{aligned} \nonumber a_h(u_h,v_h)&= \sum _{n=1}^N a_n(u_h,v_h) = \sum _{n=1}^N \left( \int _{Q_n} (\partial _{t} u_n (v_n + \theta _n h_n \partial _{t} v_n) + \nabla _x u_n \cdot \nabla _x v_n \right. \\&\left. \quad +\; \theta _n h_n \nabla _x u_n \cdot \nabla _x \partial _{t} v_n)\,dxdt + \int _{\varSigma _{n-1}} [|u_h|] \, v_n \,dx\right) ,\end{aligned}$$

(9)

$$\begin{aligned} l_h(v_h) =&\sum _{n=1}^N l_n(v_h) = \sum _{n=1}^N\int _{Q_n} f (v_n + \theta _n h_n \partial _{t} v_n) \, dx dt. \end{aligned}$$

(10)

Here and below we formally set $[|u_1|]$ on $\varSigma _{0}$ to zero since we assumed homogeneous initial conditions. It is clear that this jump term can be used to include inhomogeneous initial conditions in a weak sense. In this case, the test functions $v_n$ are not forced to be zero on $\varSigma _{0}$. The derivation of the IgA scheme given above immediately yields that this scheme is consistent for sufficiently smooth solution, cf. identity (7). Indeed, if the solution $u\in H^{1,0}_0(Q)$ of (2) belongs to $H^{1,1}_0(Q)$, then it satisfies the consistency identity

$$\begin{aligned} a_h(u,v_h) = l_h(v_h), \quad \forall v_h \in {V}_{0h}, \end{aligned}$$

(11)

yielding Galerkin orthogonality

$$\begin{aligned} a_h(u-u_h,v_h) = 0, \quad \forall v_h \in {V}_{0h}. \end{aligned}$$

(12)

Now we will show that the bilinear form $a_h(\cdot ,\cdot )$ is ${V}_{0h}$-elliptic wrt the norm $\Vert v\Vert _{h}$ defined by

$$\begin{aligned} \Vert v\Vert _{h}^2= \sum _{n=1}^N\!\Big (\frac{1}{2}\Vert \nabla _x v\Vert ^2_{L_2(Q_n)}\,+\,\theta _n\,h_n\,\Vert \partial _tv\Vert ^2_{L_2(Q_n)}\,+\, \frac{1}{2} \Vert \,[|v|]\,\Vert ^2_{L_2(\varSigma _{n-1})}\Big ) \,+\, \frac{1}{2}\Vert v\Vert ^2_{L_2(\varSigma _{N})}. \end{aligned}$$

In order to show the $V_{0h}$-ellipticity of $a_h(\cdot ,\cdot )$, we need the inverse inequality

$$\begin{aligned} \Vert \nabla _x v_n\Vert _{L_2(\varSigma _{n-1})}^2 \le c_{inv,0}^2 h_n^{-1} \Vert \nabla _x v_n\Vert _{L_2(Q_{n})}^2 \end{aligned}$$

(13)

that is valid for all $v_n \in V_{0n}$ and $n=1,\ldots ,N$, see [1, 3].

Lemma 1

The bilinear form $a_h(\cdot ,\cdot )$ defined by (9) is $V_{0h}$-elliptic, i.e., there exist a generic positive constant $\mu _e$ such that

$$\begin{aligned} a_h(v_h,v_h)\ge \mu _e \Vert v_h\Vert _h^2, \quad \forall v_h \in V_{0h}. \end{aligned}$$

(14)

provided that the parameters $\theta _n$ are sufficiently small. More precisely, $\mu _e=1$ if $0 < \theta _n \le c_{inv,0}^{-2}$ for all $n=1,2,\ldots ,N$, where $c_{inv,0}$ is the constant from the inverse inequality (13).

Proof

Using integration by parts with respect to t and the inverse inequality (13), we can derive the following estimates:

$$\begin{aligned} a_n(v_h,v_h)&= \int _{Q_n} \left( \frac{1}{2} \partial _t v_n^2 + \theta _n h_{n}(\partial _t v_n)^2+|\nabla _x v_n|^2 + \frac{\theta _n h_{n}}{2} \partial _t|\nabla _x v_n|^2 \right) \,dx\,dt\\&\quad + \int _{\varSigma _{n-1}} [| v_h |]\, v_n\,dx\\&= \frac{1}{2}\int _{\varSigma _{n}}v_n^2 dx - \frac{1}{2}\int _{\varSigma _{n-1}}v_n^2 dx + \int _{Q_n} \left( \theta _n h_{n}(\partial _t v_n)^2+|\nabla _x v_n|^2 \right) \,dx\,dt\\&\quad + \frac{\theta _n h_{n}}{2}\int _{\varSigma _{n}} |\nabla _x v_n|^2 dx - \frac{\theta _n h_{n}}{2}\int _{\varSigma _{n-1}} |\nabla _x v_n|^2 dx + \int _{\varSigma _{n-1}} [| v_h |]\, v_n\,dx\\&\ge \,\theta _n h_{n}\Vert \partial _t v_n\Vert ^2_{L_2(Q_n)} + \Vert \nabla _x v_n\Vert ^2_{L_2(Q_n)} - 0.5\, \theta _n h_{n}\Vert \nabla _x v_n\Vert ^2_{L_2(\varSigma _{n-1})}\\&\quad + \frac{1}{2}\int _{\varSigma _{n}}v_n^2 dx - \frac{1}{2}\int _{\varSigma _{n-1}}v_n^2 dx + \int _{\varSigma _{n-1}} v_n^2\,dx - \int _{\varSigma _{n-1}} v_{n-1}v_n\,dx\\&\ge \,\theta _n h_{n}\Vert \partial _t v_n\Vert ^2_{L_2(Q_n)} + (1 - 0.5\, \theta _n c_{inv,0}^2)\Vert \nabla _x v_n\Vert ^2_{L_2(Q_n)}\\&\quad + \int _{\varSigma _{n-1}} \left( \frac{1}{2}v_n^2 - v_{n-1}v_n \right) dx + \frac{1}{2}\int _{\varSigma _{n}}v_n^2 dx \end{aligned}$$

Summing over all $n=1,\ldots ,N$, we obtain

$$\begin{aligned} a_h(v_h,v_h)&= \sum _{n=1}^N a_{n}(v_h,v_h)\\&\ge \sum _{n=1}^N \theta _n h_{n} \Vert \partial _t v_h\Vert ^2_{L_2(Q_n)} + \big (1-0.5\, \theta _n\,c^2_{inv,0}\big ) \Vert \nabla _x v_h\Vert ^2_{L_2(Q_n)} \\&\quad +\sum _{n=1}^{N} \frac{1}{2} \Vert \,[|v_h|]\,\Vert ^2_{L_2(\varSigma _{n-1})} +\frac{1}{2} \Vert v_{N}\Vert ^2_{L_2(\varSigma _{N})}. \end{aligned}$$

Choosing $0 < \theta _n \le c_{inv,0}^{-2}$ for all $n=1,2,\ldots ,N$, we immediately arrive at (14) with $\mu _e=1$. $\blacksquare$

Lemma 1 immediately implies that the solution $u_h \in {V}_{0h}$ of (8) is unique. Since the IgA scheme (8) is posed in the finite dimensional space ${V}_{0h}$, the uniqueness yields existence of the solution $u_h \in {V}_{0h}$ of (8).

Once the basis is chosen, the IgA scheme (8) can be rewritten as a huge linear system of algebraic equations of the form

$$\begin{aligned} {\mathbf {L}}_h {\mathbf {u}_h} = {\mathbf {f}_h} \end{aligned}$$

(15)

for determining the vector ${\mathbf {u}_h} = ((u_{1,i})_{i \in \mathcal {I}_1},\ldots ,(u_{N,i})_{i \in \mathcal {I}_N}) \in \mathbb {R}^{N_h}$ of the control points of the IgA solution

$$\begin{aligned} u_h(x,t) = \sum _{i \in \mathcal {I}_n} u_{n,i} \varphi _{n,i}(x,t), \; (x,t) \in {\overline{Q}}_n, \; n=1,\ldots ,N, \end{aligned}$$

(16)

solving the IgA scheme (8). The system matrix ${\mathbf {L}}_h$ is the usual Galerkin (stiffness) matrix, and ${\mathbf {f}_h}$ is the corresponding right-hand side (load) vector.

4 A Priori Discretization Error Estimates

In order to derive a priori discretization error estimates, we will first show that the IgA bilinear form $a_h(\cdot ,\cdot )$ is bounded on $V_{0h,*} \times V_{0h}$, where the space $V_{0h,*} = V + V_{0h}$ is equipped with the norm $\Vert \cdot \Vert _{h,*}$ defined by the relation

$$\begin{aligned} \Vert v\Vert _{h,*}^2 = \Vert v\Vert ^2_{h} +\sum _{n=1}^ N (\theta _n h_{n})^{-1}\Vert v\Vert ^2_{L_2(Q_n)} + \sum _{n=2}^N\Vert v|_{Q_n}\Vert ^2_{L_2(\varSigma _{n-1})}, \end{aligned}$$

(17)

and V is a suitable infinite-dimensional space containing the solution u, e.g., we can choose $V= H_{0,\underline{0}}^{1,1}(Q) = \{u \in L_2(Q):\nabla _x u \in [L_2(Q)]^d, \partial _t u \in L_2(Q), u = 0 \; \text {on}\; \varSigma , \, \text {and} \,\, u = 0\; \text {on} \; \varSigma _0\}$ assuming that the solution u belongs to this space. In order to prove the boundedness of $a_h(\cdot ,\cdot )$, we need the inverse inequality

$$\begin{aligned} \Vert \nabla _x \partial _t v_n\Vert _{L_2(Q_{n})}^2 \le c_{inv,1}^2 h_n^{-2} \Vert \nabla _x v_n\Vert _{L_2(Q_{n})}^2 \end{aligned}$$

(18)

that is valid for all $v_n \in V_{0n}$ and $n=1,\ldots ,N$, see [1, 3].

Lemma 2

The bilinear form $a_h(\cdot ,\cdot )$ defined by (9) is bounded on the space $V_{0h,*} \times V_{0h}$, i.e., there exists a generic positive constant $\mu _b$ such that

$$\begin{aligned} |a_h(u,v_h)|\le \mu _b \Vert u\Vert _{h,*} \Vert v_h\Vert _h, \quad \forall u \in V_{0h,*}, \;\forall v_h \in V_{0h}. \end{aligned}$$

(19)

with the boundedness constant $\mu _b = 2\max \{\sqrt{1+c_{inv,1}/c_{inv,0}^2},\sqrt{2}\}$, where $c_{inv,0}$ and $c_{inv,1}$ are the constants from inequalities (13) and (18). We always assume that the parameters $\theta _n$ are chosen as in Lemma 1.

Proof

For the first and the interface jump terms of $a_h$, we use Green’s formula and the Cauchy inequality to derive the following estimates:

$$\begin{aligned}&\sum _{n=1}^{N} \left( \int _{Q_n} \partial _t u\, v_h\,\,dx\,dt + \int _{\varSigma _{n-1}}\,[| u|]\, \,v_{n}\,ds \right) \\&= \sum _{n=1}^{N} \left( - \int _{Q_n} u\, \partial _t v_h\,\,dx\,dt +\int _{\varSigma _{n}} u\, v_n\,ds - \int _{\varSigma _{n-1}} u\, v_n\,ds + \int _{\varSigma _{n-1}}\,[| u|]\, \,v_{n}\,ds \right) \\&\le \left( \sum _{n=1}^{N}(\theta _n h_{n})^{-1}\Big (\int _{Q_n}u^2\,\,dx\,dt\Big )^2\right) ^{\frac{1}{2}} \left( \sum _{n=1}^{N}\theta _n h_n\Big (\int _{Q_n}(\partial _tv_n)^2\,\,dx\,dt\Big )^2\right) ^{\frac{1}{2}} \\&\quad + \sum _{n=1}^N\int _{\varSigma _{n-1}} (v_{n-1}-v_{n})u\,ds + \int _{\varSigma _{N}} v_{n} u\,ds\\&\le \left( \sum _{n=1}^{N}(\theta _n h_{n})^{-1}\Big (\int _{Q_n}u^2\,\,dx\,dt\Big )^2\right) ^{\frac{1}{2}} \left( \sum _{n=1}^{N}\theta _n h_n\Big (\int _{Q_n}(\partial _tv_n)^2\,\,dx\,dt\Big )^2\right) ^{\frac{1}{2}} \\&\quad + \sqrt{2}\Big (\frac{1}{2}\sum _{n=1}^N [|v_{h}|]^2_{L_2(\varSigma _{n-1})} +\frac{1}{2} \Vert v_{N}\Vert ^2_{L_2(\varSigma _{N})}\Big )^{\frac{1}{2}} \sqrt{2}\Big (\sum _{n=1}^N \Vert u\Vert ^2_{L_2(\varSigma _{n-1})} + \frac{1}{2}\Vert u\Vert ^2_{L_2(\varSigma _{N})}\Big )^{\frac{1}{2}}. \end{aligned}$$

Using again Cauchy’s inequality, we get the estimates

$$\begin{aligned}&\sum _{n=1}^{N} \int _{Q_n}(\theta _n h_n)^{\frac{1}{2}}\partial _t u\, (\theta _n h_{n})^{\frac{1}{2}}\partial _t v_n\,dx\,dt +\sum _{n=1}^{N}\int _{Q_n}\nabla _x u\cdot \nabla _x v_n\,\,dx\,dt \\&\le \Big (\sum _{n=1}^{N}\theta _n h_n \Vert \partial _t u\Vert ^2_{L_2(Q_n)}\Big )^{\frac{1}{2}} \Big (\sum _{n=1}^{N}\theta _n h_n \Vert \partial _t v_n\Vert ^2_{L_2(Q_n)}\Big )^{\frac{1}{2}}\\&\quad + \sqrt{2} \Big (\frac{1}{2}\sum _{n=1}^{N} \Vert \nabla _x u\Vert ^2_{L_2(Q_n)}\Big )^{\frac{1}{2}} \sqrt{2}\Big (\frac{1}{2}\sum _{n=1}^{N}\Vert \nabla _x v_n\Vert ^2_{L_2(Q_n)}\Big )^{\frac{1}{2}} \end{aligned}$$

for the second and third terms. Finally, for the last but one term, we apply Cauchy’s and inverse inequalities to show

$$\begin{aligned}&\sum _{n=1}^{N} \int _{Q_n}\nabla _x u\cdot (\theta _n h)\nabla _x\partial _t v_n\,\,dx\,dt\\&\le \left( \sum _{n=1}^{N}\Vert \nabla _x u \Vert ^2_{L_2(Q_n)}\right) ^{\frac{1}{2}} \left( \sum _{n=1}^{N}(\theta _n h_{n})^2 \Vert \nabla _x\partial _t v_n \Vert ^2_{L_2(Q_n)}\right) ^{\frac{1}{2}}\\&\le \left( \sum _{n=1}^{N}\Vert \nabla _x u \Vert ^2_{L_2(Q_n)}\right) ^{\frac{1}{2}} \left( \sum _{n=1}^{N}(\theta _n h_{n})^2 c_{inv,1}^2 h_{n}^{-2}\Vert \nabla _x v_n \Vert ^2_{L_2(Q_n)}\right) ^{\frac{1}{2}}\\&\le c_{inv,1}\theta _n \sqrt{2} \Big (\frac{1}{2}\sum _{n=1}^{N}\Vert \nabla _x u \Vert ^2_{L^2(Q_n)}\Big )^{\frac{1}{2}} \sqrt{2}\Big (\frac{1}{2}\sum _{n=1}^{N}\Vert \nabla _x v_n\Vert _{L^2(Q_n)}\Big )^{\frac{1}{2}}. \end{aligned}$$

Gathering together the bounds obtained above yields estimate (19) with $\mu _b = 2\max \{\sqrt{1+c_{inv,1}\theta },\sqrt{2}\}$, where $\theta = \max _{n=1,\ldots ,N}\{\theta _n\} \le c^{-2}_{inv,0}$. $\blacksquare$

Let $v_h$ be an arbitrary IgA function from $V_{h0}$. Using the fact that $v_h - u_h \in V_{h0}$, the $V_{h0}$-ellipticity of the bilinear form $a_h(\cdot ,\cdot )$ as was shown in Lemma 1, the Galerkin orthogonality (12), and the boundedness (19) of $a_h(\cdot ,\cdot )$ on $V_{0h,*} \times V_{0h}$, we can derive the following estimate

$$\begin{aligned} \mu _e \Vert v_h - u_h\Vert _h ^2&\le a_h(v_h - u_h,v_h - u_h) = a_h(v_h - u, v_h - u_h) \\&\le \mu _b \Vert v_h - u\Vert _{h,*}\Vert v_h - u_h\Vert _{h}. \end{aligned}$$

Therefore, we can proceed as follows:

$$\begin{aligned} \Vert u - u_h\Vert _h&\le \Vert u - v_h \Vert _h + \Vert v_h - u_h\Vert _h \\&\le \Vert u - v_h \Vert _{h} + (\mu _b/\mu _e)\Vert v_h - u\Vert _{h,*} \\&\le (1 + \mu _b/\mu _c) \Vert v_h - u\Vert _{h,*}, \end{aligned}$$

which proves the following Cea-like Lemma providing an estimate of the discretization error wrt the norm $\Vert \cdot \Vert _h$ by the best approximation error wrt to the $\Vert \cdot \Vert _{h,*}$ norm.

Lemma 3

Under the assumption made above, the discretization error wrt the $\Vert \cdot \Vert _h$ norm can be estimated from above by the best approximation error wrt to the $\Vert \cdot \Vert _{h,*}$ norm as follows:

$$\begin{aligned} \Vert u - u_h\Vert _h \le (1 + \frac{\mu _b}{\mu _c}) \inf _{v_h \in V_{0h}}\Vert u-v_h \Vert _{h,*}. \end{aligned}$$

(20)

Theorem 1

Let the solution $u \in H^{1,0}_0(Q)$ of the parabolic initial-boundary value model problem (2) belong to $V= H_{0,\underline{0}}^{1,1}(Q)$ globally, and patch-wise to $H^{s_n}(Q_n)$ with some $s_n \ge 2$ for $n=1,\ldots ,N$, and let $u_h \in V_{0h}$ be the solution to the IgA scheme (8) with fixed positive $\theta _n$, $n=1,\ldots ,N$, defined as in Lemma 1. Then the discretization error estimate

$$\begin{aligned} \Vert u - u_h\Vert _h \le (1 + \frac{\mu _b}{\mu _c})\sum _{n=1}^N c_n h_n^{r_n-1} \Vert u\Vert _{H^{r_n}(Q_n)} \end{aligned}$$

(21)

holds, where $c_n$ are generic positive constants, $r_n = \min \{s_n, p_n+1\}$, and $p_n$ denotes the underlying polynomial degree of the B-splines or NURBS used in patch $Q_n$ with $n=1,\ldots ,N$.

Proof

Let $\varPi _n$ be a projective operator from $L_2(Q_n)$ to $V_{0n}$ that delivers optimal approximation error estimates in the $L_2(Q_n)$ and $H^1(Q_n)$ norms, see, e.g., [1] or [12]. We define the multi-patch projective operator $(\varPi _h u)|_{Q_n}=\varPi _n(u|_{Q_n})$ for all $n=1,\ldots ,N$. Employing the approximation results given in [1] or [12], we can easily derive the approximation error estimates

$$\begin{aligned} \Vert \nabla _x(u-\varPi _{n}u)\Vert ^2_{L^2(Q_n)} + \theta _n\,h_n \Vert \partial _t(u-\varPi _{n}u)\Vert ^2_{L^2(Q_n)} \le C_{1} h_n^{2(r_n-1)}\Vert u\Vert ^2_{{H}^{r_n}{(Q_n)}} \end{aligned}$$

(22)

and

$$\begin{aligned} \theta _n\,h_n^{-1} \Vert u-\varPi _{n}u\Vert ^2_{L^2(Q_n)} \le C_{2} h_n^{2r_n-1}\Vert u\Vert ^2_{{H}^{r_n}{(Q_n)}}, \end{aligned}$$

(23)

with positive generic constants $C_1$ and $C_2$. Based on the previous estimates and the trace inequality

$$\begin{aligned} \Vert u\Vert ^2_{L^2(\partial Q_n)} \le C_{tr}h_{n}^{-1}\big (\Vert u\Vert _{L^2(Q_n)}^2+h_{n}^2\, |u|_{H^{1}(Q_n)}^2\big ), \end{aligned}$$

we can further show the approximation error estimate

$$\begin{aligned} \Vert u-\varPi _{n} u\Vert ^2_{L^2(\partial Q_n)} \le C_3 h^{2r_n-1}\Vert u\Vert ^2_{H^{r_n}(Q_n)} \end{aligned}$$

that in turn implies

$$\begin{aligned} \Vert u-\varPi _{n} u\Vert ^2_{L^2(\varSigma _n)} \le C_4 h^{2r_n-1}\Vert u\Vert ^2_{H^{r_n}(Q_n)} \end{aligned}$$

(24)

and

$$\begin{aligned} \nonumber \frac{1}{2} \Vert \,[|u-\varPi _{h}u|]\,\Vert ^2_{L_2(\varSigma _{n-1})} \le&\Vert u_n-\varPi _{n} u\Vert ^2_{L^2(\varSigma _{n-1})} + \Vert u_{n-1}-\varPi _{n-1} u\Vert ^2_{L^2(\varSigma _{n-1})} \\ \le C_{4} h_n^{2r_n-1}\Vert u\Vert ^2_{{H}^{r_n}{(Q_n)}} +&C_{5} h_{n-1}^{2r_{n-1}-1}\Vert u\Vert ^2_{{H}^{r_{n-1}}{(Q_{n-1})}}, \end{aligned}$$

(25)

with positive generic constants $C_4$ and $C_5$. Finally, gathering together (22), (23), (24) and (25), summing over all space-time patches $Q_n$, and recalling definition (17), we get the approximation error estimate

$$\begin{aligned} \Vert u-\varPi _h u\Vert _{h,*} \le \sum _{n=1}^{N}c_n h_n^{r_n-1}\Vert u\Vert _{H^{r_n}(Q_n)}. \end{aligned}$$

(26)

Inserting (26) into (20) yields the desired result. $\blacksquare$

Remark 1

The above estimate has been derived under the isotropic assumption $u\in H^{s_n}(Q_n)$ for the patch-wise regularity of the solution. In the forthcoming work [6], we will present a discretization error analysis for the case when the solution can have anisotropic regularity behavior with respect to time and space.

5 Matrix Representation and Space-Time Multigrid Solvers

We now assume that the IgA map $\mathbf {\Phi }_n: \widehat{Q}\rightarrow Q_n$ preserves the tensor product structure of the IgA basis functions $\varphi _{n,i} = \widehat{\varphi }_{n,i} \circ \mathbf {\Phi }_n^{-1}$. Hence, for each time slice $Q_n$, $n=1,\ldots ,N$, the basis functions $\varphi _{n,i}$, $i \in \mathcal {I}_n$, can be rewritten in the form

$$\begin{aligned} \varphi _{n,i}(x,t) = \phi _{n,i_x}(x) \psi _{n,i_t}(t), \text { with } i_x \in \{1,\ldots ,N_{n,x}\} \text { and } i_t \in \{1,\ldots ,N_{n,t}\}, \end{aligned}$$

where $\text {dim}(V_{0n}) = N_{n,x} N_{n,t}$. Using this representation in the definition of the bilinear form $a_n(\cdot ,\cdot )$, we obtain

$$\begin{aligned}&\int _{Q_n} \Big (\partial _{t} \varphi _{n,j} (\varphi _{n,i} + \theta _n h_n \partial _{t} \varphi _{n,i}) + \nabla _x \varphi _{n,j} \cdot \nabla _x \varphi _{n,i} + \theta _n h_n \nabla _x \varphi _{n,j} \cdot \nabla _x \partial _{t} \varphi _{n,i}\Big )\,dxdt \\&\quad + \int _{\varSigma _{n-1}} [|\varphi _{n,j}|] \, \varphi _{n,i} \,dx \\&= \Big [\int _{\varOmega } \phi _{n,j_x} \phi _{n,i_x} \, dx\Big ] \Big [\int _{t_{n-1}}^{t_n} \partial _{t}\psi _{n,j_t} (\psi _{n,i_t} + \theta _n h_n \partial _{t}\psi _{n,i_t}) \,dt\Big ] \\&\quad + \Big [\int _{\varOmega } \nabla _x\phi _{n,j_x} \cdot \nabla _x\phi _{n,i_x} \,dx\Big ] \Big [\int _{t_{n-1}}^{t_n} \psi _{n,j_t} (\psi _{n,i_t} + \theta _n h_n \partial _{t}\psi _{n,i_t}) \,dt\Big ] \\&\quad + \Big [\int _{\varOmega }\phi _{n-1,k_x} \phi _{n,i_x}\,dx\Big ] \Big [\big (\psi _{n,j_t}(t_{n-1}) - \psi _{n-1,k_t}(t_{n-1})\big ) \psi _{n,i_t}(t_{n-1}) \Big ] \\&= {\mathbf {M}}_{n,x}[i_x,j_x] {\mathbf {K}}_{n,t}[i_t, j_t] + {\mathbf {K}}_{n,x}[i_x,j_x] {\mathbf {M}}_{n,t}[i_t, j_t] - {\widetilde{\mathbf {M}}}_{n,x}[i_x,k_x] {\mathbf {N}}_{n,t}[i_t, k_t], \end{aligned}$$

with the standard mass and stiffness matrices wrt to space

$$\begin{aligned} {\mathbf {M}}_{n,x}[i_x,j_x]&:= \int _{\varOmega } \phi _{n,j_x} \phi _{n,i_x} \, dx, \qquad {\mathbf {K}}_x[i_x,j_x] := \int _{\varOmega } \nabla _x\phi _{n,j_x} \cdot \nabla _x\phi _{n,i_x} \,dx,\\ {\widetilde{\mathbf {M}}}_{n,x}[i_x,k_x]&:= \int _{\varOmega }\phi _{n-1,k_x} \phi _{n,i_x}\,dx, \end{aligned}$$

and the corresponding matrices wrt to time

$$\begin{aligned} {\mathbf {K}}_{n,t}[i_t, j_t]&:= \int _{t_{n-1}}^{t_n} \partial _{t}\psi _{n,j_t} (\psi _{n,i_t} + \theta _n h_n \partial _{t}\psi _{n,i_t}) \,dt + \psi _{n,j_t}(t_{n-1}) \psi _{n,i_t}(t_{n-1}), \\ {\mathbf {M}}_{n,t}[i_t, j_t]&:= \int _{t_{n-1}}^{t_n} \psi _{n,j_t} (\psi _{n,i_t} + \theta _n h_n \partial _{t}\psi _{n,i_t}) \,dt,\\ {\mathbf {N}}_{n,t}[i_t, k_t]&:= \psi _{n-1,k_t}(t_{n-1}) \psi _{n,i_t}(t_{n-1}). \end{aligned}$$

With this computations, we have shown that the Galerkin matrix $\mathbf {L}_h$ can be rewritten in the block form

$$\begin{aligned} \mathbf {L}_h = \begin{pmatrix} \mathbf {A}_1 \\ -\mathbf {B}_2 &{} \mathbf {A}_2 \\ &{}&{} \ddots &{} \ddots \\ &{}&{}&{} -\mathbf {B}_N &{} \mathbf {A}_N \end{pmatrix}, \end{aligned}$$

with the matrices $\mathbf {A}_n := {\mathbf {M}}_{n,x} \otimes {\mathbf {K}}_{n,t} + {\mathbf {K}}_{n,x} \otimes {\mathbf {M}}_{n,t}$ for $n = 1,\ldots ,N$, and $\mathbf {B}_n := {\widetilde{\mathbf {M}}}_{n,x} \otimes {\mathbf {N}}_{n,t}$ for $n = 2,\ldots ,N$.

Thus, the linear system (15) can sequentially be solved from one time slice $Q_{n-1}$ to the next time slice $Q_{n}$, where a linear system with the system matrix $\mathbf {A}_n$ has to be solved. This can be done, for example, by means of an algebraic multigrid method, which was already successfully used for the single patch case in [10]. More advanced solvers for the linear system (15) are given by space-time multigrid methods, which allow parallelization wrt to space and time. The problem given in (15) perfectly fits into the framework of space-time multigrid methods introduced in [5].

6 Numerical Results

In this section, we demonstrate the proposed method for the spatial computational domain $\varOmega =(0,1)^3$ and $T=1$, i.e., $Q = (0,1)^4$. We consider the manufactured solution $u(x,t) = \sin (\pi x_1)\sin (\pi x_2)\sin (\pi x_3)\sin (\pi t)$ for problem (1). Here, we only show results for the case $p_n=1$, $n=1,\ldots ,N$, i.e., for lowest order splines. We start with an initial space-time mesh consisting of 64 elements in space and one time slice ($N=1$) which is subdivided into 8 elements. We then apply uniform refinement wrt space, and increase the number of time slices by a factor of two. At the same time, we keep the number of subdivision per time slice constant. For each time slice, we always use the same parameter $\theta _n = 0.2$. Using the results of Sect. 5, we can generate the linear system (15) very fast. Moreover, we can apply the solver technology given in [10] to solve the linear system in parallel wrt space and time. In detail, we use the space-time multigrid method (1 V-cycle in time and space, and 1 hypre algebraic multigrid (AMG) V-cycle in space) as a preconditioner for the GMRES method, and we stop the iterations until a relative residual error of $10^{-8}$ is reached. In Table 1, we show the convergence of this approach with respect to the $L_2(Q)$-norm. We observe the optimal convergence rate of 2. The number of cores used for the hypre AMG is denoted by $c_x$, whereas $c_t$ gives the number of cores with respect to time. Overall, we use $c_x c_t$ cores, which is also listed in this table. We also observe quite small iteration numbers. Finally, we can solve the global linear system with $9\,777\,365\,568$ unknowns in less than 5 min on a massively parallel machine with $131\,072$ cores. The weak parallel efficiency corresponding to the last two rows of Table 1 is about $50\%$. This is due to the massive space parallelization of the AMG that is not especially adapted to the problem under consideration. All computations have been performed on the Vulcan BlueGene/Q at Livermore, U.S.A, MFEM.

Table 1. Convergence results for the space-time IgA as well as iteration numbers and solving times for the parallel space-time multigrid preconditioned GMRES method.

7 Summary and Conclusion

We presented new time-upwind stabilized multi-patch space-time IgA schemes for parabolic IBVP, derived a priori discretization error estimates, and provided fast generation and solution methods, which can be efficiently implemented on massively parallel computers as the first numerical results show. This space-time method can be generalized to more general parabolic evolution problems.