Starting from (
19) we now derive the (semi-)discrete dispersion relation of Parareal for the one dimensional linear advection diffusion problem
$$\begin{aligned} u_t + U u_x = \nu u_{xx}. \end{aligned}$$
(25)
First, assume a plane wave solution in space
$$\begin{aligned} u(x,t) = \hat{u}(t) e^{i \kappa x} \end{aligned}$$
(26)
with wave number
\(\kappa \) so that (
25) reduces to the initial value problem
$$\begin{aligned} \hat{u}_t(t) = -\left( U i \kappa + \nu \kappa ^2 \right) \hat{u}(t) =: \delta (\kappa , U, \nu ) \hat{u}(t) \end{aligned}$$
(27)
with initial value
\(\hat{u}(0) = 1\). Integrating (
27) from
\(t=0\) to
\(t=T\) in one step gives
$$\begin{aligned} \hat{u}_{T} = R(\delta , T) \hat{u}_0 \end{aligned}$$
(28)
where
R is the stability function of the employed method. Now assume that the approximation of
\(\hat{u}\) is a discrete plane wave so that the solution at the end of the
nth time slice is given by
$$\begin{aligned} \hat{u}_n = e^{-i \omega n \Delta T}. \end{aligned}$$
(29)
Inserting this in (
28) gives
$$\begin{aligned} e^{-i \omega T} \hat{u}_0 = R \hat{u}_0 \Rightarrow \omega = i \frac{\log (R)}{T}. \end{aligned}$$
(30)
For
R in polar coordinates, that is
\(R = \left| R \right| \exp (i \theta )\) with
\(\theta = \texttt {angle}(R)\), we get
$$\begin{aligned} \omega = i \left( \log (\left| R \right| ) + i \theta \right) T^{-1}. \end{aligned}$$
(31)
The exact integrator, for example, would read
$$\begin{aligned} R_{\text {exact}} = e^{\delta (\kappa ,U,\nu ) T}. \end{aligned}$$
(32)
Using (
30) to compute the resulting frequency yields
\(\omega = i \delta (k, U, \nu )\) and retrieves the continuous plane wave solution
$$\begin{aligned} u(x,T) = \hat{u}_T e^{i \kappa x} = e^{-\nu \kappa ^2 T} e^{i \kappa \left( x - U T \right) } \end{aligned}$$
(33)
of (
25). It also reproduces the dispersion relation of the continuous system
$$\begin{aligned} \omega = i \frac{\log (R)}{T} = i \delta (\kappa , U, \nu ) = U \kappa - i \nu \kappa ^2. \end{aligned}$$
(34)
However, if we use an approximate stability function
R instead, we get some approximate
\(\omega = \omega _{r} + i \omega _{i}\) with
\(\omega _{r}, \omega _{i} \in \mathbb {R}\). The resulting semi-discrete solution becomes
$$\begin{aligned} u_j^n = e^{-i \omega t_n} e^{i \kappa x} = e^{\omega _i t_n} e^{i \kappa \left( x - \frac{\omega _{r}}{\kappa } t_n \right) }. \end{aligned}$$
(35)
Therefore,
\(\omega _{r}/\kappa \) governs the propagation speed of the solution while
\(\omega _{i}\) governs the growth or decay in amplitude. Consequently,
\(\omega _{r}/\kappa \) is referred to as
phase velocity while
\(\exp (\omega _i)\) is called
amplification factor. In the continuous case, the phase speed is equal to
U and the amplification factor equal to
\(e^{-\nu \kappa ^2}\). Note that for (
25) the exact phase speed should be independent of the wave number
\(\kappa \). However, the discrete phase speed of a numerical method often will change with
\(\kappa \), thus introducing numerical dispersion. Also note that for
\(\nu > 0\) higher wave numbers decay faster because the amplification factor decreases rapidly as
\(\kappa \) increases.
3.1 Normalisation
The update function R for Parareal in Eq. (
19) denotes not an update over [0, 1] but over
\([0,T_P]\) where
\(T_P = P\) is the number of processors. A phase speed of
\(\omega _{r}/\kappa = 1.0\), for example, indicates a wave that travels across a whole interval [0, 1] during the step. If scaled up to an interval [0,
P], the corresponding phase speed would become
\(\omega _{r}/\kappa = P\) instead.
This enlarged range of values causes problems with the complex logarithm in (
30). As an example, take the stability function of the exact propagator (
32). Analytically, the identity
$$\begin{aligned} \omega = i \frac{R}{T} = i \delta (\kappa , U, \nu ) \frac{T}{T} = i \delta (\kappa , U, \nu ) \end{aligned}$$
(36)
holds, resulting in the correct dispersion relation (
34) of the continuous system. However, depending on the values of
\(\kappa \),
U,
T and
\(\nu \), this identity is not necessarily satisfied when computing the complex logarithm using
np.log
. For example, for
\(\kappa = 2\),
\(U = 1\),
\(\nu = 0\) and
\(T>0\), the exact stability function is
\(R = e^{-2 i T}\). In Python, we obtain for
\(T=1\)$$\begin{aligned} \texttt {1j} * \texttt {np.log}(e^{-2 i})/1 = 2 = \kappa \end{aligned}$$
(37)
but for
\(T=2\) we obtain
$$\begin{aligned} \texttt {1j} * \texttt {np.log}(e^{-4 i})/2 \approx -1.1416 \ne \kappa \end{aligned}$$
(38)
and so identity (
36) is not fulfilled. The reason is that the logarithm of a complex number is not unique and so
np.log
returns only
a complex logarithm but not necessarily the right one in terms of the dispersion relation.
To circumvent this problem, we “normalise” the update
R for Parareal to [0, 1]. To this end, decompose
$$\begin{aligned} R = \root P \of {R} \cdot \ldots \cdot \root P \of {R} \end{aligned}$$
(39)
where
\(\root P \of {R}\) corresponds to the propagation over [0, 1] instead of [0,
P]. Since there are
P many roots
\(\root P \of {R}\), we have to select the right one. First, we use the
zeros
function of
numPy
to find all
P complex roots
\(z_i\) of
$$\begin{aligned} z^n - R = 0. \end{aligned}$$
(40)
Then, we select as root
\(\root P \of {R}\) the value
\(z_i\) that satisfies
$$\begin{aligned} \left| \theta (\root P \of {R}) - \theta _\mathrm{targ} \right| = \min _{p=1,\ldots ,P} \left| \theta (z_p) - \theta _\mathrm{targ} \right| \end{aligned}$$
(41)
where
\(\theta \) is the
angle
function and
\(\theta _\mathrm{targ}\) some target angle, which we still need to define.
We compute
\(\omega \) and the resulting phase speed and amplification factor for a range of wave numbers
\(0 \le \kappa _1 \le \kappa _2 \le \cdots \le \kappa _{N} \le \pi \). For
\(\kappa _1\),
\(\theta _\mathrm{targ}\) is set to the angle of the frequency
\(\omega \) computed from the analytic dispersion relation. After that,
\(\theta _\mathrm{targ}\) is set to the angle of the root selected for the previous value of
\(\kappa \). The rationale is that small changes in
\(\kappa \) should only result in small changes of frequency and phase so that
\(\theta (\omega _{i-1}) \approx \theta (\omega _i)\) if the increment between wave numbers is small enough. From the selected root
\(\root P \of {R}\) we then compute
\(\omega \) using (
30), the resulting discrete phase speed and amplification factor and the target angle
\(\theta _\mathrm{targ}\) for the next wave number.