# Local Fourier Analysis of a Space-Time Multigrid Method for DG-SEM for the
Linear Advection Equation

Lea M. Versbach1∗, Philipp Birken1, Viktor Linders1, Gregor Gassner2

1Centre for Mathematical Sciences, Numerical Analysis, Lund University, Lund,
Sweden
2Center for Data and Simulation Sciences; Department of Mathematics and
Computer Science
Weyertal 86-90, 50931 Köln, Germany

<EMAIL_ADDRESS>
###### Abstract

In this paper we present a Local Fourier Analysis of a space-time multigrid
solver for a hyperbolic test problem. The space-time discretization is based
on arbitrarily high order discontinuous Galerkin spectral element methods in
time and a first order finite volume method in space. We apply a block Jacobi
smoother and consider coarsening in space-time, as well as temporal coarsening
only. Asymptotic convergence factors for the smoother and the two-grid method
for both coarsening strategies are presented. For high CFL numbers, the
convergence factors for both strategies are $0.5$ for first order, and $0.375$
for second order accurate temporal approximations. Numerical experiments in
one and two spatial dimensions for space-time DG-SEM discretizations of
varying order gives even better convergence rates of around $0.3$ and $0.25$
for sufficiently high CFL numbers.

Keywords: Local Fourier Analysis, Space-Time, Multigrid, Discontinuous
Galerkin Spectral Element Method, Linear Advection Equation
Mathematics Subject Classification 2020: 65M55,65M22,65M60,65T99

##  1 Introduction

Space-time discontinuous Galerkin (DG) discretizations have received increased
attention in recent years. One reason is that they allow for high order
implicit discretizations and parallelization in time [12]. Moreover, new
space-time DG spectral element methods have been constructed [11]. These are
provably entropy stable for hyperbolic conservation laws which is of great
interest in that community. Several authors have studied space-time DG methods
for different equations, for instance hyperbolic problems in [8, 11],
advection-diffusion problems in [23, 25], the Euler equations of gas dynamics
in [30, 32] and nonlinear wave equations in [31].

The philosophy of space-time methods is to treat time as just an additional
dimension [24]. This has several advantages, i.e. moving boundaries can be
treated more easily [27] and parallelization in time is possible [12].
However, the technique also has challenges, since the temporal direction has a
special role. Time always needs to follow a causality principle: a solution
later in time is only determined by a solution earlier in time, never the
other way around.

Several time parallel numerical methods exist, and can be divided into four
groups [12]: Methods based on multiple shooting, methods based on domain
decomposition and waveform relaxation, space-time multigrid methods and direct
time parallel methods. In this article we focus on space-time multigrid
methods, which often scale linearly with the number of unknowns [26].

An analysis tool for multigrid methods is the Local Fourier Analysis (LFA),
introduced in [4]. It can be used to study smoothers and two-grid algorithms.
The technique is based on assuming periodic boundary conditions and
transforming the given problem into the frequency domain using a discrete
Fourier transform. Thus, the LFA can be used as a predictor for asymptotic
convergence rates when considering problems with non-periodic boundary
conditions [10]. The smoothing and asymptotic convergence are both related to
the eigenvalues of the operators for the smoother and the two-grid algorithm.
These operators are very large for space-time discretizations, since the
effective dimension becomes $d+1$ for a $d$-dimensional problem. It is
therefore not feasible to calculate the eigenvalues. When performing an LFA,
the operators are of block diagonal form in the Fourier space, which reduces
the problem to an analysis of so-called Fourier symbols. These are of much
smaller size and make calculations feasible. Multigrid solvers have been
analyzed in the DG context with block smoothers for convection-diffusion
problems in [14, 23, 33] and for elliptic problems in [19, 20]. Space-time MG
methods have been analyzed mostly for parabolic problems [9, 10, 13]. Analysis
of space-time MG algorithms for DG discretizations of advection dominated
flows has been quite limited but can be found for the advection-diffusion
equation or linearized versions of the compressible Euler equations [29, 28]
and for generalized diffusion problems [10].

In this article we use the LFA to analyze a space-time multigrid solver for a
hyperbolic model problem. The analysis is similar to [13], where the authors
considered a one-dimensional heat equation discretized with a finite element
method in space and DG in time. Instead we study the one-dimensional linear
advection equation discretized with a first order finite volume (FV) method in
space and a discontinuous Galerkin spectral element method (DG-SEM) in time.
This results in a fully discrete space-time DG discretization.

Due to the choice of the test problem as well as the spatial discretization we
get complex Fourier symbols, making the analysis more difficult. However, for
large CFL numbers we are able to determine asymptotic smoothing factors
analytically. We use a block Jacobi smoother and compare two different
coarsening strategies: coarsening in both temporal and spatial directions as
well as coarsening in the temporal direction only. The two-grid convergence
factors need to be calculated numerically based on the complex Fourier
symbols. We compare the results of the analysis to numerical convergence rates
for multi-dimensional advection problems with more general boundary
conditions. These experiments are produced using the the Distributed and
Unified Numerics Environment (DUNE), an open source modular toolbox for
solving partial differential equations with grid-based methods as DG, finite
element and finite differences [1, 5, 6, 7].

In section 2 we describe the model problem and the DG space-time
discretization. Moreover, we introduce the multigrid solver and its
components. In section 3 we discuss some preliminaries: the equivalence of
temporal DG-SEM discretizations with upwind flux and Lobatto IIIC Runge-Kutta
methods, stability results, as well as the basic tools needed for the LFA. In
section 4 we derive the Fourier symbols for all elements of the multigrid
iteration: discretization operator, smoother, restriction and prolongation. In
section 5 we analyze the smoothing properties for a block Jacobi smoother to
find an optimal damping parameter. The two-grid asymptotic convergence factors
are calculated in section 6. Numerical results for the advection equation in
one and two dimensions are presented in section 7 and serve as a comparison to
the theoretical results obtained from the LFA. Conclusions are drawn in
section 8.

##  2 Problem Description

The goal of this paper is to analyze a space-time multigrid solver for a
discretized hyperbolic model problem. We consider the one-dimensional linear
advection equation

$\displaystyle u_{t}+au_{x}=0,\leavevmode\nobreak\
(x,t)\in[L,R]\times[0,T]=:\boldsymbol{\Omega}\subset\mathbb{R}^{2}$ (1)

with $a>0$. For the analysis, we need periodic boundary conditions in space
and time.

###  2.1 Discretization

For the analysis we discretize (1) with a space-time DG method with a FV
method in space (which corresponds to one a DG method of order $p_{x}=0$ with
one Legendre-Gauss node, i.e., the midpoint) and variable temporal polynomial
degree $p_{t}$. For the temporal direction, we use a DG-SEM. This is a
specific DG discretization based on the following choices: The solution and
the physical flux function are approximated element-wise by nodal polynomials
using a Lagrangian basis based on Legendre-Gauss-Lobatto (LGL) nodes.
Moreover, integrals are approximated by Gaussian quadrature, which is
collocated with the nodes of the polynomial approximation [21].

To discretize equation (1), we start by dividing $\boldsymbol{\Omega}$ into
space-time elements $[x_{n},x_{n+1}]\times[t_{m},t_{m+1}],\leavevmode\nobreak\
n=1,\dots,N_{x},\leavevmode\nobreak\ m=1,\dots,N$. A weak form on each space-
time element $[x_{n},x_{n+1}]\times[t_{m},t_{m+1}]$ is

$\displaystyle\int_{x_{n}}^{x_{n+1}}\int_{t_{m}}^{t_{m+1}}(u_{t}+au_{x})\psi\text{d}x\text{d}t=0,$

for test functions $\psi$ in a test space $C^{1}(\boldsymbol{\Omega})$.

It is of advantage for the DG-SEM discretization to map the temporal elements
to the reference element $[-1,1]$ using the linear map
$\tau(t)=2\frac{t-t_{m}}{\Delta t}$ with $\Delta t=t_{m+1}-t_{m}$. Then we get
the modified weak form

$\displaystyle\frac{2}{\Delta
t}\int_{x_{n}}^{x_{n+1}}\int_{-1}^{+1}u_{\tau}\psi\text{d}x\text{d}\tau+\int_{x_{n}}^{x_{n+1}}\int_{-1}^{1}au_{x}\psi\text{d}x\text{d}\tau=0.$

Integration by parts in both direction yields

$\displaystyle\frac{2}{\Delta
t}\int_{x_{n}}^{x_{n+1}}(u\psi|_{-1}^{1}-\int_{-1}^{+1}u\psi_{\tau}\text{d}\tau)\text{d}x+a\int_{-1}^{1}(u\psi|_{x_{n}}^{x_{n+1}}-\int_{x_{n}}^{x_{n+1}}u\psi_{\xi}\text{d}x)\text{d}\tau=0.$

We now approximate $u$ on each space-time element
$[x_{n},x_{n+1}]\times[-1,1]$ by polynomials of variable degree $p_{t}$ in
time and constant degree $p_{x}=0$ in space:

$\displaystyle u(x,\tau)=\sum_{i=1}^{N_{t}}u_{ij}\ell_{i}(\tau),$

with $N_{t}=p_{t}+1$ and $j=1,\dots,N_{x}$ volumes in space. For the DG-SEM
discretization, the basis functions $\ell_{i}$ are Lagrange polynomials of
degree $p_{t}$ based on the Legendre-Gauss-Lobatto (LGL) nodes
$\\{\tau_{j}\\}_{i=1}^{N_{t}}$ in $[-1,1]$. We choose $\psi$ from the same
space, thus

$\displaystyle\psi(x,\tau)=\sum_{i=1}^{N_{t}}\psi_{ij}\ell_{i}(\tau),\leavevmode\nobreak\
j=1,\dots,N_{x}.$

Inserting the polynomial approximations gives

$\displaystyle\frac{2}{\Delta
t}\int_{x_{n}}^{x_{n+1}}(u\psi|_{-1}^{1}-\int_{-1}^{+1}u\psi_{\tau}\text{d}\tau)\text{d}x+a\int_{-1}^{1}(u(x_{n+1},\tau)\psi(x_{n+1},\tau)-u(x_{n},\tau))\psi(x_{n},\tau)\text{d}\tau=0.$

Next, we approximate the integrals in time with Gaussian quadrature using the
same LGL nodes $\\{\tau_{i}\\}_{i=1}^{N_{\tau}}$ and weights
$\\{\omega_{i}\\}_{i=1}^{N_{t}}$ as for the basis functions

$\displaystyle\int_{-1}^{1}f(\tau)\text{d}\tau\approx\sum_{i=1}^{N_{t}}\omega_{i}f(\tau_{i}),$

and consider mean values in the spatial direction. This yields

$\displaystyle\frac{2}{\Delta
t}(u^{*}_{N_{t}j}\delta_{iN_{x}}-u^{*}_{1j}\delta_{i1}-\sum_{l=1}^{N_{t}}\omega_{l}\ell_{i}^{\prime}(\tau_{l})u_{lj})+\frac{a\omega_{i}}{\Delta
x}(u^{*}_{i,j}-u^{*}_{i,j-1})=0,\leavevmode\nobreak\
i=1,\dots,N_{t},j=2,\dots,N_{x},$

where we have replaced the boundary terms by numerical flux functions $u^{*}$.
Here, we choose the upwind flux in the spatial and the temporal direction.

We can combine the temporal and spatial discretizations with a tensor product
ansatz. Let us denote the spatial discretization operators by the index $\xi$
and the temporal discretization operators by $\tau$. With the temporal DG-SEM
operators

$\displaystyle\mathbf{M}_{\tau}=\frac{\Delta t}{2}\begin{pmatrix}\omega_{1}\\\
&\ddots\\\ &&\omega_{N_{t}}\end{pmatrix}\in\mathbb{R}^{N_{t}\times
N_{t}},\leavevmode\nobreak\ \mathbf{C}_{\tau}=\begin{pmatrix}0&&1\\\
&\ddots\\\ &&0\end{pmatrix}\in\mathbb{R}^{N_{t}\times
N_{t}},\leavevmode\nobreak\ \mathbf{E}_{N_{t}}=\begin{pmatrix}0\\\ &\ddots\\\
&&0\\\ &&&1\end{pmatrix}\in\mathbb{R}^{N_{t}\times N_{t}},$
$\displaystyle\mathbf{K}_{\tau}=\mathbf{E}_{N_{t}}-\mathbf{D}_{\tau}^{T}\mathbf{M}_{\tau}\in\mathbb{R}^{N_{t}\times
N_{t}},\leavevmode\nobreak\ (\mathbf{D}_{\tau})_{ij}=\frac{2}{\Delta
t}\ell^{\prime}_{j}(\tau_{i}),\leavevmode\nobreak\ i,j=1\dots,N_{t},$ (2)

and the spatial operator

$\displaystyle\mathbf{K}_{\xi}=\frac{a}{\Delta x}\begin{pmatrix}1&&&-1\\\
-1&1&&\\\ &\ddots&\ddots&\\\ &&-1&1\end{pmatrix}\in\mathbb{R}^{N_{x}\times
N_{x}},\leavevmode\nobreak\ \mathbf{I}_{\xi}\in\mathbb{R}^{N_{x}\times
N_{x}},$ (3)

the following linear space-time system has to be solved on each so-called
space-time slab $n$:

$\displaystyle(\mathbf{I}_{\xi}\otimes\mathbf{K}_{\tau}+\mathbf{K}_{\xi}\otimes\mathbf{M}_{\tau})\mathbf{u}^{n+1}=(\mathbf{I}_{\xi}\otimes\mathbf{C}_{\tau})\mathbf{u}^{n},$
(4)

Here, the spatial matrices correspond to the whole domain in space while the
temporal matrices correspond to one DG element in time.

An example for an equidistant space-time grid can be seen in Figure 1. Then
all $N_{x}$ spatial elements and one temporal element $n$ represent one space-
time slab $n=1,\dots,N$, as highlighted gray in the figure.

$space-time\leavevmode\nobreak\ slab$$x$$t$$\Delta t$$\Delta t$$\Delta
t$$\Delta t$$\Delta x$$\Delta x$$\Delta x$$\Delta x$$\Delta x$$\Delta
x$$\Delta x$$\Delta x$$\Delta x$ Figure 1: Equidistant space-time grid in one
spatial dimension.

Let us write the vector of unknowns for the space-time problem as
$\underline{\mathbf{u}}=[\mathbf{u}^{1},\dots,\mathbf{u}^{N}]^{T}\in\mathbb{R}^{NN_{x}N_{t}}$.
The components of $\mathbf{u}^{n}\in\mathbb{R}^{N_{x}N_{t}}$ are given by
$\mathbf{u}^{n}_{j,k}\in\mathbb{R}$, where $n$ denotes the space-time slab,
$j$ is the index for the unknowns in space and $k$ the index for the unknowns
in one time element, i.e. $\mathbf{u}^{n}_{j}\in\mathbb{R}^{N_{t}}$. This
index notation is used throughout this paper for vectors in the space
$\mathbb{R}^{NN_{x}N_{t}}$.

The full space-time system for $N$ space-time slabs on $[0,T]$ can then be
written in block form

$\displaystyle\underline{\mathbf{L}}_{\tau,\xi}\underline{\mathbf{u}}:=\begin{pmatrix}\mathbf{A}_{\tau,\xi}&&&\mathbf{B}_{\tau,\xi}\\\
\mathbf{B}_{\tau,\xi}&\mathbf{A}_{\tau,\xi}\\\ &\ddots&\ddots\\\
&&\mathbf{B}_{\tau,\xi}&\mathbf{A}_{\tau,\xi}\end{pmatrix}\begin{pmatrix}\mathbf{u}^{1}\\\
\mathbf{u}^{2}\\\ \vdots\\\
\mathbf{u}^{N}\end{pmatrix}=\begin{pmatrix}\mathbf{0}\\\ \mathbf{0}\\\
\vdots\\\ \mathbf{0}\end{pmatrix}=:\underline{\mathbf{b}}$ (5)

with

$\displaystyle\mathbf{A}_{\tau,\xi}$
$\displaystyle:=\mathbf{I}_{\xi}\otimes\mathbf{K}_{\tau}+\mathbf{K}_{\xi}\otimes\mathbf{M}_{\tau}\in\mathbb{R}^{N_{x}N_{t}\times
N_{x}N_{t}},$ (6) $\displaystyle\mathbf{B}_{\tau,\xi}$
$\displaystyle:=-\mathbf{I}_{\xi}\otimes\mathbf{C}_{\tau}\in\mathbb{R}^{N_{x}N_{t}\times
N_{x}N_{t}}.$ (7)

