Keywords

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

The very rapidly increasing number of cores in state-of-the-art supercomputers fuels both the need for and the interest in novel numerical algorithms inherently designed to feature concurrency. In addition to the mature field of space-parallel approaches (e.g. domain decomposition techniques), time-parallel methods that allow concurrency along the temporal dimension are now an increasingly active field of research, although first ideas, like in [12], go back several decades. A prominent and widely studied algorithm in this area is Parareal, introduced in [10], which has the advantage that one can couple and reuse classical time-stepping schemes in an iterative fashion to parallelize in time. However, there also exist a number of other approaches, e.g. the “parallel implicit time algorithm” (PITA) from [5], the “parallel full approximation scheme in space and time” (PFASST) from [4] or “revisionist integral deferred corrections” (RIDC) from [3] to name a few. Parareal in particular and temporal parallelism in general has been considered early as an addition to spatial parallelism in order to extend strong scaling limits, see [11]. Efficacy of this approach in large-scale parallel simulations on hundreds of thousands of cores has been demonstrated for the PFASST algorithm in [14].

For Parareal, multiple works exist that demonstrate its efficiency for diffusion problems: Gander and Vandewalle [9] prove super-linear convergence of Parareal for the standard 1D heat equation. A more general theorem showing super-linear convergence for nonlinear ODEs is proven by Gander and Hairer [7], while [2] presents a convergence theorem for linear parabolic PDEs with constant coefficients. The present paper investigates the effect of space- and time-dependent coefficients in the two-dimensional heat equation on the convergence of Parareal. This is done by means of numerical examples, including one that shows how convergence of Parareal can be estimated by the maximum singular value of a Parareal iteration matrix.

2 Parareal

To match the numerical examples in Sect. 3, the presentation of Parareal given here starts with an initial value problem

$$\displaystyle{ My_{t}(t) = f(y(t),t),\ y(0) = b \in \mathbb{R}^{d},\ t \in [0,T], }$$
(1)

with a mass matrix M and right-hand side f arising from a finite element discretization of a partial differential equation. Let (t n ) n = 0 N with t 0 = 0 and t N  = T be a decomposition of [0, T] into N so-called time-slices [t n , t n+1] which, for the sake of simplicity, are assumed to be of equal length here. Furthermore, let y n be an approximation to the solution at t n , that is y n  ≈ y(t n ).

Denote by \(\mathcal{F}\) a “fine”, computationally expensive and accurate integration method with a time step δ t (e.g. a higher-order Runge-Kutta method) and by \(\mathcal{G}\) a “coarse”, computationally cheap and probably inaccurate method with a time step Δ t ≫ δ t (e.g. implicit Euler). Assume here that the constant length of the time-slices is a multiple of both δ t and Δ t, so that the fine as well as the coarse method can integrate over one time-slice using a fixed integer number of time-steps. Denote the result of integrating over the slice [t n , t n+1], starting from an initial value y at t n , using the fine or coarse method as \(\mathcal{F}(y,t_{n+1},t_{n})\) and \(\mathcal{G}(y,t_{n+1},t_{n})\) respectively. Serial integration using the fine method would then correspond to computing

$$\displaystyle{ y_{n+1} = \mathcal{F}(y_{n},t_{n+1},t_{n}),\ n = 0,\ldots,N - 1, }$$
(2)

step-by-step with y 0: = b. Instead, Parareal computes the iteration given by

$$\displaystyle{ y_{n+1}^{k+1} = \mathcal{G}(y_{ n}^{k+1},t_{ n+1},t_{n}) + \mathcal{F}(y_{n}^{k},t_{ n+1},t_{n}) -\mathcal{G}(y_{n}^{k},t_{ n+1},t_{n}) }$$
(3)

where the evaluation of the fine method over the N time-slices can be distributed over N processors (see [10] for details). The iteration converges to the serial fine solution as k → N. Speedup can be achieved if \(\mathcal{G}\) is sufficiently cheap compared to \(\mathcal{F}\) and if the iteration converges in K ≪ N iterations. Therefore, rapid convergence is critical for Parareal to be efficient. In the examples below, the defect

$$\displaystyle{ d^{k}:=\max _{ i=0,\ldots,N}\left \|y_{i} - y_{i}^{k}\right \|_{ \infty } }$$
(4)

between the solution provided by the Parareal iteration (3) after k iterations and the serial fine solution (2) is used to measure convergence.

3 Heat Equation with Non-constant Coefficients

The test problem used here to study the convergence of Parareal for non-constant coefficients is the two-dimensional heat equation

$$\displaystyle{ u_{t}(x,y,t) =\nu (t)\nabla \cdot \left (a(x,y)\nabla u(x,y,t)\right ) }$$
(5)