and the space-time operator
$\underline{\mathbf{L}}_{\tau,\xi}\in\mathbb{R}^{NN_{t}N_{x}\times
NN_{t}N_{x}}$ and space-time vectors
$\underline{\mathbf{u}},\underline{\mathbf{b}}\in\mathbb{R}^{NN_{x}N_{t}}$.

###  2.2 Multigrid Solver

In the next step, the linear system (5) has to be solved. One method is to
apply a forward substitution w.r.t. the time blocks. This involves inverting
the diagonal blocks in each time step and results in a sequential process.
Instead, we use a space-time multigrid method to solve (5). Multigrid
algorithms consist of three main components: a smoother, intergrid transfer
operators, i.e. prolongation and restriction, and a coarse grid solver. It is
of advantage to study the intergrid transfer operators in space and time
separately due to the special causality principle in the temporal direction.
We consider a geometric multigrid method in space and time. We choose block
Jacobi smoothers with blocks corresponding to one space-time slab since it has
been shown in the case of space-time multigrid methods that pointwise or line-
smoothers, when not chosen carefully, can result in divergent methods [16, 24,
26]. The choice of these blocks follows from the block form of the full space-
time system (5).

Let $\boldsymbol{\Omega}_{\ell}\subset\mathbb{R}^{2}$ be the grid on level
$\ell=0,\dots,M$ with $\ell=0$ the coarsest and $\ell=M$ the finest level. We
denote the number of time slabs on multigrid level $\ell$ by
$N_{\ell_{t}}\in\mathbb{N}$ and the number of spatial elements by
$N_{\ell_{x}}\in\mathbb{N}$. In consequence, on each space-time grid level
$\ell$ the system matrix $\underline{\mathbf{L}}_{\tau_{\ell},\xi_{\ell}}$ is
defined by (3) with $N_{\ell_{x}}$ volumes and the space-time system (5) with
$N_{\ell_{t}}$ time steps.

For the temporal component, restriction and prolongation matrices are defined
using $\mathcal{L}_{2}$ projections,

$\displaystyle\begin{split}\mathbf{R}^{\ell_{t}}_{\ell_{t}-1}&:=\begin{pmatrix}\mathbf{R}_{1}&\mathbf{R}_{2}\\\
&&\mathbf{R}_{1}&\mathbf{R}_{2}\\\ &&&\ddots&\ddots\\\
&&&&\mathbf{R}_{1}&\mathbf{R}_{2}\end{pmatrix}\in\mathbb{R}^{N_{t}N_{\ell_{t}-1}\times
N_{t}N_{\ell_{t}}},\\\
\mathbf{P}_{\ell_{t}}^{\ell_{t}-1}&:=(\mathbf{R}^{\ell_{t}}_{\ell_{t}-1})^{T}\in\mathbb{R}^{N_{t}N_{\ell_{t}}\times
N_{t}N_{\ell_{t}-1}},\end{split}$ (8)

with local prolongation matrices
$\mathbf{R}_{1}^{T}:=\mathbf{M}_{\tau_{\ell}}^{-1}\widetilde{\mathbf{M}}_{\tau_{\ell}}^{1}$
and
$\mathbf{R}_{2}^{T}:=\mathbf{M}_{\tau_{\ell}}^{-1}\widetilde{\mathbf{M}}_{\tau_{\ell}}^{2}$,
see [13], [23]. For basis functions
$\\{\ell_{k}\\}_{k=1}^{N_{t}}\subset\mathbb{P}^{p_{t}}(0,\tau_{\ell})$ on the
fine grid and
$\\{\tilde{\ell}_{k}\\}_{k=1}^{N_{t}}\subset\mathbb{P}^{p_{t}}(0,2\tau_{\ell})$
on the coarse grid, the local projection matrices from the coarse to the fine
grid are defined by

$\displaystyle\widetilde{M}_{\tau_{\ell}}^{1}(k,l):=\int_{0}^{\tau_{\ell}}\tilde{\ell}_{l}(t)\ell_{k}(t)dt,\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\
\widetilde{M}_{\tau_{\ell}}^{2}(k,l):=\int_{\tau_{\ell}}^{2\tau_{\ell}}\tilde{\ell}_{l}(t)\ell_{k}(t-\tau)dt,\leavevmode\nobreak\
k,l=1,\dots,N_{t}.$ (9)

Restriction and prolongation matrices in space are given by agglomeration

$\displaystyle\begin{split}\mathbf{R}^{\ell_{x}}_{\ell_{x}-1}&:=\frac{1}{2}\begin{pmatrix}1&1\\\
&&1&1\\\ &&&\ddots&\ddots\\\
&&&&1&1\end{pmatrix}\in\mathbb{R}^{N_{\ell_{x}-1}\times N_{\ell_{x}}},\\\
\mathbf{P}_{\ell_{x}}^{\ell_{x}-1}&:=(2\mathbf{R}^{\ell_{x}}_{\ell_{x}-1})^{T}\in\mathbb{R}^{N_{\ell_{x}}\times
N_{\ell_{x}-1}}.\end{split}$ (10)

We study two different coarsening strategies: coarsening in space and time,
referred to as full-coarsening and denoted by index $f$, and coarsening in the
temporal direction only, which we refer to as semi-coarsening with index $s$.
Since we are especially interested in the efficiency of the multigrid method
in time, we study a semi-coarsening strategy in this direction.

For the space-time system, restriction and prolongation operators can then be
defined with a tensor product

$\displaystyle(\underline{\mathbf{R}}^{\ell}_{\ell-1})^{s}$
$\displaystyle:=\mathbf{I}_{N_{\ell_{x}}}\otimes\mathbf{R}^{\ell_{t}}_{\ell_{t}-1},\leavevmode\nobreak\
(\underline{\mathbf{R}}^{\ell}_{\ell-1})^{f}:=\mathbf{R}^{\ell_{x}}_{\ell_{x}-1}\otimes\mathbf{R}^{\ell_{t}}_{\ell_{t}-1},$
(11) $\displaystyle(\underline{\mathbf{P}}_{\ell}^{\ell-1})^{s}$
$\displaystyle:=\mathbf{I}_{N_{\ell_{x}}}\otimes\mathbf{P}_{\ell_{t}}^{\ell_{t}-1},\leavevmode\nobreak\
(\underline{\mathbf{P}}_{\ell}^{\ell-1})^{f}:=\mathbf{P}_{\ell_{x}}^{\ell_{x}-1}\otimes\mathbf{P}_{\ell_{t}}^{\ell_{t}-1}.$
(12)

As smoother we choose a damped block Jacobi method

$\displaystyle\underline{\mathbf{u}}^{(k+1)}=\omega_{t}(\underline{\mathbf{D}}_{\tau_{\ell},\xi_{\ell}})^{-1}\underline{\mathbf{b}}+(\underline{\mathbf{I}}_{\tau_{\ell},\xi_{\ell}}-\omega_{t}(\underline{\mathbf{D}}_{\tau_{\ell},\xi_{\ell}})^{-1}\underline{\mathbf{L}}_{\tau_{\ell},\xi_{\ell}})\underline{\mathbf{u}}^{(k)},$
(13)

with damping factor $\omega_{t}$ and block diagonal matrix

$\displaystyle\underline{\mathbf{D}}_{\tau_{\ell},\xi_{\ell}}:=\text{diag}([\mathbf{A}_{\tau_{\ell},\xi_{\ell}},\dots,\mathbf{A}_{\tau_{\ell},\xi_{\ell}}]).$
(14)

Here, the blocks correspond to a space-time slab on the given grid level due
to the block form of the full space-time system (5). The block Jacobi
iteration matrix reads

$\displaystyle\underline{\mathbf{S}}_{\tau_{\ell},\xi_{\ell}}:=\underline{\mathbf{I}}-\omega_{t}(\underline{\mathbf{D}}_{\tau_{\ell},\xi_{\ell}})^{-1}\underline{\mathbf{L}}_{\tau_{\ell},\xi_{\ell}}.$
(15)

With this, the iteration matrices for a two-grid V-cycle with $\nu_{1}$ pre-
and $\nu_{2}$ post-smoothing steps on the fine grid are given by

$\displaystyle\underline{\mathbf{M}}_{\tau_{\ell},\xi_{\ell}}^{s}$
$\displaystyle:=\underline{\mathbf{S}}_{\tau_{\ell},\xi_{\ell}}^{\nu_{2}}\left[\underline{\mathbf{I}}-(\underline{\mathbf{P}}_{\ell}^{\ell-1})^{s}(\underline{\mathbf{L}}_{2\tau_{\ell},\xi_{\ell}})^{-1}(\underline{\mathbf{R}}^{\ell}_{\ell-1})^{s}\underline{\mathbf{L}}_{\tau_{\ell},\xi_{\ell}}\right]\underline{\mathbf{S}}_{\tau_{\ell},\xi_{\ell}}^{\nu_{1}},$
(16) $\displaystyle\underline{\mathbf{M}}_{\tau_{\ell},\xi_{\ell}}^{f}$
$\displaystyle:=\underline{\mathbf{S}}_{\tau_{\ell},\xi_{\ell}}^{\nu_{2}}\left[\underline{\mathbf{I}}-(\underline{\mathbf{P}}_{\ell}^{\ell-1})^{f}(\underline{\mathbf{L}}_{2\tau_{\ell},2\xi_{\ell}})^{-1}(\underline{\mathbf{R}}^{\ell}_{\ell-1})^{f}\underline{\mathbf{L}}_{\tau_{\ell},\xi_{\ell}}\right]\underline{\mathbf{S}}_{\tau_{\ell},\xi_{\ell}}^{\nu_{1}},$
(17)

for semi-coarsening and full-coarsening respectively. Here, it is assumed that
the systems are solved exactly on the coarse grid.

##  3 Preliminaries

In this section we discuss some preliminaries which are needed for the local
Fourier analysis presented in the following sections.

###  3.1 DG-SEM and Lobatto IIIC Methods

We start with the temporal DG-SEM discretization (2.1). Using an upwind flux,
which is a flux to fulfill the temporal causality principle, the DG-SEM
discretization in time for the linear test equation

$\displaystyle u_{t}+\lambda u=0,\leavevmode\nobreak\
t\in[0,T],\leavevmode\nobreak\ u(0)=u_{0},\leavevmode\nobreak\ \lambda\geq 0,$
(18)

reads

$\displaystyle(\mathbf{K}_{\tau}+\lambda\mathbf{M}_{\tau})\mathbf{u}^{n+1}=\mathbf{C}_{\tau}\mathbf{u}^{n}.$
(19)

One can show that the scheme is equivalent to a specific Runge-Kutta time-
stepping method:

######  Theorem 3.1 ([3, 17]).

The DG-SEM (19) with $p_{t}+1$ Legendre-Gauss-Lobatto nodes is equivalent to
the $(p_{t}+1)$-stage Runge-Kutta scheme Lobatto IIIC.

Here, equivalence is referred to the solution of the unknowns in the end of
each element assuming the resulting systems are solved exactly.

With the help of Theorem 3.1 some stability results for the temporal
discretization can be drawn.

######  Theorem 3.2 ([18, 22]).

For $s\in\mathbb{N}$ the $s$-stage Lobatto IIIC scheme is of order $2s-1$ and
its stability function $R(z)$ is given by the $(s-2,s)$-Padé approximation of
the exponential function $e^{z}$. The method is $L$-stable and furthermore
algebraically stable, thus B-stable and A-stable.

######  Corollary 3.3.

The stability function $R(z)$ of the DG-SEM (19) with $p_{t}+1\in\mathbb{N}$
Legendre-Gauss-Lobatto nodes, $p_{t}\geq 1$, is given by the
$(p_{t}-1,p_{t}+1)$-Padé approximation to the exponential function $e^{z}$.

###### Proof.

By Theorem 3.1 DG-SEM is equivalent to the Lobatto IIIC method. Thus, both
methods have the same stability function $R(z)$. By Theorem 3.2 the stability
function is given by the $(p_{t}-1,p_{t}+1)$-Padé approximation to the
exponential function $e^{z}$. ∎

The Padé approximant for the exponential function can be calculated directly.

######  Theorem 3.4 ([18]).

The $(k,m)$-Padé approximant

$\displaystyle r_{km}(z)=\frac{p_{km}(z)}{q_{km}(z)}$

of the exponential function $e^{z}$ is given by

$\displaystyle p_{km}(z)$
$\displaystyle=1+\sum_{j=1}^{k}\frac{(k+m-j)!\,k!}{(k+m)!\,(k-j)!}\cdot\frac{z^{j}}{j!},$
$\displaystyle q_{km}(z)$
$\displaystyle=1+\sum_{j=1}^{m}\frac{(k+m-j)!\,m!}{(k+m)!\,(m-j)!}\cdot\frac{(-z)^{j}}{j!}.$

With the help of the stability function $R$, the eigenvalues of the
discretization matrix (19) can be calculated.

######  Lemma 3.5 ([13]).

For $\lambda\in\mathbb{C}$ the spectrum of the matrix
$(\mathbf{K}_{\tau}+\lambda\mathbf{M}_{\tau})^{-1}\mathbf{C}_{\tau}\in\mathbb{C}^{N_{t}\times
N_{t}}$ is given by

$\displaystyle\sigma((\mathbf{K}_{\tau}+\lambda\mathbf{M}_{\tau})^{-1}\mathbf{C}_{\tau})=\\{0,R(-\lambda\tau)\\}$

where $R(z)$ is the stability function of the DG time stepping scheme, see
Corollary 3.3.

These results are used for the smoothing analysis in section 5.

###  3.2 Definitions and Notation for the Local Fourier Analysis

In this section we present the basic tools needed to perform a local Fourier
analysis for the multigrid solver as presented in section 2.2. For a more
detailed description of this technique we refer to [2, 15].

First we define the Fourier modes and frequencies.

######  Definition 3.6 ([34]).

The function

$\displaystyle\boldsymbol{\varphi}(\theta_{k}):=[\varphi_{1}(\theta_{k}),\dots,\varphi_{N}(\theta_{k})]^{T},\leavevmode\nobreak\
\varphi_{j}(\theta_{k}):=e^{\mathrm{i}j\theta_{k}},\leavevmode\nobreak\
j=1,\dots,N,\leavevmode\nobreak\ N\in\mathbb{N},$

is called Fourier mode with frequencies

$\displaystyle\theta_{k}\in\Theta:=\left\\{\frac{2k\pi}{N}:k=1-\frac{N}{2},\dots,\frac{N}{2}\right\\}\subset(-\pi,\pi].$

The frequencies can be separated into low and high frequencies

$\displaystyle\Theta^{low}:=\Theta\cap\left(-\frac{\pi}{2},\frac{\pi}{2}\right],\leavevmode\nobreak\
\Theta^{high}:=\Theta\cap\left(\left(-\pi,-\frac{\pi}{2}\right]\cup\left(\frac{\pi}{2},\pi\right]\right].$

In this paper we consider frequencies on a two-dimensional space-time domain.
Given the set of space-time frequencies

$\displaystyle\Theta_{\ell_{x},\ell_{t}}:=\\{(\theta_{x},\theta_{t}):\theta_{x}\in\Theta_{\ell_{x}},\leavevmode\nobreak\
\theta_{t}\in\Theta_{\ell_{t}}\\}\subset(-\pi,\pi]^{2},$

low and high frequencies are defined as

$\displaystyle\Theta_{\ell_{x},\ell_{t}}^{high,s}$
$\displaystyle:=\Theta_{\ell_{x},\ell_{t}}\setminus\Theta_{\ell_{x},\ell_{t}}^{low,s}\leavevmode\nobreak\
\leavevmode\nobreak\ \text{ for }\leavevmode\nobreak\ \leavevmode\nobreak\
\Theta_{\ell_{x},\ell_{t}}^{low,s}:=\Theta_{\ell_{x},\ell_{t}}\cap(-\pi,\pi]\times\left(-\frac{\pi}{2},\frac{\pi}{2}\right],$
(20) $\displaystyle\Theta_{\ell_{x},\ell_{t}}^{high,f}$
$\displaystyle:=\Theta_{\ell_{x},\ell_{t}}\setminus\Theta_{\ell_{x},\ell_{t}}^{low,f}\leavevmode\nobreak\
\leavevmode\nobreak\ \text{ for }\leavevmode\nobreak\ \leavevmode\nobreak\
\Theta_{\ell_{x},\ell_{t}}^{low,f}:=\Theta_{\ell_{x},\ell_{t}}\cap\left(-\frac{\pi}{2},\frac{\pi}{2}\right]^{2},$
(21)

for semi-coarsening in time and full space-time coarsening respectively. In
Figure 2 the ranges for the frequencies in the space-time domain are
visualized for both coarsening strategies.

$\theta_{x}$$\theta_{t}$$-\pi$$\pi$-$\pi$$\pi$-$\frac{\pi}{2}$$\frac{\pi}{2}$$\Theta^{\text{high,s}}$$\Theta^{\text{high,s}}$$\Theta^{\text{low,s}}$

$\theta_{x}$$\theta_{t}$$-\pi$$\pi$-$\pi$$\pi$-$\frac{\pi}{2}$$\frac{\pi}{2}$-$\frac{\pi}{2}$$\frac{\pi}{2}$$\Theta^{\text{high,f}}$$\Theta^{\text{low,f}}$

Figure 2: Low and high frequencies for semi coarsening (left) and full
coarsening (right)

With this, the discrete Fourier transform reads:

######  Theorem 3.7 (Discrete Fourier transform [34]).

Let $\underline{\mathbf{u}}\in\mathbb{R}^{N_{t}N_{\ell_{x}}N_{\ell_{t}}}$ for
$N_{t},N_{\ell_{x}},N_{\ell_{t}}\in\mathbb{N}$, and assume that $N_{\ell_{x}}$
and $N_{\ell_{t}}$ are even. The vector $\underline{\mathbf{u}}$ can be
represented as

$\displaystyle\underline{\mathbf{u}}=\sum_{\theta_{x}\in\Theta_{\ell_{x}}}\sum_{\theta_{t}\in\Theta_{\ell_{t}}}\underline{\boldsymbol{\psi}}(\theta_{x},\theta_{t}),$

where
$\underline{\boldsymbol{\psi}}(\theta_{x},\theta_{t})\in\mathbb{C}^{N_{t}N_{\ell_{x}}N_{\ell_{t}}}$
consists of the vectors

$\displaystyle\boldsymbol{\psi}^{n}_{j}(\theta_{x},\theta_{t}):=\mathbf{U}(\theta_{x},\theta_{t})\boldsymbol{\Phi}^{n}_{j}(\theta_{x},\theta_{t})\in\mathbb{C}^{N_{t}},\leavevmode\nobreak\
n=1,\dots,N_{\ell_{t}},\leavevmode\nobreak\ j=1,\dots,N_{\ell_{x}},$

and the vector
$\boldsymbol{\Phi}^{n}_{j}(\theta_{x},\theta_{t})\in\mathbb{C}^{N_{t}}$ has
elements

$\displaystyle\Phi^{n}_{j,l}(\theta_{x},\theta_{t}):=\varphi_{n}(\theta_{t})\varphi_{j}(\theta_{x}),\leavevmode\nobreak\
l=1,\dots,N_{t}.$

Moreover, we define the coefficient matrix as

$\displaystyle\mathbf{U}(\theta_{x},\theta_{t}):=\text{diag}(\hat{u}_{1},\dots,\hat{u}_{N_{t}})\in\mathbb{C}^{N_{t}\times
N_{t}},$

with coefficients

$\displaystyle\hat{u}_{l}:=\frac{1}{N_{\ell_{x}}}\frac{1}{N_{\ell_{t}}}\sum_{j=1}^{N_{\ell_{x}}}\sum_{n=1}^{N_{\ell_{t}}}u^{n}_{j,l}\varphi_{j}(-\theta_{x})\varphi_{n}(-\theta_{t}),\leavevmode\nobreak\
l=1,\dots,N_{t}.$

Then, the linear space of Fourier modes can be defined.

######  Definition 3.8.

Consider the frequencies $\theta_{x}\in\Theta_{\ell_{x}}$ and
$\theta_{t}\in\Theta_{\ell_{t}}$ and the vector
$\boldsymbol{\Phi}^{n}_{j}(\theta_{x},\theta_{t})$ as in Theorem 3.7. Then the
linear space of Fourier modes with frequencies $(\theta_{x},\theta_{t})$ is
defined as

$\displaystyle\Psi_{\ell_{x},\ell_{t}}(\theta_{x},\theta_{t})$
$\displaystyle:=\text{span}\\{\underline{\boldsymbol{\Phi}}(\theta_{x},\theta_{t})\\}$
$\displaystyle:=\\{\underline{\boldsymbol{\psi}}(\theta_{x},\theta_{t})\in\mathbb{C}^{N_{t}\cdot
N_{\ell_{x}}\cdot
N_{\ell_{t}}}:\boldsymbol{\psi}^{n}_{j}(\theta_{x},\theta_{t}):=\mathbf{U}\boldsymbol{\Phi}^{n}_{j}(\theta_{x},\theta_{l}),$
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \text{for}\leavevmode\nobreak\
n=1,\dots,N_{\ell_{t}},\leavevmode\nobreak\
j=1,\dots,N_{\ell_{x}}\leavevmode\nobreak\ \text{and}\leavevmode\nobreak\
\mathbf{U}\in\mathbb{C}^{N_{t}\times N_{t}}\\}.$

With the result from the next theorem it suffices to consider low frequencies.

######  Theorem 3.9 ([26]).

Let
$\underline{\mathbf{u}}=[\mathbf{u}^{1},\dots,\mathbf{u}^{N_{{\ell}_{t}}}]^{T}\in\mathbb{R}^{N_{t}N_{{\ell}_{x}}N_{{\ell}_{t}}}$
and assume that $N_{{\ell}_{x}}$ and $N_{\ell_{t}}$ are even numbers. Then the
vector $\underline{\mathbf{u}}$ can be written as

$\displaystyle\underline{\mathbf{u}}=\sum_{(\theta_{x},\theta_{t})\in\Theta_{{\ell}_{x},{\ell}_{t}}^{low,f}}\left(\underline{\boldsymbol{\psi}}(\theta_{x},\theta_{t})+\underline{\boldsymbol{\psi}}(\gamma(\theta_{x}),\theta_{t})+\underline{\boldsymbol{\psi}}(\theta_{x},\gamma(\theta_{t}))+\underline{\boldsymbol{\psi}}(\gamma(\theta_{x}),\gamma(\theta_{t}))\right),$

with the shifting operator

$\displaystyle\gamma(\theta):=\begin{cases}\theta+\pi,&\theta<0,\\\
\theta-\pi,&\theta\geq 0,\end{cases}$

and
$\underline{\boldsymbol{\psi}}(\theta_{x},\theta_{t})\in\mathbb{C}^{N_{t}N_{\ell_{x}}N_{\ell_{t}}}$
as in Lemma 3.7.

Since $\underline{\boldsymbol{\psi}}(\theta_{x},\theta_{t})$ consists of the
vectors
$\boldsymbol{\psi}_{j}^{n}(\theta_{x},\theta_{t})=\mathbf{U}\boldsymbol{\Phi}_{j}^{n}(\theta_{x},\theta_{t})$,
which itself build the vector
$\underline{\boldsymbol{\Phi}}(\theta_{x},\theta_{t})$, the previous theorem
implies that
$\underline{\mathbf{u}}=[\mathbf{u}^{1},\dots,\mathbf{u}^{N_{{\ell}_{t}}}]^{T}$
can be written as a linear combination of the low frequency vectors

$\displaystyle\\{\underline{\boldsymbol{\Phi}}(\theta_{x},\theta_{t}),\underline{\boldsymbol{\Phi}}(\gamma(\theta_{x}),\theta_{t}),\underline{\boldsymbol{\Phi}}(\theta_{x},\gamma(\theta_{t})),\underline{\boldsymbol{\Phi}}(\gamma(\theta_{x}),\gamma(\theta_{t}))\\}.$

Thus, four fine grid modes get aliased to one coarse grid mode. In the
following it suffices therefore to only consider low frequencies and use the
shifting operator $\gamma:\Theta_{\ell}^{low}\rightarrow\Theta_{\ell}^{high}$.
We can therefore define a new Fourier space, based on low frequencies only:

######  Definition 3.10.

For $N_{t},N_{{\ell}_{x}},N_{{\ell}_{t}}$ consider the vector
$\underline{\boldsymbol{\psi}}(\theta_{x},\theta_{t})\in\mathbb{C}^{N_{t}N_{{\ell}_{x}}N_{{\ell}_{t}}}$
for $(\theta_{x},\theta_{t})\in\Theta_{{\ell}_{x},{\ell}_{t}}^{low,f}$ as in
Lemma 3.7. The linear space of low frequency harmonics is defined as

$\displaystyle\mathcal{E}_{{\ell}_{x},{\ell}_{t}}(\theta_{x},\theta_{t})$
$\displaystyle:=\text{span}\\{\underline{\boldsymbol{\Phi}}(\theta_{x},\theta_{t}),\underline{\boldsymbol{\Phi}}(\gamma(\theta_{x}),\theta_{t}),\underline{\boldsymbol{\Phi}}(\theta_{x},\gamma(\theta_{t})),\underline{\boldsymbol{\Phi}}(\gamma(\theta_{x}),\gamma(\theta_{t}))\\}$
$\displaystyle=\\{\underline{\boldsymbol{\psi}}(\theta_{x},\theta_{t})\in\mathbb{C}^{N_{t}\cdot
N_{{\ell}_{x}}\cdot
N_{{\ell}_{t}}}:\boldsymbol{\psi}^{n}_{j}(\theta_{x},\theta_{t})=\mathbf{U}_{1}\boldsymbol{\Phi}^{n}_{j}(\theta_{x},\theta_{t})$
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\
+\mathbf{U}_{2}\boldsymbol{\Phi}^{n}_{j}(\gamma(\theta_{x}),\theta_{t})+\mathbf{U}_{3}\boldsymbol{\Phi}^{n}_{j}(\theta_{x},\gamma(\theta_{t}))+\mathbf{U}_{4}\boldsymbol{\Phi}^{n}_{j}(\gamma(\theta_{x}),\gamma(\theta_{t})),$
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\
n=1,\dots,N_{{\ell}_{t}},\leavevmode\nobreak\
j=1,\dots,N_{{\ell}_{x}}\leavevmode\nobreak\ \text{and}\leavevmode\nobreak\
\mathbf{U}_{1},\mathbf{U}_{2},\mathbf{U}_{3},\mathbf{U}_{4}\in\mathbb{C}^{N_{t}\times
N_{t}}\\}.$

Moreover, we can define the Fourier space for the semi-coarsening strategy.

######  Definition 3.11 (Fourier space, semi-coarsening).

For $N_{t},N_{\ell_{x}},N_{\ell_{t}-1}\in\mathbb{N}$ and
$(\theta_{x},\theta_{t})\in\Theta_{\ell_{x},\ell_{t}}^{low,f}$ consider
$\underline{\boldsymbol{\Phi}}(\theta_{x},\theta_{t})\in\mathbb{C}^{N_{t}N_{\ell_{x}}N_{\ell_{t}-1}}$
as in Lemma 3.7. We define the linear space with frequencies
$(\theta_{x},2\theta_{t})$ as

$\displaystyle\Psi_{\ell_{x},\ell_{t}-1}(\theta_{x},2\theta_{t})$
$\displaystyle:=\text{span}\\{\underline{\boldsymbol{\Phi}}^{\ell_{x},\ell_{t}-1}(\theta_{x},2\theta_{t}),\underline{\boldsymbol{\Phi}}^{\ell_{x},\ell_{t}-1}(\gamma(\theta_{x}),2\theta_{t})\\}$
$\displaystyle=\\{\underline{\boldsymbol{\psi}}^{\ell_{x},\ell_{t}-1}(\theta_{x},2\theta_{t})\in\mathbb{C}^{N_{t},N_{\ell_{x}},N_{\ell_{t}-1}}:$
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\
\boldsymbol{\psi}^{n,\ell_{x},\ell_{t}-1}_{j}(\theta_{x},2\theta_{t})=\mathbf{U}_{1}\boldsymbol{\Phi}^{n,\ell_{x},\ell_{t}-1}_{j}(\theta_{x},2\theta_{t})$
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\
+\mathbf{U}_{2}\boldsymbol{\Phi}^{n,\ell_{x},\ell_{t}-1}_{j}(\gamma(\theta_{x}),2\theta_{t})\text{
for }n=1,\dots,N_{\ell_{t}}-1,$ $\displaystyle\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ j=1,\dots,N_{\ell_{x}},\leavevmode\nobreak\
\mathbf{U}_{1},\mathbf{U}_{2}\in\mathbb{C}^{N_{t}\times N_{t}}\\}.$

One key property of the LFA is the shifting equality, which is used
extensively when deriving the Fourier symbols of the operators in the next
section.

######  Lemma 3.12 ([24]).

Let $\theta_{x}\in\Theta_{\ell_{x}}$, $\theta_{t}\in\Theta_{\ell_{t}}$ and
$\underline{\boldsymbol{\psi}}(\theta_{x},\theta_{t})\in\Psi_{\ell_{x},\ell_{t}}(\theta_{x},\theta_{t})$.
Then the following shifting equalities hold:

$\displaystyle\boldsymbol{\psi}^{n-1}_{j}(\theta_{x},\theta_{t})=e^{-\mathrm{i}\theta_{t}}\boldsymbol{\psi}^{n}_{j}(\theta_{x},\theta_{t}),\leavevmode\nobreak\
n=2,\dots,N_{\ell_{t}}$
$\displaystyle\boldsymbol{\psi}^{n}_{j-1}(\theta_{x},\theta_{t})=e^{-\mathrm{i}\theta_{x}}\boldsymbol{\psi}^{n}_{j}(\theta_{x},\theta_{t}),\leavevmode\nobreak\
j=2,\dots,N_{\ell_{x}}.$

##  4 Fourier Symbols

The first step of the local Fourier analysis is to derive the Fourier symbols
of all operators in the MG iteration (17) and (16), i.e. of the system matrix,
smoother, restriction and prolongation. These symbols are also referred to as
formal eigenvalues [26] since they are derived by multiplying the operators by
the vector $\underline{\boldsymbol{\psi}}(\theta_{x},\theta_{t})$ from Theorem
3.7.

We start with the Fourier symbol of the system matrix (5).

######  Lemma 4.1 (Fourier symbol of
$\underline{\mathbf{L}}_{\tau_{\ell},\xi_{\ell}}$).

For $\theta_{x}\in\Theta_{\ell_{x}}$ and $\theta_{t}\in\Theta_{\ell_{t}}$ we
consider the vector
$\underline{\boldsymbol{\psi}}(\theta_{x},\theta_{t})\in\Psi_{\ell_{x},\ell_{t}}(\theta_{x},\theta_{t})$.
For

$\displaystyle\boldsymbol{\mathcal{L}}_{\tau_{\ell},\xi_{\ell}}(\theta_{x},\theta_{t}):=-e^{-\mathrm{i}\theta_{t}}\mathbf{C}_{\tau_{\ell}}+\mathbf{K}_{\tau_{\ell}}+\frac{a}{\Delta
x}(-e^{-\mathrm{i}\theta_{x}}+1)\mathbf{M}_{\tau_{\ell}}\in\mathbb{C}^{N_{t}\times
N_{t}}$

it holds that

$\displaystyle(\underline{\mathbf{L}}_{\tau_{\ell},\xi_{\ell}}\underline{\boldsymbol{\psi}}(\theta_{x},\theta_{t}))^{n}_{j}=\boldsymbol{\mathcal{L}}_{\tau_{\ell},\xi_{\ell}}(\theta_{x},\theta_{t})\boldsymbol{\psi}^{n}_{j}(\theta_{x},\theta_{t}),$

for $n=2,\dots,N_{\ell_{t}},\leavevmode\nobreak\ j=2,\dots,N_{\ell_{x}}-1$ and
we call
$\boldsymbol{\mathcal{L}}_{\tau_{\ell},\xi_{\ell}}(\theta_{x},\theta_{t})\in\mathbb{C}^{N_{t}\times
N_{t}}$ the Fourier symbol of
$\underline{\mathbf{L}}_{\tau_{\ell},\xi_{\ell}}\in\mathbb{C}^{N_{\ell_{t}}N_{t}N_{\ell_{x}}\times
N_{\ell_{t}}N_{t}N_{\ell_{x}}}$.

###### Proof.

With Lemma 3.12 we get for
$\underline{\boldsymbol{\psi}}(\theta_{x},\theta_{t})\in\Psi_{\ell_{x},\ell_{t}}(\theta_{x},\theta_{t})$