on a square Ω = [0, 1]2. The initial values are given by

$$\displaystyle{ u_{0}(x,y) =\exp \left [-\left ((x - 0.5)^{2} + (y - 0.5)^{2}\right )/\sigma ^{2}\right ],\ \sigma = 0.35, }$$
(6)

and the problem is run until T = 4. 0. The interval [0, T] is divided into N = 40 time-slices and an implicit Euler method with \(\varDelta t = 1/100\) is used for \(\mathcal{G}\) and a third order RadauIIA(3) method with \(\delta t = 1/200\) for \(\mathcal{F}\). The spatial domain Ω is divided into three “strips”

$$\displaystyle\begin{array}{rcl} \varOmega _{1}& =& [0,x_{0}) \times [0,1],{}\end{array}$$
(7)
$$\displaystyle\begin{array}{rcl} \varOmega _{2}& =& [x_{0},x_{0} + w) \times [0,1],{}\end{array}$$
(8)
$$\displaystyle\begin{array}{rcl} \varOmega _{3}& =& [x_{0} + w,1] \times [0,1],{}\end{array}$$
(9)

and a different constant value for a is prescribed on every strip, that is

$$\displaystyle{ a(x,y) = \left \{\begin{array}{c @{ \: \ }l} a_{1}\:\ &(x,y) \in \varOmega _{1} \\ a_{2}\:\ &(x,y) \in \varOmega _{2} \\ a_{3}\:\ &(x,y) \in \varOmega _{3}. \end{array} \right. }$$
(10)

Furthermore, the effect of varying the width w of the middle strip Ω 2 is investigated. Conforming triangle meshes aligned with the strips Ω i are generated for values of \(w \in \left \{0.2,0.1,0.05,0.02\right \}\). Then, for every value of w, a number of uniform refinement steps is performed in order to produce meshes of comparable mesh width. After refinement, the minimum element sizes for the different values of w range from h min = 0. 01 to h min = 0. 005 and the maximum element sizes from h max = 0. 02 to h max = 0. 035, so that the resolutions are comparable. All experiments reported below use linear finite elements, but preliminary tests not documented here suggest that the results are not significantly affected by the use of higher-order FEM. Homogeneous Dirichlet boundary conditions are employed. Simulations are run with \(a_{1} = a_{3} = 0.01\) fixed and \(a_{2} \in \left \{0.01,1.0,100\right \}\), resulting in ratios \(\varDelta a = a_{2}/a_{3} = a_{2}/a_{1} \in \left \{1,100,10000\right \}\).

3.1 Space-Dependent Coefficients

First, set ν ≡ 1 in order to study only the effect of spatially varying coefficients. Figure 1 shows the resulting convergence of Parareal for the different values of Δ a and w = 0. 2 (left) and w = 0. 02 (right). Convergence in the cases with jumping coefficients is slightly slower, but the effect is very small. Also, the reduction in convergence speed seems to be rather independent of the magnitude of the jump in the diffusion coefficient: In both plots, the lines for Δ a = 100 and Δ a = 10, 000 are more or less indistinguishable.

Fig. 1
figure 1

Defect d k between Parareal and the serial fine solution versus the iteration number k depending on the magnitude of the jump in the diffusion coefficient from Ω 1, Ω 3 to Ω 2

Full size image

Convergence of Parareal is utterly oblivious to the width w of the middle strip Ω 2: When plotting the defects for fixed Δ a and different values of w, the resulting data points all essentially coincide so that the corresponding plots are rather uninteresting and are therefore omitted.

3.2 Space- and Time-Dependent Coefficients

To investigate the effect of a time-dependent diffusion coefficient on the convergence of Parareal, fix the strip width to w = 0. 2 and the coefficient jump to Δ a = 100. Furthermore, use the following three different profiles for the time-dependent diffusion coefficient ν:

$$\displaystyle\begin{array}{rcl} \nu (t)& = 1\quad & \text{(\textquotedblleft constant\textquotedblright )},{}\end{array}$$
(11)
$$\displaystyle\begin{array}{rcl} \nu (t)& = \frac{1} {2}\left (1 +\cos \left (\alpha \frac{\pi } {2}t\right )\right )\quad & \text{(\textquotedblleft cosine\textquotedblright )},{}\end{array}$$
(12)
$$\displaystyle\begin{array}{rcl} \nu (t)& = \frac{1} {2}\left (1 + \text{erf}(\alpha (t - 2))\right )\quad & \text{(\textquotedblleft erf\textquotedblright )}.{}\end{array}$$
(13)

Initial value and boundary conditions are set as described above. Two sets of simulations are performed, one with α = 1 corresponding to a very slowly changing ν and one with α = 10 corresponding to a more rapid change. The resulting convergence of Parareal is shown in Fig. 2. In both cases, the slow as well as the fast varying one, Parareal’s convergence is only marginally affected by the space- and time-dependent diffusion coefficients. The resulting defects are slightly larger than for the reference case and the difference is a little more pronounced for α = 10, but the overall effect is not drastic: In the fast varying case with the error function profile (13), Parareal requires only a single additional iteration compared to the constant reference in order to reach the same defect level.

Fig. 2
figure 2

Defect d k of Parareal versus the iteration number k for different time-dependent ν-profiles with Δ a = 100, α = 1 (left) and α = 10 (right)

Full size image

3.3 Error Bound from Singular Values

Parareal can be considered as a fixed point iteration, see e.g. [1] or [6] for more detailed explanations. For ν ≡ 1 and the linear problem considered here, the action of the propagators \(\mathcal{F}\) and \(\mathcal{G}\) can be expressed as multiplication by matrices G or F. Then, running the fine or coarse method over all N time-slices can be expressed as inversion of size Nd × Nd matrices

$$\displaystyle{ \mathbf{M}_{f} = \left [\begin{array}{*{10}c} I & \ldots \\ -F &I & \\ & \ddots &\ddots&\\ & &&-F &I \end{array} \right ],\quad \mathbf{M}_{g} = \left [\begin{array}{*{10}c} I & \ldots \\ -G &I & \\ & \ddots &\ddots&\\ & &&-G&I \end{array} \right ], }$$
(14)

so that computing the fine solution through (2) corresponds to a block-wise solution of M f y = b with y = (y 0, …, y N )T and b = (b, 0, …, 0)T. The Parareal iteration (3) can then be written as the preconditioned fixed point iteration

$$\displaystyle{ \mathbf{M}_{g}\mathbf{y}^{k+1} = \left (\mathbf{M}_{ g} -\mathbf{M}_{f}\right )\mathbf{y}^{k} + \mathbf{b}, }$$
(15)

where inverting M g corresponds to running the coarse method. A straightforward computation shows that the iteration matrix \(\mathbf{I} -\mathbf{M}_{g}^{-1}\mathbf{M}_{f}\) is nilpotent and thus that its spectral radius is zero, corresponding to the well-known fact that Parareal always converges to the fine solution after N iterations, see e.g. [9] (although Parareal won’t provide any speedup in this case). A bound for the convergence rate can be obtained by computing the maximum singular value instead. In order to keep the size of the iteration matrix manageable, the example studied here uses only the w = 0. 2 geometry with a coarser grid with h min = 0. 04, h max = 0. 068 and only N = 20 time-slices. The maximum singular values of the iteration matrix are computed with Matlab’s svds function and are \(\sigma _{\mathrm{max}} \approx 0.162\) for Δ a = 1 and \(\sigma _{\mathrm{max}} \approx 0.163\) for Δ a = 10, 000: The minimal difference gives an additional indication that the coefficient jump should not influence Parareal’s convergence. Figure 3 shows the convergence rates of Parareal for this example for Δ a = 1, i.e. with a constant coefficient (left) and with Δ a = 10, 000 (right), as well as the estimate \(d^{0} \times (\sigma _{\mathrm{max}})^{k}\) resulting from the maximum singular value. In both cases, actual convergence is a little better than expected but \(\sigma _{\mathrm{max}}\) gives a reasonable estimate. Again, the jumping coefficients affect Parareal’s convergence only marginally. Note that interpreting variants like the “Krylov-subspace-enhanced Parareal”, introduced in [8] and studied further in [13], as a non-stationary fixed point iteration could be an interesting approach for a mathematical analysis.

Fig. 3
figure 3

Convergence of Parareal and error estimate from the largest singular value of the Parareal iteration matrix (dashed line)

Full size image

4 Conclusions

The paper presents a numerical study of the convergence behavior of the time-parallel Parareal method for the heat equation with space- and time-dependent coefficients. It demonstrates that the good convergence of Parareal for diffusive problems is only marginally affected by both jumps in the diffusion coefficients and a diffusion coefficient that changes in time. For linear problems, Parareal can be interpreted as a preconditioned fixed point iteration and, at least for small enough problems, the iteration matrix and its maximum singular value can be computed numerically. An example is shown that demonstrates that the largest singular value gives a reasonable estimate for the convergence of Parareal. Extending the analysis presented here to more complicated cases e.g. in three dimensions with complicated geometries, with coefficient jumps not aligned with the mesh or cases that also include advection would be an interesting direction of future research.