$\displaystyle(\underline{\mathbf{L}}_{\tau_{\ell},\xi_{\ell}}\underline{\boldsymbol{\psi}}(\theta_{x},\theta_{t}))^{n}$
$\displaystyle=\mathbf{B}_{\tau_{\ell},\xi_{\ell}}\boldsymbol{\psi}^{n-1}(\theta_{x},\theta_{t})+\mathbf{A}_{\tau_{\ell},\xi_{\ell}}\boldsymbol{\psi}^{n}(\theta_{x},\theta_{t})$
$\displaystyle=(e^{-\mathrm{i}\theta_{t}}\mathbf{B}_{\tau_{\ell},\xi_{\ell}}+\mathbf{A}_{\tau_{\ell},\xi_{\ell}})\boldsymbol{\psi}^{n}(\theta_{x},\theta_{t}),\leavevmode\nobreak\
n=2,\dots,N_{\ell_{t}}.$

Thus, we have to study the product of
$\mathbf{A}_{\tau_{\ell},\xi_{\ell}}=\mathbf{I}_{\xi_{\ell}}\otimes\mathbf{K}_{\tau_{\ell}}+\mathbf{K}_{\xi_{\ell}}\otimes\mathbf{M}_{\tau_{\ell}}$
and
$\mathbf{B}_{\tau_{\ell},\xi_{\ell}}=-\mathbf{I}_{\xi_{\ell}}\otimes\mathbf{C}_{\tau_{\ell}}$
with the vector $\boldsymbol{\psi}^{n}(\theta_{x},\theta_{t})$:

$\displaystyle(\mathbf{A}_{\tau_{\ell},\xi_{\ell}}\boldsymbol{\psi}^{n}(\theta_{x},\theta_{t}))_{j,l}$
$\displaystyle=\sum_{i=1}^{N_{{\ell}_{x}}}\sum_{k=1}^{N_{t}}I_{\xi_{\ell}}(j,i)K_{\tau_{\ell}}(l,k)\psi^{n}_{i,k}(\theta_{x},\theta_{t})$
$\displaystyle\leavevmode\nobreak\
+\sum_{i=1}^{N_{h_{\ell}}}\sum_{k=1}^{N_{t}}K_{\xi_{\ell}}(j,i)M_{\tau_{\ell}}(l,k)\psi^{n}_{i,k}(\theta_{x},\theta_{t})$
$\displaystyle=(\mathbf{K}_{\tau_{\ell}}\boldsymbol{\psi}^{n}_{j}(\theta_{x},\theta_{t}))_{l}+\frac{a}{\Delta
x}(-e^{-\mathrm{i}\theta_{x}}+1)(\mathbf{M}_{\tau_{\ell}}\boldsymbol{\psi}^{n}_{j}(\theta_{x},\theta_{t}))_{l}$
$\displaystyle=(\mathbf{K}_{\tau_{\ell}}+\frac{a}{\Delta
x}(-e^{-\mathrm{i}\theta_{x}}+1)\mathbf{M}_{\tau_{\ell}})\boldsymbol{\psi}^{n}_{j}(\theta_{x},\theta_{t}))_{l},$

and

$\displaystyle(\mathbf{B}_{\tau_{\ell},\xi_{\ell}}\boldsymbol{\psi}^{n}(\theta_{x},\theta_{t}))_{j,l}$
$\displaystyle=-\sum_{i=1}^{N_{{\ell}_{x}}}\sum_{k=1}^{N_{t}}I_{\xi_{\ell}}(j,i)C_{\tau_{\ell}}(l,k)\psi^{n}_{i,k}(\theta_{x},\theta_{t})$
$\displaystyle=-\sum_{k=1}^{N_{t}}C_{\tau_{\ell}}(l,k)\psi^{n}_{j,k}(\theta_{x},\theta_{t})=-(\mathbf{C}_{\tau_{\ell}}\boldsymbol{\psi}^{n}_{j}(\theta_{x},\theta_{t}))_{l},$

for $j=2,\dots,N_{{\ell}_{x}}-1$ and $l=1,\dots,N_{t}$. Then

$\displaystyle(\underline{\mathbf{L}}_{\tau_{\ell},\xi_{\ell}}\underline{\boldsymbol{\psi}}(\theta_{x},\theta_{t}))^{n}_{j}=(-e^{-\mathrm{i}\theta_{t}}\mathbf{C}_{\tau_{\ell}}+\mathbf{K}_{\tau_{\ell}}+\frac{a}{\Delta
x}(-e^{-\mathrm{i}\theta_{x}}+1)\mathbf{M}_{\tau_{\ell}})\boldsymbol{\psi}^{n}_{j}(\theta_{x},\theta_{t}),$

and thus

$\displaystyle\boldsymbol{\mathcal{L}}_{\tau_{\ell},\xi_{\ell}}=-e^{-\mathrm{i}\theta_{t}}\mathbf{C}_{\tau_{\ell}}+\mathbf{K}_{\tau_{\ell}}+\frac{a}{\Delta
x}(-e^{-\mathrm{i}\theta_{x}}+1)\mathbf{M}_{\tau_{\ell}}\in\mathbb{C}^{N_{t}\times
N_{t}}.$

∎

With this result we can derive the symbol of the the block Jacobi smother
(13).

######  Lemma 4.2 (Fourier symbol of
$\underline{\mathbf{S}}_{\tau_{\ell},\xi_{\ell}}$).

For $\theta_{x}\in\Theta_{{\ell}_{x}}$ and $\theta_{t}\in\Theta_{{\ell}_{t}}$
we consider the vector
$\underline{\boldsymbol{\psi}}(\theta_{x},\theta_{t})\in\Psi_{{\ell}_{x},{\ell}_{t}}(\theta_{x},\theta_{t})$.
For

$\displaystyle\boldsymbol{\mathcal{S}}_{\tau_{\ell},\xi_{\ell}}(\theta_{x},\theta_{t}):=(1-\omega_{t})\mathbf{I}_{N_{t}}+\omega_{t}e^{-\mathrm{i}\theta_{t}}(\mathbf{K}_{\tau_{\ell}}+\frac{a}{\Delta
x}(-e^{-\mathrm{i}\theta_{x}}+1)\mathbf{M}_{\tau_{\ell}})^{-1}\mathbf{C}_{\tau_{\ell}}\in\mathbb{C}^{N_{t}\times
N_{t}}$

it holds that

$\displaystyle(\underline{\mathbf{S}}_{\tau_{\ell},\xi_{\ell}}\underline{\boldsymbol{\psi}}(\theta_{x},\theta_{t}))^{n}_{j}=\boldsymbol{\mathcal{S}}_{\tau_{\ell},\xi_{\ell}}(\theta_{x},\theta_{t})\boldsymbol{\psi}^{n}_{j}(\theta_{x},\theta_{t})$

for $n=1,\dots,N_{{\ell}_{t}}$, $j=1,\dots,N_{{\ell}_{x}}$ and we call
$\boldsymbol{\mathcal{S}}_{\tau_{\ell},\xi_{\ell}}(\theta_{x},\theta_{t})\in\mathbb{C}^{N_{t}\times
N_{t}}$ the Fourier symbol of
$\underline{\mathbf{S}}_{\tau_{\ell},\xi_{\ell}}\in\mathbb{C}^{N_{\ell_{t}}N_{t}N_{\ell_{x}}\times
N_{\ell_{t}}N_{t}N_{\ell_{x}}}$.

###### Proof.

Let
$\underline{\boldsymbol{\psi}}(\theta_{x},\theta_{t})\in\Psi_{{\ell}_{x},{\ell}_{t}}(\theta_{x},\theta_{t})$.
For fixed $n=1,\dots,N_{{\ell}_{t}}$ and $j=1,\dots,N_{{\ell}_{x}}$ it holds

$\displaystyle(\underline{\mathbf{S}}_{\tau_{\ell},\xi_{\ell}}\underline{\boldsymbol{\psi}}(\theta_{x},\theta_{t}))^{n}_{j}$
$\displaystyle=((\underline{\mathbf{I}}_{N_{t}N_{{\ell}_{x}}N_{{\ell}_{t}}}-\omega_{t}(\underline{\mathbf{D}}_{\tau_{\ell},\xi_{\ell}})^{-1}\underline{\mathbf{L}}_{\tau_{\ell},\xi_{\ell}})\underline{\boldsymbol{\psi}}(\theta_{x},\theta_{t}))^{n}_{j}$
$\displaystyle=(\mathbf{I}_{N_{t}}-\omega_{t}(\hat{\mathbf{A}}_{\tau_{\ell},\xi_{\ell}}(\theta_{x}))^{-1}\boldsymbol{\mathcal{L}}_{\tau_{\ell},\xi_{\ell}}(\theta_{x},\theta_{t}))\boldsymbol{\psi}^{n}_{j}(\theta_{x},\theta_{t})$
$\displaystyle=\boldsymbol{\mathcal{S}}_{\tau_{\ell},\xi_{\ell}}(\theta_{x},\theta_{t})\boldsymbol{\psi}^{n}_{j}(\theta_{x},\theta_{t}),$

with
$\hat{\mathbf{A}}_{\tau_{\ell},\xi_{\ell}}(\theta_{x}):=\mathbf{K}_{\tau_{\ell}}+\frac{a}{\Delta
x}(-e^{-\mathrm{i}\theta_{x}}+1)\mathbf{M}_{\tau_{\ell}}$ derived as in the
previous proof. Moreover,

$\displaystyle(\hat{\mathbf{A}}_{\tau_{\ell},\xi_{\ell}}(\theta_{x}))^{-1}\boldsymbol{\mathcal{L}}_{\tau_{\ell},\xi_{\ell}}(\theta_{x},\theta_{t})$
$\displaystyle=(\mathbf{K}_{\tau_{\ell}}+\frac{a}{\Delta
x}(-e^{-\mathrm{i}\theta_{x}}+1)\mathbf{M}_{\tau_{\ell}})^{-1}$
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\
(-e^{-\mathrm{i}\theta_{t}}\mathbf{C}_{\tau_{\ell}}+\mathbf{K}_{\tau_{\ell}}+\frac{a}{\Delta
x}(-e^{-\mathrm{i}\theta_{x}}+1)\mathbf{M}_{\tau_{\ell}})$
$\displaystyle=\mathbf{I}_{N_{t}}-e^{-\mathrm{i}\theta_{t}}(\mathbf{K}_{\tau_{\ell}}+\frac{a}{\Delta
x}(-e^{-\mathrm{i}\theta_{x}}+1)\mathbf{M}_{\tau_{\ell}})^{-1}\mathbf{C}_{\tau_{\ell}}.$

Thus,

$\displaystyle\boldsymbol{\mathcal{S}}_{\tau_{\ell},\xi_{\ell}}(\theta_{x},\theta_{t})$
$\displaystyle=\mathbf{I}_{N_{t}}-\omega_{t}(\mathbf{I}_{N_{t}}-e^{-\mathrm{i}\theta_{t}}(\mathbf{K}_{\tau_{\ell}}+\frac{a}{\Delta
x}(-e^{-\mathrm{i}\theta_{x}}+1)\mathbf{M}_{\tau_{\ell}})^{-1}\mathbf{C}_{\tau_{\ell}})$
$\displaystyle=(1-\omega_{t})\mathbf{I}_{N_{t}}+\omega_{t}e^{-\mathrm{i}\theta_{t}}(\mathbf{K}_{\tau_{\ell}}+\frac{a}{\Delta
x}(-e^{-\mathrm{i}\theta_{x}}+1)\mathbf{M}_{\tau_{\ell}})^{-1}\mathbf{C}_{\tau_{\ell}}\in\mathbb{C}^{N_{t}\times
N_{t}}.$

∎

With Theorems 3.7 and 3.9 and Lemma 4.1 we get for the system matrix
$\underline{\mathbf{L}}_{\tau_{\ell},\xi_{\ell}}$ and
$(\theta_{x},\theta_{t})\in\Theta_{{\ell}_{x},{\ell}_{t}}^{low,f}$ the
following mapping property:

$\displaystyle\begin{split}\underline{\mathbf{L}}_{\tau_{\ell},\xi_{\ell}}:&\mathcal{E}_{{\ell}_{x},{\ell}_{t}}(\theta_{x},\theta_{t})\to\mathcal{E}_{{\ell}_{x},{\ell}_{t}}(\theta_{x},\theta_{t}),\\\
&\begin{pmatrix}\mathbf{U}_{1}\\\ \mathbf{U}_{2}\\\ \mathbf{U}_{3}\\\
\mathbf{U}_{4}\end{pmatrix}\to\begin{pmatrix}\boldsymbol{\mathcal{L}}_{\tau_{\ell},\xi_{\ell}}(\theta_{x},\theta_{t})\mathbf{U}_{1}\\\
\boldsymbol{\mathcal{L}}_{\tau_{\ell},\xi_{\ell}}(\gamma(\theta_{x}),\theta_{t})\mathbf{U}_{2}\\\
\boldsymbol{\mathcal{L}}_{\tau_{\ell},\xi_{\ell}}(\theta_{x},\gamma(\theta_{t}))\mathbf{U}_{3}\\\
\boldsymbol{\mathcal{L}}_{\tau_{\ell},\xi_{\ell}}(\gamma(\theta_{x}),\gamma(\theta_{t}))\mathbf{U}_{4}\\\
\end{pmatrix}=:\widetilde{\boldsymbol{\mathcal{L}}}_{\tau_{\ell},\xi_{\ell}}(\theta_{x},\theta_{t})\begin{pmatrix}\mathbf{U}_{1}\\\
\mathbf{U}_{2}\\\ \mathbf{U}_{3}\\\ \mathbf{U}_{4}\end{pmatrix},\end{split}$
(22)

with a block diagonal matrix
$\widetilde{\boldsymbol{\mathcal{L}}}_{\tau_{\ell},\xi_{\ell}}(\theta_{x},\theta_{t})\in\mathbb{C}^{4N_{t}\times
4N_{t}}$,
$\boldsymbol{\mathcal{L}}_{\tau_{\ell},\xi_{\ell}}\in\mathbb{C}^{N_{t}\times
N_{t}}$ as defined in Lemma 4.1 and the space of low frequencies
$\mathcal{E}_{{\ell}_{x},{\ell}_{t}}$ as defined in 3.10. Accordingly, we
obtain with Lemma 4.2 for the smoother
$\underline{\mathbf{S}}_{\tau_{\ell},\xi_{\ell}}$ and
$(\theta_{x},\theta_{t})\in\Theta_{{\ell}_{x},{\ell}_{t}}^{low,f}$

$\displaystyle\begin{split}\underline{\mathbf{S}}_{\tau_{\ell},\xi_{\ell}}:&\mathcal{E}_{{\ell}_{x},{\ell}_{t}}(\theta_{x},\theta_{t})\to\mathcal{E}_{{\ell}_{x},{\ell}_{t}}(\theta_{x},\theta_{t}),\\\
&\begin{pmatrix}\mathbf{U}_{1}\\\ \mathbf{U}_{2}\\\ \mathbf{U}_{3}\\\
\mathbf{U}_{4}\end{pmatrix}\to\begin{pmatrix}\boldsymbol{\mathcal{S}}_{\tau_{\ell},\xi_{\ell}}(\theta_{x},\theta_{t})\mathbf{U}_{1}\\\
\boldsymbol{\mathcal{S}}_{\tau_{\ell},\xi_{\ell}}(\gamma(\theta_{x}),\theta_{t})\mathbf{U}_{2}\\\
\boldsymbol{\mathcal{S}}_{\tau_{\ell},\xi_{\ell}}(\theta_{x},\gamma(\theta_{t}))\mathbf{U}_{3}\\\
\boldsymbol{\mathcal{S}}_{\tau_{\ell},\xi_{\ell}}(\gamma(\theta_{x}),\gamma(\theta_{t}))\mathbf{U}_{4}\\\
\end{pmatrix}=:\widetilde{\boldsymbol{\mathcal{S}}}_{\tau_{\ell},\xi_{\ell}}(\theta_{x},\theta_{t})\begin{pmatrix}\mathbf{U}_{1}\\\
\mathbf{U}_{2}\\\ \mathbf{U}_{3}\\\ \mathbf{U}_{4}\end{pmatrix},\end{split}$
(23)

with a block diagonal matrix
$\widetilde{\boldsymbol{\mathcal{S}}}_{\tau_{\ell},\xi_{\ell}}(\theta_{x},\theta_{t})\in\mathbb{C}^{4N_{t}\times
4N_{t}}$ and
$\boldsymbol{\mathcal{S}}_{\tau_{\ell},\xi_{\ell}}\in\mathbb{C}^{N_{t}\times
N_{t}}$ as defined in Lemma 4.2.

Next, we derive the Fourier symbols of the restriction and prolongation
operators.

######  Lemma 4.3 (Fourier symbols of spatial prolongation and restriction).

Consider the spatial restriction and prolongation operators
$\mathbf{R}_{\ell_{x}-1}^{\ell_{x}}\in\mathbb{C}^{N_{{\ell}_{x}-1}\times
N_{{\ell}_{x}}}$ and
$\mathbf{P}^{\ell_{x}-1}_{\ell_{x}}\in\mathbb{C}^{N_{{\ell}_{x}}\times
N_{{\ell}_{x}-1}}$ defined in (10). Let
$\boldsymbol{\varphi}^{\ell_{x}}(\theta_{x})\in\mathbb{C}^{N_{{\ell}_{x}}}$ be
a fine Fourier mode and
$\boldsymbol{\varphi}^{\ell_{x}-1}(2\theta_{x})\in\mathbb{C}^{N_{{\ell}_{x}-1}}$
a coarse Fourier mode for $\theta_{x}\in\Theta_{{\ell}_{x}}^{low}$. Then for
$\mathcal{R}_{\ell_{x}-1}^{\ell_{x}}(\theta_{x}):=\frac{1}{2}(e^{-\mathrm{i}\theta_{x}}+1)$
it holds

$\displaystyle(\mathbf{R}_{\ell_{x}-1}^{\ell_{x}}\boldsymbol{\varphi}^{\ell_{x}}(\theta_{x}))_{j}=\mathcal{R}_{\ell_{x}-1}^{\ell_{x}}(\theta_{x})\varphi_{j}^{\ell_{x}-1}(2\theta_{x}),\leavevmode\nobreak\
j=1,\dots,N_{{\ell}_{x}-1},$

and we call $\mathcal{R}_{\ell_{x}-1}^{\ell_{x}}(\theta_{x})\in\mathbb{C}$ the
Fourier symbol of the restriction operator in space.
For
$\mathcal{P}^{\ell_{x}-1}_{\ell_{x}}(\theta_{x}):=\frac{1}{2}(e^{\mathrm{i}\theta_{x}}+1)$
it holds

$\displaystyle(\mathbf{P}^{\ell_{x}-1}_{\ell_{x}}\boldsymbol{\varphi}^{\ell_{x}-1}(2\theta_{x}))_{i}=\mathcal{P}^{\ell_{x}-1}_{\ell_{x}}(\theta_{x})\varphi_{i}^{\ell_{x}}(\theta_{x})+\mathcal{P}^{\ell_{x}-1}_{\ell_{x}}(\gamma(\theta_{x}))\varphi_{i}^{\ell_{x}}(\gamma(\theta_{x})),\leavevmode\nobreak\
i=1,\dots,N_{{\ell}_{x}}$

and we call $\mathcal{P}^{\ell_{x}-1}_{\ell_{x}}(\theta_{x})\in\mathbb{C}$ the
Fourier symbol of the prolongation operator in space.

###### Proof.

For the restriction operator we get

$\displaystyle(\mathbf{R}_{\ell_{x}-1}^{\ell_{x}}\boldsymbol{\varphi}^{\ell_{x}}(\theta_{x}))_{j}$
$\displaystyle=\frac{1}{2}(\varphi^{\ell_{x}}_{2j-1}(\theta_{x})+\varphi_{2j}^{\ell_{x}}(\theta_{x}))=\frac{1}{2}(e^{-\mathrm{i}\theta_{x}}+1)\varphi_{2j}^{\ell_{x}}(\theta_{x})$
$\displaystyle=\frac{1}{2}(e^{-\mathrm{i}\theta_{x}}+1)\varphi_{j}^{\ell_{x}-1}(2\theta_{x})=\mathcal{R}_{\ell_{x}-1}^{\ell_{x}}(\theta_{x})\varphi_{j}^{\ell_{x}-1}(2\theta_{x}),\leavevmode\nobreak\
j=1,\dots,N_{{\ell}_{x}-1},$

using the shifting Lemma 3.12 and
$\varphi_{2j}^{\ell_{x}}(\theta_{x})=\varphi_{j}^{\ell_{x}-1}(2\theta_{x})$.
For the prolongation operator it holds

$\displaystyle(\mathbf{P}^{\ell_{x}-1}_{\ell_{x}}\boldsymbol{\varphi}^{\ell_{x}-1}(2\theta_{x}))_{2j-1}=\varphi^{\ell_{x}-1}_{j}(2\theta_{x})=\varphi_{2j}^{\ell_{x}}(\theta_{x})=e^{\mathrm{i}\theta_{x}}\varphi_{2j-1}^{\ell_{x}}(\theta_{x}),$

and

$\displaystyle(\mathbf{P}^{\ell_{x}-1}_{\ell_{x}}\boldsymbol{\varphi}^{\ell_{x}-1}(2\theta_{x}))_{2j}=\varphi^{\ell_{x}-1}_{j}(2\theta_{x})=\varphi_{2j}^{\ell_{x}}(\theta_{x}),$

for $j=1,\dots,N_{{\ell}_{x}-1}$, with the same arguments as before. Then

$\displaystyle(\mathbf{P}^{\ell_{x}-1}_{\ell_{x}}\boldsymbol{\varphi}^{\ell_{x}-1}(2\theta_{x}))_{j}=\begin{cases}e^{\mathrm{i}\theta_{x}}\varphi_{j}^{\ell_{x}}(\theta_{x}),&j\text{
odd},\\\ \varphi_{j}^{\ell_{x}}(\theta_{x}),&j\text{ even},\end{cases}$

for $j=1,\dots,N_{{\ell}_{x}}$. Moreover,

$\displaystyle\varphi_{j}^{\ell_{x}}(\gamma(\theta_{x}))=e^{\mathrm{i}j\gamma(\theta_{x})}=\begin{cases}e^{\mathrm{i}j\pi}e^{\mathrm{i}j\theta_{x}},&\theta_{x}<0,\\\
e^{-\mathrm{i}j\pi}e^{\mathrm{i}j\theta_{x}},&\theta_{x}\geq
0,\end{cases}=\begin{cases}-\varphi_{j}^{\ell_{x}}(\theta_{x}),&j\text{
odd},\\\ \varphi_{j}^{\ell_{x}}(\theta_{x}),&j\text{ even},\end{cases}$

and

$\displaystyle\mathcal{P}^{\ell_{x}-1}_{\ell_{x}}(\gamma(\theta_{x}))=\frac{1}{2}(e^{\mathrm{i}\gamma(\theta_{x})}+1)=\frac{1}{2}(-e^{\mathrm{i}\theta_{x}}+1),$

for $j=1,\dots,N_{{\ell}_{x}}$. This implies

$\displaystyle\mathcal{P}^{\ell_{x}-1}_{\ell_{x}}(\theta_{x})\varphi_{j}^{\ell_{x}}(\theta_{x})+\mathcal{P}^{\ell_{x}-1}_{\ell_{x}}(\gamma(\theta_{x}))\varphi_{j}^{\ell_{x}}(\gamma(\theta_{x}))$
$\displaystyle=\frac{1}{2}(e^{\mathrm{i}\theta_{x}}+1)\varphi_{j}^{\ell_{x}}(\theta_{x})+\frac{1}{2}(-e^{\mathrm{i}\theta_{x}}+1)\begin{cases}-\varphi_{j}^{\ell_{x}}(\theta_{x}),&j\text{
odd},\\\ \varphi_{j}^{\ell_{x}}(\theta_{x}),&j\text{ even}\end{cases}$
$\displaystyle=\begin{cases}e^{\mathrm{i}\theta_{x}}\varphi_{j}^{\ell_{x}}(\theta_{x}),&j\text{
odd},\\\ \varphi_{j}^{\ell_{x}}(\theta_{x}),&j\text{
even},\end{cases}=(\mathbf{P}^{\ell_{x}-1}_{\ell_{x}}\boldsymbol{\varphi}^{\ell_{x}-1}(2\theta_{x}))_{j},$

for $j=1,\dots,N_{\ell_{x}}$. ∎

The following five Lemmata from [13] give us the Fourier symbols of the
restriction and prolongation operators for the different coarsening
strategies.

######  Lemma 4.4 (Fourier symbols for temporal prolongation and restriction).

Consider temporal restriction and prolongation operators
$\mathbf{R}^{\ell_{t}}_{\ell_{t}-1}\in\mathbb{C}^{N_{t}N_{\ell_{t}-1}\times
N_{t}N_{\ell_{t}}}$ and
$\mathbf{P}^{\ell_{t}-1}_{\ell_{t}}\in\mathbb{C}^{N_{t}N_{\ell_{t}}\times
N_{t}N_{\ell_{t}-1}}$ as defined in (8). Let
$\boldsymbol{\Phi}^{\ell_{t}}(\theta_{t})\in\mathbb{C}^{N_{t}N_{\ell_{t}}}$ be
a fine Fourier mode and
$\boldsymbol{\Phi}^{\ell_{t}-1}(\theta_{t})\in\mathbb{C}^{N_{t}N_{\ell_{t}-1}}$
a coarse Fourier mode for $\theta_{t}\in\Theta_{\ell_{t}}^{low}$ with elements

$\displaystyle\Phi^{n,\ell_{t}}_{l}(\theta_{t})$
$\displaystyle:=\varphi_{n}(\theta_{t}),\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ l=1,\dots,N_{t},\leavevmode\nobreak\
n=1,\dots,N_{\ell_{t}},$ $\displaystyle\Phi^{n,\ell_{t}-1}_{l}(\theta_{t})$
$\displaystyle:=\varphi_{n}(\theta_{t}),\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ l=1,\dots,N_{t},\leavevmode\nobreak\
n=1,\dots,N_{\ell_{t}-1}.$

Then for
$\boldsymbol{\mathcal{R}}^{\ell_{t}}_{\ell_{t}-1}(\theta_{t}):=e^{-\mathrm{i}\theta_{t}}\mathbf{R}_{1}+\mathbf{R}_{2}\in\mathbb{C}^{N_{t}\times
N_{t}}$, with $\mathbf{R}_{1}$ and $\mathbf{R}_{2}$ defined in (8), it holds

$\displaystyle(\mathbf{R}^{\ell_{t}}_{\ell_{t}-1}\boldsymbol{\Phi}^{\ell_{t}}(\theta_{t}))^{n}=\boldsymbol{\mathcal{R}}^{\ell_{t}}_{\ell_{t}-1}(\theta_{t})\boldsymbol{\Phi}^{n,\ell_{t}-1}(2\theta_{t}),\leavevmode\nobreak\
n=1,\dots,N_{\ell_{t}-1},$

and we call
$\boldsymbol{\mathcal{R}}^{\ell_{t}}_{\ell_{t}-1}(\theta_{t})\in\mathbb{C}^{N_{t}\times
N_{t}}$ the Fourier symbol for the restriction operator in time.
Moreover, for
$\boldsymbol{\mathcal{P}}^{\ell_{t}-1}_{\ell_{t}}(\theta_{t}):=\frac{1}{2}(e^{\mathrm{i}\theta_{t}}\mathbf{R}_{1}^{T}+\mathbf{R}_{2}^{T})\in\mathbb{C}^{N_{t}\times
N_{t}}$ it holds

$\displaystyle(\mathbf{P}^{\ell_{t}-1}_{\ell_{t}}\boldsymbol{\Phi}^{\ell_{t}-1}(2\theta_{t}))^{n}=\boldsymbol{\mathcal{P}}^{\ell_{t}-1}_{\ell_{t}}(\theta_{t})\boldsymbol{\Phi}^{n,\ell_{t}}(\theta_{t})+\boldsymbol{\mathcal{P}}^{\ell_{t}-1}_{\ell_{t}}(\gamma(\theta_{t}))\boldsymbol{\Phi}^{n,\ell_{t}}(\gamma(\theta_{t})),\leavevmode\nobreak\
n=1,\dots,N_{\ell_{t}},$

and we call
$\boldsymbol{\mathcal{P}}^{\ell_{t}-1}_{\ell_{t}}(\theta_{t})\in\mathbb{C}^{N_{t}\times
N_{t}}$ the Fourier symbol for the prolongation in time.

With these results we can get the mapping properties for the semi-restriction
and semi-prolongation operators.

######  Lemma 4.5 (Fourier symbol for restriction, semi-coarsening).

The following mapping property holds for the restriction operator
$(\underline{\mathbf{R}}_{\ell-1}^{\ell})^{s}$:

$\displaystyle(\underline{\mathbf{R}}_{\ell-1}^{\ell})^{s}:\mathcal{E}_{\ell_{x},\ell_{t}}(\theta_{x},\theta_{t})$
$\displaystyle\to\Psi_{\ell_{x},\ell_{t}-1}(\theta_{x},2\theta_{t}),$
$\displaystyle\begin{pmatrix}\mathbf{U}_{1}\\\ \mathbf{U}_{2}\\\
\mathbf{U}_{3}\\\ \mathbf{U}_{4}\end{pmatrix}$
$\displaystyle\mapsto({\widetilde{\boldsymbol{\mathcal{R}}}}_{\ell-1}^{\ell})^{s}(\theta_{t})\begin{pmatrix}\mathbf{U}_{1}\\\
\mathbf{U}_{2}\\\ \mathbf{U}_{3}\\\ \mathbf{U}_{4}\end{pmatrix},$

with

$\displaystyle({\widetilde{\boldsymbol{\mathcal{R}}}}_{\ell-1}^{\ell})^{s}(\theta_{t}):=\begin{pmatrix}\boldsymbol{\mathcal{R}}_{\ell_{t}-1}^{\ell_{t}}(\theta_{t})&0&\boldsymbol{\mathcal{R}}_{\ell_{t}-1}^{\ell_{t}}(\gamma(\theta_{t}))&0\\\
0&\boldsymbol{\mathcal{R}}_{\ell_{t}-1}^{\ell_{t}}(\theta_{t})&0&\boldsymbol{\mathcal{R}}_{\ell_{t}-1}^{\ell_{t}}(\gamma(\theta_{t}))\end{pmatrix}\in\mathbb{C}^{2N_{t}\times
4N_{t}}$

and the Fourier symbol
$\boldsymbol{\mathcal{R}}_{\ell_{t}-1}^{\ell_{t}}(\theta_{t})\in\mathbb{C}^{N_{t}\times
N_{t}}$ as defined in Lemma 4.4.

######  Lemma 4.6 (Fourier symbol of prolongation, semi-coarsening).

The following mapping property holds for the prolongation operator
$(\underline{\mathbf{P}}_{\ell}^{\ell-1})^{s}$:

$\displaystyle(\underline{\mathbf{P}}_{\ell}^{\ell-1})^{s}:\Psi_{\ell_{x},\ell_{t}-1}(\theta_{x},2\theta_{t})$
$\displaystyle\to\mathcal{E}_{\ell_{x},\ell_{t}}(\theta_{x},\theta_{t}),$
$\displaystyle\begin{pmatrix}\mathbf{U}_{1}\\\ \mathbf{U}_{2}\end{pmatrix}$
$\displaystyle\mapsto(\widetilde{\boldsymbol{\mathcal{P}}}_{\ell}^{\ell-1})^{s}(\theta_{t})\begin{pmatrix}\mathbf{U}_{1}\\\
\mathbf{U}_{2}\end{pmatrix},$

with

$\displaystyle(\widetilde{\boldsymbol{\mathcal{P}}}_{\ell}^{\ell-1})^{s}(\theta_{t}):=\begin{pmatrix}\boldsymbol{\mathcal{P}}_{\ell_{t}}^{\ell_{t}-1}(\theta_{t})&0\\\
0&\boldsymbol{\mathcal{P}}_{\ell_{t}}^{\ell_{t}-1}(\theta_{t})\\\
\boldsymbol{\mathcal{P}}_{\ell_{t}}^{\ell_{t}-1}(\gamma(\theta_{t}))&0\\\
0&\boldsymbol{\mathcal{P}}_{\ell_{t}}^{\ell_{t}-1}(\gamma(\theta_{t}))\end{pmatrix}\in\mathbb{C}^{4N_{t}\times
2N_{t}}$

and the Fourier symbol
$\boldsymbol{\mathcal{P}}_{\ell_{t}}^{\ell_{t}-1}(\theta_{t})\in\mathbb{C}^{N_{t}\times
N_{t}}$ as defined in Lemma 4.4.

Analogously to the semi-coarsening case we can get the mapping properties for
the full-restriction and full-prolongation operators.

######  Lemma 4.7 (Fourier symbol of restriction, full-coarsening).

The following mapping property holds for the restriction operator
$(\underline{\mathbf{R}}_{\ell-1}^{\ell})^{f}$:

$\displaystyle(\underline{\mathbf{R}}_{\ell-1}^{\ell})^{f}:\mathcal{E}_{\ell_{x},\ell_{t}}(\theta_{x},\theta_{t})$
$\displaystyle\to\Psi_{\ell_{x}-1,\ell_{t}-1}(2\theta_{x},2\theta_{t}),$
$\displaystyle\begin{pmatrix}\mathbf{U}_{1}\\\ \mathbf{U}_{2}\\\
\mathbf{U}_{3}\\\ \mathbf{U}_{4}\end{pmatrix}$
$\displaystyle\mapsto(\widetilde{\boldsymbol{\mathcal{R}}}_{\ell-1}^{\ell})^{f}(\theta_{x},\theta_{t})\begin{pmatrix}\mathbf{U}_{1}\\\
\mathbf{U}_{2}\\\ \mathbf{U}_{3}\\\ \mathbf{U}_{4}\end{pmatrix},$

with

$\displaystyle(\widetilde{\boldsymbol{\mathcal{R}}}_{\ell-1}^{\ell})^{f}(\theta_{x},\theta_{t}):=$
$\displaystyle\begin{pmatrix}\hat{\boldsymbol{\mathcal{R}}}_{\ell-1}^{\ell}(\theta_{x},\theta_{t})&\hat{\boldsymbol{\mathcal{R}}}_{\ell-1}^{\ell}(\gamma(\theta_{x}),\theta_{t})&\hat{\boldsymbol{\mathcal{R}}}_{\ell_{t}}^{\ell}(\theta_{x},\gamma(\theta_{t}))&\hat{\boldsymbol{\mathcal{R}}}_{\ell-1}^{\ell}(\gamma(\theta_{x}),\gamma(\theta_{t}))\end{pmatrix}\in\mathbb{C}^{N_{t}\times
4N_{t}},$

and the Fourier symbol

$\displaystyle\hat{\boldsymbol{\mathcal{R}}}_{\ell-1}^{\ell}(\theta_{x},\theta_{t}):=\mathcal{R}_{\ell_{x}-1}^{\ell_{x}}(\theta_{x})\boldsymbol{\mathcal{R}}_{\ell_{t}-1}^{\ell_{t}}(\theta_{t})\in\mathbb{C}^{N_{t}\times
N_{t}},$

with $\mathcal{R}_{\ell_{x}-1}^{\ell_{x}}(\theta_{x})\in\mathbb{C}$ from Lemma
4.3 and
$\boldsymbol{\mathcal{R}}_{\ell_{t}-1}^{\ell_{t}}(\theta_{t})\in\mathbb{C}^{N_{t}\times
N_{t}}$ from Lemma 4.4.

######  Lemma 4.8 (Fourier symbol of prolongation, full-coarsening).

The following mapping property holds for the prolongation operator
$(\underline{\mathbf{P}}_{\ell}^{\ell-1})^{f}$:

$\displaystyle(\underline{\mathbf{P}}_{\ell}^{\ell-1})^{f}:\Psi_{\ell_{x}-1,\ell_{t}-1}(2\theta_{x},2\theta_{t})$
$\displaystyle\to\mathcal{E}_{\ell_{x},\ell_{t}}(\theta_{x},\theta_{t}),$
$\displaystyle\mathbf{U}$
$\displaystyle\mapsto(\widetilde{\boldsymbol{\mathcal{P}}}_{\ell}^{\ell-1})^{f}(\theta_{t},\theta_{x})\mathbf{U},$

with

$\displaystyle(\widetilde{\boldsymbol{\mathcal{P}}}_{\ell}^{\ell-1})^{f}(\theta_{t},\theta_{x}):=\begin{pmatrix}\hat{\boldsymbol{\mathcal{P}}}_{\ell}^{\ell-1}(\theta_{x},\theta_{t})\\\
\hat{\boldsymbol{\mathcal{P}}}_{\ell}^{\ell-1}(\gamma(\theta_{x}),\theta_{t})\\\
\hat{\boldsymbol{\mathcal{P}}}_{\ell}^{\ell-1}(\theta_{x},\gamma(\theta_{t}))\\\
\hat{\boldsymbol{\mathcal{P}}}_{\ell}^{\ell-1}(\gamma(\theta_{x}),\gamma(\theta_{t}))\end{pmatrix}\in\mathbb{C}^{4N_{t}\times
N_{t}},$

and the Fourier symbol

$\displaystyle\hat{\boldsymbol{\mathcal{P}}}_{\ell}^{\ell-1}(\theta_{x},\theta_{t}):=\mathcal{P}_{\ell_{x}}^{\ell_{x}-1}(\theta_{x})\boldsymbol{\mathcal{P}}_{\ell_{t}}^{\ell_{t}-1}(\theta_{t})\in\mathbb{C}^{N_{t}\times
N_{t}},$

with $\mathcal{P}_{\ell_{x}}^{\ell_{x}-1}\in\mathbb{C}$ from Lemma 4.3 and
$\boldsymbol{\mathcal{P}}_{\ell_{t}}^{\ell_{t}-1}\in\mathbb{C}^{N_{t}\times
N_{t}}$ from Lemma 4.4.

With Lemma 4.1 we obtain the mapping property for coarse grid correction when
semi-coarsening in time is applied:

$\displaystyle\begin{split}(\underline{\mathbf{L}}_{2\tau_{\ell},\xi_{\ell}})^{-1}:\Psi_{\ell_{x},\ell_{t}-1}(\theta_{x},2\theta_{t})&\rightarrow\Psi_{\ell_{x},\ell_{t}-1}(\theta_{x},2\theta_{t}),\\\
\begin{pmatrix}\mathbf{U}_{1}\\\
\mathbf{U}_{2}\end{pmatrix}&\mapsto(\hat{\boldsymbol{\mathcal{L}}}^{s}_{2\tau_{\ell},\xi_{\ell}}(\theta_{x},2\theta_{t}))^{-1}\begin{pmatrix}\mathbf{U}_{1}\\\
\mathbf{U}_{2}\end{pmatrix},\end{split}$ (24)

with

$\displaystyle(\hat{\boldsymbol{\mathcal{L}}}^{s}_{2\tau_{\ell},\xi_{\ell}}(\theta_{x},2\theta_{t}))^{-1}:=\begin{pmatrix}(\boldsymbol{\mathcal{L}}_{2\tau_{\ell},\xi_{\ell}}(\theta_{x},2\theta_{t}))^{-1}&0\\\
0&(\boldsymbol{\mathcal{L}}_{2\tau_{\ell},\xi_{\ell}}(\gamma(\theta_{x}),2\theta_{t}))^{-1}\end{pmatrix}\in\mathbb{C}^{2N_{t}\times
2N_{t}}.$

A complication arises for frequencies $(\theta_{x},\theta_{t})$ such that
$\boldsymbol{\mathcal{L}}_{2\tau_{\ell},\xi_{\ell}}(\theta_{x},2\theta_{t})=0$.
For some more discussion of the reasons for this formal complication we refer
to [26]. In order to make sure that $\hat{\boldsymbol{\mathcal{L}}}^{s}$
exists, we exclude the set of frequencies

$\displaystyle\Lambda_{s}:=\left\\{(\theta_{x},\theta_{t})\in\left(-\pi,\pi\right]\times\left(-\frac{\pi}{2},\frac{\pi}{2}\right]:\boldsymbol{\mathcal{L}}_{\tau_{\ell},\xi_{\ell}}(\theta_{x},\theta_{t})=0\text{
or
}\boldsymbol{\mathcal{L}}_{2\tau_{\ell},\xi_{\ell}}(\theta_{x},2\theta_{t})=0\right\\}.$
(25)

For the full-coarsening case we obtain the mapping property

$\displaystyle\begin{split}(\underline{\mathbf{L}}_{2\tau_{\ell},2\xi_{\ell}})^{-1}:\Psi_{\ell_{x}-1,\ell_{t}-1}(2\theta_{x},2\theta_{t})&\rightarrow\Psi_{\ell_{x}-1,\ell_{t}-1}(2\theta_{x},2\theta_{t}),\\\
\mathbf{U}&\mapsto(\hat{\boldsymbol{\mathcal{L}}}^{f}_{2\tau_{\ell},2\xi_{\ell}}(2\theta_{x},2\theta_{t}))^{-1}\mathbf{U},\end{split}$
(26)

with

$\displaystyle(\hat{\boldsymbol{\mathcal{L}}}^{f}_{2\tau_{\ell},2\xi_{\ell}}(2\theta_{x},2\theta_{t}))^{-1}:=(\boldsymbol{\mathcal{L}}_{2\tau_{\ell},2\xi_{\ell}}(2\theta_{x},2\theta_{t}))^{-1}\in\mathbb{C}^{N_{t}\times
N_{t}}.$ (27)

As before, a complication arises for frequencies $(\theta_{x},\theta_{t})$
such that
$\boldsymbol{\mathcal{L}}_{2\tau_{\ell},2\xi_{\ell}}(2\theta_{x},2\theta_{t})=0$.
In order to make sure that $\hat{\boldsymbol{\mathcal{L}}}^{f}$ exists, we
exclude the set of frequencies

$\displaystyle\Lambda_{f}:=\left\\{(\theta_{x},\theta_{t})\in\left(-\frac{\pi}{2},\frac{\pi}{2}\right]^{2}:\boldsymbol{\mathcal{L}}_{\tau_{\ell},\xi_{\ell}}(\theta_{x},\theta_{t})=0\text{
or
}\boldsymbol{\mathcal{L}}_{2\tau_{\ell},2\xi_{\ell}}(2\theta_{x},2\theta_{t})=0\right\\}.$

We are now able to get the Fourier symbol of the two-grid operators and
calculate the asymptotic convergence factors.

######  Theorem 4.9 (Fourier symbol of two-grid operator, semi-coarsening).

For $(\theta_{x},\theta_{t})\in\Theta_{\ell_{x},\ell_{t}}^{low,f}$ the
following mapping property holds for the two-grid operator
$\underline{\mathbf{M}}^{s}_{\tau_{\ell},\xi_{\ell}}$ in (17) with semi-
coarsening in time:

$\displaystyle\underline{\mathbf{M}}^{s}_{\tau_{\ell},\xi_{\ell}}:\mathcal{E}_{\ell_{x},\ell_{t}}(\theta_{x},\theta_{t})$
$\displaystyle\rightarrow\mathcal{E}_{\ell_{x},\ell_{t}}(\theta_{x},\theta_{t}),$
$\displaystyle\begin{pmatrix}\mathbf{U}_{1}\\\ \mathbf{U}_{2}\\\
\mathbf{U}_{3}\\\ \mathbf{U}_{4}\end{pmatrix}$
$\displaystyle\mapsto\boldsymbol{\mathcal{M}}^{s}(\theta_{x},\theta_{t})\begin{pmatrix}\mathbf{U}_{1}\\\
\mathbf{U}_{2}\\\ \mathbf{U}_{3}\\\ \mathbf{U}_{4}\end{pmatrix},$

with

$\displaystyle\begin{split}\boldsymbol{\mathcal{M}}^{s}(\theta_{x},\theta_{t})&:=\widetilde{\boldsymbol{\mathcal{S}}}_{\tau_{\ell},\xi_{\ell}}^{\nu_{2}}(\theta_{x},\theta_{t})(\mathbf{I}_{4N_{t}}-(\widetilde{\boldsymbol{\mathcal{P}}}^{\ell-1}_{\ell})^{s}(\theta_{t})(\hat{\boldsymbol{\mathcal{L}}}^{s}_{2\tau_{\ell},\xi_{\ell}}(\theta_{x},2\theta_{t}))^{-1}\\\
&\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\
(\widetilde{\boldsymbol{\mathcal{R}}}_{\ell-1}^{\ell})^{s}(\theta_{t})\widetilde{\boldsymbol{\mathcal{L}}}_{\tau_{\ell},\xi_{\ell}}(\theta_{x},\theta_{t}))\widetilde{\boldsymbol{\mathcal{S}}}_{\tau_{\ell},\xi_{\ell}}^{\nu_{1}}(\theta_{x},\theta_{t})\in\mathbb{C}^{4N_{t}\times
4N_{t}}.\end{split}$ (28)

###### Proof.

The two-grid operator for semi-coarsening is given by

$\displaystyle\underline{\mathbf{M}}^{s}_{\tau_{\ell},\xi_{\ell}}=\underline{\mathbf{S}}_{\tau_{\ell},\xi_{\ell}}^{\nu_{2}}(\underline{\mathbf{I}}-(\underline{\mathbf{P}}_{\ell}^{\ell-1})_{s}(\underline{\mathbf{L}}_{2\tau_{\ell},\xi_{\ell}})^{-1}(\underline{\mathbf{R}}_{\ell-1}^{\ell})_{s}\underline{\mathbf{L}}_{\tau_{\ell},\xi_{\ell}})\underline{\mathbf{S}}_{\tau_{\ell},\xi_{\ell}}^{\nu_{1}}.$

By previous results we obtain

$\displaystyle\underline{\mathbf{M}}^{s}_{\tau_{\ell},\xi_{\ell}}:$
$\displaystyle\mathcal{E}_{\ell_{x},\ell_{t}}\xrightarrow[]{\eqref{MappingSmoother}}\mathcal{E}_{\ell_{x},\ell_{t}}\xrightarrow[]{\eqref{MappingSystemMatrix}}\mathcal{E}_{\ell_{x},\ell_{t}}\xrightarrow[]{\ref{FourierSymbRsemi}}\Psi_{\ell_{x},\ell_{t}-1}(\theta_{x},2\theta_{t})$
$\displaystyle\xrightarrow[]{\eqref{MappingSystemMatrixSemi}}\Psi_{\ell_{x},\ell_{t}-1}(\theta_{x},2\theta_{t})\xrightarrow[]{\ref{FourierSymbPsemi}}\mathcal{E}_{\ell_{x},\ell_{t}}\xrightarrow[]{\eqref{MappingSmoother}}\mathcal{E}_{\ell_{x},\ell_{t}},$

with the mapping

$\displaystyle\begin{pmatrix}\mathbf{U}_{1}\\\ \mathbf{U}_{2}\\\
\mathbf{U}_{3}\\\ \mathbf{U}_{4}\end{pmatrix}$
$\displaystyle\mapsto\widetilde{\boldsymbol{\mathcal{S}}}_{\tau_{\ell},\xi_{\ell}}^{\nu_{1}}\begin{pmatrix}\mathbf{U}_{1}\\\
\mathbf{U}_{2}\\\ \mathbf{U}_{3}\\\
\mathbf{U}_{4}\end{pmatrix}\mapsto\widetilde{\boldsymbol{\mathcal{L}}}_{\tau_{\ell},\xi_{\ell}}\widetilde{\boldsymbol{\mathcal{S}}}_{\tau_{\ell},\xi_{\ell}}^{\nu_{1}}\begin{pmatrix}\mathbf{U}_{1}\\\
\mathbf{U}_{2}\\\ \mathbf{U}_{3}\\\
\mathbf{U}_{4}\end{pmatrix}\mapsto(\widetilde{\boldsymbol{\mathcal{R}}}_{\ell-1}^{\ell})^{s}\widetilde{\boldsymbol{\mathcal{L}}}_{\tau_{\ell},\xi_{\ell}}\widetilde{\boldsymbol{\mathcal{S}}}_{\tau_{\ell},\xi_{\ell}}^{\nu_{1}}\begin{pmatrix}\mathbf{U}_{1}\\\
\mathbf{U}_{2}\\\ \mathbf{U}_{3}\\\ \mathbf{U}_{4}\end{pmatrix}$
$\displaystyle\mapsto(\hat{\boldsymbol{\mathcal{L}}}^{s}_{2\tau_{\ell},\xi_{\ell}})^{-1}(\widetilde{\boldsymbol{\mathcal{R}}}_{\ell-1}^{\ell})^{s}\widetilde{\boldsymbol{\mathcal{L}}}_{\tau_{\ell},\xi_{\ell}}\widetilde{\boldsymbol{\mathcal{S}}}_{\tau_{\ell},\xi_{\ell}}^{\nu_{1}}\begin{pmatrix}\mathbf{U}_{1}\\\
\mathbf{U}_{2}\\\ \mathbf{U}_{3}\\\ \mathbf{U}_{4}\end{pmatrix}$
$\displaystyle\mapsto(\widetilde{\boldsymbol{\mathcal{P}}}^{\ell-1}_{\ell})^{s}(\hat{\boldsymbol{\mathcal{L}}}^{s}_{2\tau_{\ell},\xi_{\ell}})^{-1}(\widetilde{\boldsymbol{\mathcal{R}}}_{\ell-1}^{\ell})^{s}\widetilde{\boldsymbol{\mathcal{L}}}_{\tau_{\ell},\xi_{\ell}}\widetilde{\boldsymbol{\mathcal{S}}}_{\tau_{\ell},\xi_{\ell}}^{\nu_{1}}\begin{pmatrix}\mathbf{U}_{1}\\\
\mathbf{U}_{2}\\\ \mathbf{U}_{3}\\\ \mathbf{U}_{4}\end{pmatrix}$
$\displaystyle\mapsto(\mathbf{I}_{4N_{t}}-(\widetilde{\boldsymbol{\mathcal{P}}}^{\ell-1}_{\ell})^{s}(\hat{\boldsymbol{\mathcal{L}}}^{s}_{2\tau_{\ell},\xi_{\ell}})^{-1}(\widetilde{\boldsymbol{\mathcal{R}}}_{\ell-1}^{\ell})^{s}\widetilde{\boldsymbol{\mathcal{L}}}_{\tau_{\ell},\xi_{\ell}})\widetilde{\boldsymbol{\mathcal{S}}}_{\tau_{\ell},\xi_{\ell}}^{\nu_{1}}\begin{pmatrix}\mathbf{U}_{1}\\\
\mathbf{U}_{2}\\\ \mathbf{U}_{3}\\\ \mathbf{U}_{4}\end{pmatrix}$
$\displaystyle\mapsto\widetilde{\boldsymbol{\mathcal{S}}}_{\tau_{\ell},\xi_{\ell}}^{\nu_{2}}(\mathbf{I}_{4N_{t}}-(\widetilde{\boldsymbol{\mathcal{P}}}^{\ell-1}_{\ell})^{s}(\hat{\boldsymbol{\mathcal{L}}}^{s}_{2\tau_{\ell},\xi_{\ell}})^{-1}(\widetilde{\boldsymbol{\mathcal{R}}}_{\ell-1}^{\ell})^{s}\widetilde{\boldsymbol{\mathcal{L}}}_{\tau_{\ell},\xi_{\ell}})\widetilde{\boldsymbol{\mathcal{S}}}_{\tau_{\ell},\xi_{\ell}}^{\nu_{1}}\begin{pmatrix}\mathbf{U}_{1}\\\
\mathbf{U}_{2}\\\ \mathbf{U}_{3}\\\ \mathbf{U}_{4}\end{pmatrix}.$

∎

######  Theorem 4.10 (Fourier symbol of two-grid operator, full-coarsening).

For $(\theta_{x},\theta_{t})\in\Theta_{{\ell}_{x},{\ell}_{t}}^{low,f}$ the
following mapping property holds for the two-grid operator
$\underline{\mathbf{M}}^{f}_{\tau_{\ell},\xi_{\ell}}$ in (16) with space-time
coarsening:

$\displaystyle\underline{\mathbf{M}}^{f}_{\tau_{\ell},\xi_{\ell}}:\mathcal{E}_{{\ell}_{x},{\ell}_{t}}(\theta_{x},\theta_{t})$
$\displaystyle\rightarrow\mathcal{E}_{{\ell}_{x},{\ell}_{t}}(\theta_{x},\theta_{t}),$
$\displaystyle\begin{pmatrix}\mathbf{U}_{1}\\\ \mathbf{U}_{2}\\\
\mathbf{U}_{3}\\\ \mathbf{U}_{4}\end{pmatrix}$
$\displaystyle\mapsto\boldsymbol{\mathcal{M}}^{f}(\theta_{x},\theta_{t})\begin{pmatrix}\mathbf{U}_{1}\\\
\mathbf{U}_{2}\\\ \mathbf{U}_{3}\\\ \mathbf{U}_{4}\end{pmatrix},$

with

$\displaystyle\begin{split}\boldsymbol{\mathcal{M}}^{f}(\theta_{x},\theta_{t})&:=\widetilde{\boldsymbol{\mathcal{S}}}_{\tau_{\ell},\xi_{\ell}}^{\nu_{2}}(\theta_{x},\theta_{t})(\mathbf{I}_{4N_{t}}-(\widetilde{\boldsymbol{\mathcal{P}}}^{\ell-1}_{\ell})^{f}(\theta_{x},\theta_{t})(\hat{\boldsymbol{\mathcal{L}}}^{f}_{2\tau_{\ell},2\xi_{\ell}}(2\theta_{x},2\theta_{t}))^{-1}\\\
&\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\
(\widetilde{\boldsymbol{\mathcal{R}}}_{\ell-1}^{\ell})^{f}(\theta_{x},\theta_{t})\widetilde{\boldsymbol{\mathcal{L}}}_{\tau_{\ell},\xi_{\ell}}(\theta_{x},\theta_{t}))\widetilde{\boldsymbol{\mathcal{S}}}_{\tau_{\ell},\xi_{\ell}}^{\nu_{1}}(\theta_{x},\theta_{t})\in\mathbb{C}^{4N_{t}\times
4N_{t}}.\end{split}$ (29)

###### Proof.

The proof follows analogous to the previous one. ∎

##  5 Smoothing Analysis

We now have all tools at hand to analyze the elements of the multigrid
iteration. We start with the smoother. The asymptotic smoothing factor of the
damped block Jacobi method (15) can be measured by computing the spectral
radius of its symbol
$\boldsymbol{\mathcal{S}}_{\tau_{\ell},\xi_{\ell}}(\theta_{x},\theta_{t})$,
which is of much smaller size and thus makes the calculations feasible.

######  Definition 5.1 ([34]).

We define the asymptotic smoothing factors for semi- and full-coarsening as

$\displaystyle\varrho(\boldsymbol{\mathcal{S}}^{s})$
$\displaystyle:=\max\\{\varrho(\boldsymbol{\mathcal{S}}_{\tau_{\ell},\xi_{\ell}}(\theta_{x},\theta_{t})):(\theta_{x},\theta_{t})\in\Theta_{{\ell}_{x},{\ell}_{t}}^{high,s}\\},$
$\displaystyle\varrho(\boldsymbol{\mathcal{S}}^{f})$
$\displaystyle:=\max\\{\varrho(\boldsymbol{\mathcal{S}}_{\tau_{\ell},\xi_{\ell}}(\theta_{x},\theta_{t})):(\theta_{x},\theta_{t})\in\Theta_{{\ell}_{x},{\ell}_{t}}^{high,f}\\},$

with
$\boldsymbol{\mathcal{S}}_{\tau_{\ell},\xi_{\ell}}(\theta_{x},\theta_{t})$ the
Fourier symbol of the smoother and the set of frequencies defined in (20) and
(21).

######  Lemma 5.2.

The spectral radius of the Fourier symbol of the smoother
$\boldsymbol{\mathcal{S}}_{\tau_{\ell},\xi_{\ell}}(\theta_{x},\theta_{t})$ is
given by

$\displaystyle\rho(\boldsymbol{\mathcal{S}}_{\tau_{\ell},\xi_{\ell}}(\theta_{x},\theta_{t}))=\max\\{|1-\omega_{t}|,S(\omega_{t},\theta_{x},\theta_{t})\\}$

with

$\displaystyle
S(\omega_{t},\theta_{x},\theta_{t}):=|1-\omega_{t}+e^{-\mathrm{i}\theta_{t}}\omega_{t}R(-\mu\beta(\theta_{x}))|,$
(30)

$R$ the stability function of the DG-SEM time stepping scheme,
$\beta(\theta_{x}):=1-e^{-\mathrm{i}\theta_{x}}$ and CFL number
$\mu:=\frac{a\Delta\tau_{\ell}}{\Delta x_{\ell}}$.

###### Proof.

The eigenvalues of
$\boldsymbol{\mathcal{S}}_{\tau_{\ell},\xi_{\ell}}(\theta_{x},\theta_{t})$ are
given by

$\displaystyle\sigma(\boldsymbol{\mathcal{S}}_{\tau_{\ell},\xi_{\ell}}(\theta_{x},\theta_{t}))$
$\displaystyle=1-\omega_{t}+e^{-\mathrm{i}\theta_{t}}\omega_{t}\sigma\left(\left(\mathbf{K}_{\tau_{\ell}}+\frac{a}{\Delta
x}(-e^{-\mathrm{i}\theta_{x}}+1)\mathbf{M}_{\tau_{\ell}}\right)^{-1}\mathbf{C}_{\tau_{\ell}}\right).$

With Lemma 3.5 we can compute the spectrum as

$\displaystyle\sigma(\boldsymbol{\mathcal{S}}_{\tau_{\ell},\xi_{\ell}}(\theta_{x},\theta_{t}))=\\{1-\omega_{t},1-\omega_{t}+e^{-\mathrm{i}\theta_{t}}\omega_{t}R(-\mu\beta(\theta_{x}))\\}.$

Therefore it follows that

$\displaystyle\rho(\boldsymbol{\mathcal{S}}_{\tau_{\ell},\xi_{\ell}}(\theta_{x},\theta_{t}))=\max\\{|1-\omega_{t}|,|1-\omega_{t}+e^{-\mathrm{i}\theta_{k}}\omega_{t}R(-\mu\beta(\theta_{x}))|\\}.$

∎

###  5.1 Optimal Damping Parameter

The goal is to find a smoother with optimal smoothing behavior, i.e. to find a
damping parameter $\omega_{t}$ for the block Jacobi smoother such that the
high frequencies frequencies are smoothed as efficiently as possible. We
analyze the Fourier symbol $\boldsymbol{\mathcal{S}}_{\tau_{\ell},\xi_{\ell}}$
to find the optimal damping parameter $\omega_{t}\in(0,1]$ in (15). In order
to do so, the frequencies which are damped less efficiently need to be
determined. These are also called worst case frequencies:

######  Definition 5.3.

The worst case frequencies for the Fourier symbol
$\boldsymbol{\mathcal{S}}_{\tau_{\ell},\xi_{\ell}}$ of the smoother are
defined as those high frequencies that are damped least efficiently.

This can be done by calculating the maximum of $|1-\omega_{t}|$ and

$\displaystyle(\theta_{x}^{*}(\omega_{t},\mu),\theta_{t}^{*}(\omega_{t},\mu)):=\operatorname*{arg\,sup}_{\begin{subarray}{c}(\theta_{x},\theta_{t})\in\Theta^{high}\end{subarray}}S(\omega_{t},\theta_{x},\theta_{t}),$
(31)

with the function $S$ defined in Lemma 5.2, see equation (30).

Straightforward calculations give

$\displaystyle S(\omega_{t},\theta_{x},\theta_{t})^{2}$
$\displaystyle=|1-\omega_{t}+e^{-\mathrm{i}\theta_{t}}\omega_{t}R(-\mu\beta(\theta_{x}))|^{2}$
$\displaystyle=(1-\omega_{t})^{2}+2\omega_{t}(1-\omega_{t})(\cos(\theta_{t})\text{Re}(R(-\mu\beta(\theta_{x})))+\sin(\theta_{t})\text{Im}(R(-\mu\beta(\theta_{x}))))$
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\
+\omega_{t}^{2}|R(-\mu\beta(\theta_{x}))|^{2}.$

When considering implicit time integration, large CFL numbers $\mu\gg 0$ are
of interest. Then

$\displaystyle\cos(\theta_{t})\text{Re}(R(-\mu\beta(\theta_{x})))+\sin(\theta_{t})\text{Im}(R(-\mu\beta(\theta_{x})))\xrightarrow[\mu\to\infty]{}0,$

since $\cos(\theta_{t}),\sin(\theta_{t})\in[-1,1]$, and the method is
L-stable, see Corollary 3.3, thus $R(-z)\rightarrow 0$ for
$z\rightarrow\infty$ and $\text{Re}(-\mu\beta(\theta_{x}))\leq 0$ for
$\theta_{x}\in[-\pi,\pi]$.

To find the worst case frequencies in space for large CFL numbers $\mu$ we
thus need to maximize $|R(-\mu\beta(\theta_{x}))|^{2}$. From L-stability it
follows that $|R(-\mu\beta(\theta_{x}))|^{2}\leq 1$ and moreover we have by
definition of the Padé approximant that $R(0)=1$. Thus we have found the worst
case frequency in space:

$\displaystyle\theta_{x}^{*}=\operatorname*{arg\,sup}_{\begin{subarray}{c}\theta_{x}\in(-\pi,\pi]\end{subarray}}S(\omega_{t},\theta_{x},\theta_{t})=0.$

Evaluating (30) at $\theta_{x}=\theta_{x}^{*}=0$ gives

$\displaystyle S(\omega_{t},0,\theta_{t})$
$\displaystyle=|1-\omega_{t}+e^{-\mathrm{i}\theta_{t}}\omega_{t}R(-\mu\beta(\theta_{x}))|$
$\displaystyle=\sqrt{(1-\omega_{t})^{2}+2\omega_{t}(1-\omega_{t})\cos(\theta_{t})+\omega_{t}^{2}}.$

With this, it follows that the worst case frequencies in time are given by

$\displaystyle\theta_{t}^{*}$
$\displaystyle=\operatorname*{arg\,sup}_{\begin{subarray}{c}\theta_{t}\in[\pi/2,\pi]\end{subarray}}S(\omega_{t},\theta_{x}^{*},\theta_{t})=\frac{\pi}{2},$
$\displaystyle\theta_{t}^{*}$
$\displaystyle=\operatorname*{arg\,sup}_{\begin{subarray}{c}\theta_{t}\in[-\pi,-\pi/2]\end{subarray}}S(\omega_{t},\theta_{x}^{*},\theta_{t})=-\frac{\pi}{2}.$

Thus, we have found worst case frequencies
$(\theta_{x}^{*},\theta_{t}^{*})\in\Theta_{\ell_{x},\ell_{t}}^{high,s}$ for
the semi-coarsening strategy as well as
$(\theta_{x}^{*},\theta_{t}^{*})\in\Theta_{\ell_{x},\ell_{t}}^{high,f}$ for
the full-coarsening strategy. The optimal damping parameter can then be
calculated by

$\displaystyle\omega_{t}^{*}=\operatorname*{arg\,inf}_{\omega_{t}\in(0,1]}S(\omega_{t},\theta_{x}^{*},\theta_{t}^{*})=0.5.$

###  5.2 Asymptotic Smoothing Factor

With the optimal damping parameter $\omega_{t}^{*}=0.5$ and the worst case
frequencies $(\theta_{x}^{*},\theta_{t}^{*})$ at hand we can calculate the
asymptotic smoothing factor from Definition 5.1.

In the case of full space-time coarsening we get for $\mu$ large enough

$\displaystyle\varrho(\boldsymbol{\mathcal{S}})=\rho(\boldsymbol{\mathcal{S}}_{\tau_{\ell},\xi_{\ell}}(\theta_{x}^{*},\theta_{t}^{*}))=\max\left\\{|0.5|,S(0.5,0,\frac{\pi}{2})\right\\}=\max\\{0.5,\sqrt{0.5}\\}=\frac{1}{\sqrt{2}},$

and for semi-coarsening in time

$\displaystyle\varrho(\boldsymbol{\mathcal{S}})=\rho(\boldsymbol{\mathcal{S}}_{\tau_{\ell},\xi_{\ell}}(\theta_{x}^{*},\theta_{t}^{*}))=\max\left\\{|0.5|,S(0.5,0,-\frac{\pi}{2})\right\\}=\max\\{0.5,\sqrt{0.5}\\}=\frac{1}{\sqrt{2}}.$

##  6 Two-Grid Analysis

In this section we analyze the two-grid iteration for full- and semi-
coarsening by studying the corresponding iteration matrices
$\underline{\mathbf{M}}_{\tau_{\ell},\xi_{\ell}}^{f}$ and
$\underline{\mathbf{M}}_{\tau_{\ell},\xi_{\ell}}^{s}$, see equations (16) and
(17). With Theorems 4.9 and 4.10 we can analyze the asymptotic convergence
behavior of the two-grid cycle by computing the maximal spectral radius of the
Fourier symbols $\boldsymbol{\mathcal{M}}_{\mu}^{s}(\theta_{x},\theta_{t})$
and $\boldsymbol{\mathcal{M}}_{\mu}^{f}(\theta_{x},\theta_{t})$ for
$(\theta_{x},\theta_{t})\in\Theta_{{\ell}_{x},{\ell}_{t}}^{low,f}$, see (29)
and (28).

######  Definition 6.1.

We define the asymptotic two-grid convergence factors as

$\displaystyle\varrho(\boldsymbol{\mathcal{M}}^{s})$
$\displaystyle:=\max\\{\varrho(\boldsymbol{\mathcal{M}}^{s}(\theta_{x},\theta_{t})):(\theta_{x},\theta_{t})\in\Theta_{{\ell}_{x},{\ell}_{t}}^{low,f}\setminus\Lambda_{s}\\},$
$\displaystyle\varrho(\boldsymbol{\mathcal{M}}^{f})$
$\displaystyle:=\max\\{\varrho(\boldsymbol{\mathcal{M}}^{f}(\theta_{x},\theta_{t})):(\theta_{x},\theta_{t})\in\Theta_{{\ell}_{x},{\ell}_{t}}^{low,f}\setminus\Lambda_{f}\\},$

with $\boldsymbol{\mathcal{M}}^{s}(\theta_{x},\theta_{t})$ and
$\boldsymbol{\mathcal{M}}^{f}(\theta_{x},\theta_{t})$ the symbols of the two-
grid iteration matrices and $\Lambda_{s}$ defined in (25) and $\Lambda_{f}$
defined in (27).

To derive $\varrho(\boldsymbol{\mathcal{M}}^{s})$ and
$\varrho(\boldsymbol{\mathcal{M}}^{f})$ for a given CFL number
$\mu\in\mathbb{R}_{+}$ and a given polynomial degree $p_{t}\in\mathbb{N}$, it
is necessary to compute the eigenvalues of

$\displaystyle\boldsymbol{\mathcal{M}}^{s}(\theta_{x},\theta_{t})\in\mathbb{C}^{4N_{t}\times
4N_{t}}\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \text{and}\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\
\boldsymbol{\mathcal{M}}^{f}(\theta_{x},\theta_{t})\in\mathbb{C}^{4N_{t}\times
4N_{t}},$

with $N_{t}=p_{t}+1$ for all low frequencies
$(\theta_{x},\theta_{t})\in\Theta_{{\ell}_{x},{\ell}_{t}}^{low,s}$
respectively
$(\theta_{x},\theta_{t})\in\Theta_{{\ell}_{x},{\ell}_{t}}^{low,f}$.

It is difficult to find analytical expressions for the eigenvalues of the two-
grid operators $\boldsymbol{\mathcal{M}}^{f}(\theta_{x},\theta_{t})$ and
$\boldsymbol{\mathcal{M}}^{s}(\theta_{x},\theta_{t})$ since they are the
product of several Fourier symbols which itself are complex functions. We
therefore compute the eigenvalues numerically for all frequencies
$(\theta_{x},\theta_{t})\in\Theta_{{\ell}_{x},{\ell}_{t}}^{low,f}$ and
$(\theta_{x},\theta_{t})\in\Theta_{{\ell}_{x},{\ell}_{t}}^{low,s}$. We
consider a space-time discretization with $N_{x}$ volumes in space and $N$
space-time slabs on the domain $[0,1]\times[0,T]$, where we adapt $T$ via the
CFL number $\mu=\frac{\Delta t}{\Delta x}\in[1,800]$.

The results for the LFA can be seen in Figure 3 for $N_{x}=2^{5}$, $N=2^{3}$
to the left and for $N_{x}=2^{10}$, $N=2^{3}$ to the right,
$\mu\in[1,10,50,100,200,400,600,800]$ for both coarsening strategies, referred
to as semi and full, and $p_{t}=0$ and $p_{t}=1$, respectively.

They show that for high CFL numbers the multigrid solver has excellent
asymptotic convergence rates about $0.5$ for $p_{t}=0$ which can be improved
to $0.375$ by increasing the polynomial degree in time to $p_{t}=1$. Moreover,
these convergence rates are independent of the coarsening strategy.

Figure 3: Results of the LFA for the test problem: left for $N_{x}=2^{5}$,
$N=2^{3}$, right for $N_{x}=2^{10}$, $N=2^{3}$.

##  7 Numerical Examples

We now solve the system (5) using this two-grid method. Periodic boundary
conditions in space and time, needed to perform the LFA, cannot be used for
the numerical tests since this results in singular iteration matrices. We
therefore adjust test case (1) and consider the following problems in one
respectively two spatial dimensions:

$\displaystyle u_{t}+au_{x}=0,\leavevmode\nobreak\ a=1,\leavevmode\nobreak\
(x,t)\in(0,1]\times(0,T],$ (32)

with solution $u(x,t)=\sin(\pi(x-t))$, and

$\displaystyle\mathbf{u}_{t}+\mathbf{a}\cdot\mathbf{u}_{x}=\mathbf{0},\leavevmode\nobreak\
\mathbf{a}=(1,1],\leavevmode\nobreak\ (\mathbf{x},t)\in(0,1]^{2}\times[0,T],$
(33)

with solution $\mathbf{u}(\mathbf{x},t)=\sin(\pi(x_{1}-t))\sin(\pi(x_{2}-t))$.
Moreover, we consider a full space-time DG-SEM, i.e. a DG-SEM in space and
time. As before, the time interval is determined via $T=N\mu\Delta x$.

All numerical tests in this section are performed using the Python interface
of DUNE [6] on an Intel Xeon E5-2650 v3 processor (Haswell) on the LUNARC
Aurora cluster at Lund University.

We calculate the asymptotic convergence rate from 60 multigrid iterations by

$\displaystyle\max_{i=1,\dots,59}\frac{\|\mathbf{r}^{i+1}\|_{2}}{\|\mathbf{r}^{i}\|_{2}},\leavevmode\nobreak\
\mathbf{r}^{i}=\underline{\mathbf{L}}_{\tau,\xi}\underline{\mathbf{u}}^{i}-\underline{\mathbf{b}}.$

The results for one spatial dimension can be seen in Figure 4 to the left,
with $N=2^{3}$ and $N_{x}=2^{10}$. The convergence rates converge for both
coarsening strategies to approximately $0.25$ for $p_{t}=p_{x}=0$ and to
approximately $0.3$ for $p_{t}=p_{x}=1$. The CFL number to achieve these
convergence rates increases when increasing the order of the polynomial
approximation. Moreover, we get slightly higher convergence rates for small
CFL numbers when using the semi-coarsening strategy.

Increasing the number of spatial dimensions we measure the numerical
convergence rates for $N=2^{3}$ and $N_{x}=N_{y}=2^{5}$. The results can be
seen in Figure 4 to the right. Here, the convergence rates for both coarsening
strategies and different DG orders are very similar, converging to
approximately $0.25$. However, we notice some oscillations for the semi-
coarsening ansatz with $p_{t}=p_{x}=1$. This might vanish when increasing the
CFL number. While the numerical convergence rates are similar to the one-
dimensional case for $p_{t}=p_{x}=0$, they improve slightly for
$p_{x}=p_{t}=1$ when increasing the number of spatial dimensions.

Figure 4: Numerical convergence results: left for one spatial dimension, right
for two spatial dimensions.

We now fix $CFL=600$ and vary the number of spatial elements to study the grid
independence of the multigrid solver. The results can be seen in Figure 5. For
$p_{t}=p_{x}=1$ we can conclude a grid independence, while the convergence
rate increases slightly when increasing the order of the DG approximation.

Figure 5: Numerical convergence results two spatial dimension, $\mu=600$,
$N=2^{5}$

##  8 Conclusions

In this article we have applied the LFA to a space-time multigrid solver for
the advection equation discretized with a space-time DG method. With the help
of the analysis we calculated asymptotic convergence factors for the smoother
and the two-grid method. The resulting Fourier symbols are complex since the
spatial FV discretization with upwind flux results in a non-symmetric
operator. For large CFL numbers we could analytically find promising
asymptotic smoothing factors converging to $\frac{1}{\sqrt{2}}$ with
increasing CFL number for both coarsening strategies independent of the
temporal DG-SEM order. As for the smoother, it was difficult to find
analytical expressions for the two-grid asymptotic convergence rates since
they are based on the product of several complex Fourier symbols. We therefore
calculated these numerically. The LFA gave excellent asymptotic convergence
rates converging to $0.5$ for $p_{t}=0$ and decreasing to $0.375$ for
$p_{t}=1$ for higher CFL numbers after some oscillations for small CFL
numbers. The influence of the coarsening strategies on the convergence rates
is minimal, with semi-coarsening in time resulting in slightly better
asymptotic convergence rates for smaller CFL numbers.

For the numerical tests we considered non-periodic advection problems in one
and two spatial dimensions with a space-time DG-SEM approximations and
executed the numerical experiments in DUNE. We obtained asymptotic convergence
rates of approximately $0.25$ for $p_{t}=p_{x}=0$ and $0.3$ for
$p_{t}=p_{x}=1$ and high CFL numbers, independent of the coarsening strategy
in the one-dimensional case. For two dimensions, asymptotic convergence rates
of approximately $0.25$ were measured for high CFL numbers, independent of the
DG-SEM order and the coarsening strategy

The tests showed that the theoretical asymptotic convergence rates from the
LFA were slightly larger than the convergence rates obtained in the numerical
experiments. This can be explained by the different boundary conditions and
more dimensions considered for in numerical experiments. Moreover, the
coarsening strategy does not influence the results very much and simple block
Jacobi smoothers can be used to get smoothing factors of $\frac{1}{\sqrt{2}}$.

However, solving the resulting space-time system at once results in large
systems and it is thus advisable to either parallelize the solver or use a
block multigrid solver for each space-time block.

## Acknowledgements

Gregor Gassner has been supported by the European Research Council (ERC) under
the European Union’s Eights Framework Program Horizon 2020 with the research
project Extreme, ERC grant agreement no. 714487.

## References

  * [1] P. Bastian, M. Blatt, A. Dedner, N.-A. Dreier, C. Engwer, R. Fritze, C. Gräser, C. Grüninger, D. Kempf, R. Klöfkorn, et al.  The Dune framework: Basic concepts and recent developments.  Comput. Math. Appl., 81:75–112, 2021.
  * [2] P. Birken.  Numerical Methods for Unsteady Compressible Flow Problems.  CRC Press, 2021.
  * [3] P. D. Boom and D. W. Zingg.  High-Order Implicit Time-Marching Methods Based on Generalized Summation-by-Parts Operators.  SIAM J. Sci. Comput., 37:A2682–A2709, 2015.
  * [4] A. Brandt.  Multi-level adaptive solutions to boundary-value problems.  Math. Comp., 31(138):333–390, 1977.
  * [5] A. Dedner and R. Klöfkorn.  Extendible and Efficient Python Framework for Solving Evolution Equations with Stabilized Discontinuous Galerkin Methods.  Commun. Appl. Math. Comput., pages 1–40, 2021.
  * [6] A. Dedner, R. Klöfkorn, and M. Nolte.  Python bindings for the dune-fem module.  Zenodo (March 2020), 2020.
  * [7] A. Dedner, R. Klöfkorn, M. Nolte, and M. Ohlberger.  A generic interface for parallel and adaptive discretization schemes: abstraction principles and the dune-fem module.  Computing, 90:165–196, 2010.
  * [8] W. Dörfler, S. Findeisen, and C. Wieners.  Space-time discontinuous Galerkin discretizations for linear first-order hyperbolic evolution systems.  Comput. Methods Appl. Math., 16(3):409–428, 2016.
  * [9] R. D. Falgout, S. Friedhoff, T. V. Kolev, S. P. MacLachlan, J. B. Schroder, and S. Vandewalle.  Multigrid methods with space–time concurrency.  Comput. Vis. Sci., 18(4-5):123–143, 2017.
  * [10] S. Friedhoff, S. MacLachlan, and C. Borgers.  Local Fourier analysis of space-time relaxation and multigrid schemes.  SIAM J. Sci. Comput., 35(5):S250–S276, 2013.
  * [11] L. Friedrich, G. Schnücke, A. R. Winters, D. C. R. Fernández, G. J. Gassner, and M. H. Carpenter.  Entropy Stable Space–Time Discontinuous Galerkin Schemes with Summation-by-Parts Property for Hyperbolic Conservation Laws.  J. Sci. Comput., 80(1):175–222, 2019.
  * [12] M. J. Gander.  50 Years of Time Parallel Time Integration.  In T. Carraro, M. Geiger, S. Körkel, and R. Rannacher, editors, Multiple Shooting and Time Domain Decomposition Methods, pages 69–113, Cham, 2015. Springer International Publishing.
  * [13] M. J. Gander and M. Neumüller.  Analysis of a new space-time parallel multigrid algorithm for parabolic problems.  SIAM J. Sci. Comput., 38(4):A2173–A2208, 2016.
  * [14] J. Gopalakrishnan and G. Kanschat.  A multilevel discontinuous Galerkin method.  Numer. Math., 95(3):527–550, 2003.
  * [15] B. Gustafsson.  High order difference methods for time dependent PDE, volume 38.  Springer Science & Business Media, 2007.
  * [16] W. Hackbusch.  Parabolic multigrid methods.  In R. Glowinski and J.-L. Lions, editors, Computing Methods in Applied Sciences and Engineering IV, pages 189–197. Elsevier Science Publisher B.V., Noth-Holland, 1984.
  * [17] E. Hairer, C. Lubich, and G. Wanner.  Geometric numerical integration: structure-preserving algorithms for ordinary differential equations, volume 31.  Springer Science & Business Media, 2006.
  * [18] E. Hairer and G. Wanner.  Solving ordinary differential equations II, volume 14 of Springer Series in Computational Mathematics.  Springer-Verlag, Berlin, 2010.
  * [19] P. W. Hemker, W. Hoffmann, and M. Van Raalte.  Two-level Fourier analysis of a multigrid approach for discontinuous Galerkin discretization.  SIAM J. Sci. Comput., 25(3):1018–1041, 2003.
  * [20] P. W. Hemker, W. Hoffmann, and M. Van Raalte.  Fourier two-level analysis for discontinuous Galerkin discretization with linear elements.  Numer. Linear Algebra Appl., 11(5-6):473–491, 2004.
  * [21] J. S. Hesthaven, S. Gottlieb, and D. Gottlieb.  Spectral methods for time-dependent problems, volume 21.  Cambridge University Press, 2007.
  * [22] L. O. Jay.  Lobatto methods.  In B. Engquist, editor, Encyclopedia of Applied and Computational Mathematics, pages 817–826. Springer Berlin Heidelberg, Berlin, Heidelberg, 2015.
  * [23] C. M. Klaij, M. H. van Raalte, H. van der Ven, and J. J. van der Vegt.  h-Multigrid for space-time discontinuous Galerkin discretizations of the compressible Navier-Stokes equations.  J. Comput. Phys., 227(2):1024–1045, 2007.
  * [24] M. Neumüller.  Space-Time Methods, volume 20 of Monograph Series TU Graz: Computation in Engineering and Science.  TU Graz, 2013.
  * [25] J. J. Sudirham, J. J. W. van der Vegt, and R. M. J. van Damme.  Space-time discontinuous Galerkin method for advection-diffusion problems on time-dependent domains.  Appl. Numer. Math., 56(12):1491–1518, 2006.
  * [26] U. Trottenberg, C. Oosterlee, and A. Schüller.  Multigrid.  Elsevier Ldt., 2001.
  * [27] J. Van der Vegt.  Space-time discontinuous Galerkin finite element methods, pages 1–37.  VKI Lecture Series. Von Karman Institute for Fluid Dynamics, 2006.  Conference date: 14-11-2005 Through 18-11-2005.
  * [28] J. van der Vegt and S. Rhebergen.  hp-Multigrid as Smoother algorithm for higher order discontinuous Galerkin discretizations of advection dominated flows. Part II: Optimization of the Runge–Kutta smoother.  J. Comput. Phys., 231:7564–7583, 2012.
  * [29] J. J. van der Vegt and S. Rhebergen.  hp-multigrid as smoother algorithm for higher order discontinuous Galerkin discretizations of advection dominated flows: Part I. Multilevel analysis.  J. Comput. Phys., 231(22):7537–7563, 2012.
  * [30] J. J. van der Vegt and H. van der Ven.  Space-time discontinuous Galerkin finite element method with dynamic grid motion for inviscid compressible flows. I. General formulation.  J. Comput. Phys., 182(2):546–585, 2002.
  * [31] J. J. van der Vegt and Y. Xu.  Space–time discontinuous Galerkin method for nonlinear water waves.  J. Comput. Phys., 224(1):17–39, 2007.
  * [32] H. Van der Ven and J. J. van der Vegt.  Space–time discontinuous Galerkin finite element method with dynamic grid motion for inviscid compressible flows: II. Efficient flux quadrature.  Comput. Methods Appl. Mech. Engrg., 191(41-42):4747–4780, 2002\.
  * [33] M. Van Raalte and P. W. Hemker.  Two-level multigrid analysis for the convection–diffusion equation discretized by a discontinuous Galerkin method.  Numer. Linear Algebra Appl., 12(5-6):563–584, 2005.
  * [34] P. Wesseling.  An Introduction to Multigrid Methods.  An Introduction to Multigrid Methods. R.T. Edwards, 2004.