Geometric Multigrid for Conform and Non–″ Elements: Restriction Operators

Question

First of all, let me set up some notations.

Suppose we have a hierarchy of meshes $\mathcal{T}_0 \subset \mathcal{T}_1 \subset \dots \subset \mathcal{T}_n$. For simplicity I restrict myself here to $\mathcal{T}_H := \mathcal{T}_0 \subset \mathcal{T}_1 =: \mathcal{T}_h$:

$\mathbb{U}_H$ and $\mathbb{U}_h$ are spaces of FE–interpolants defined on the coarse and fine mesh, respectively. $\mathbb{R}_H$ and $\mathbb{R}_h$ are corresponding spaces of vectors of coefficients.

$\mathcal{P} \; : \; \mathbb{R} \longleftrightarrow \mathbb{U}$ is a natural isomorphism. For one, for linear Lagrange shapes we have $\mathcal{P}_H \; : \; \mathbb{R}_H \ni \langle \, \xi_0, \, \xi_1, \, \dots, \, \xi_{16} \, \rangle \, \mapsto \, \sum_{i = 0}^{16} \xi_i \, S^H_i(x, y) \in \mathbb{U}_H$, where $S^H_i$ is a usual “hat–function.” $S^H_{15}$ looks like this:

i. Prolongation, $\mathbb{U}_H \subset \mathbb{U}_h$

We want to define a prolongation operator $P \, : \, \mathbb{R}_H \longrightarrow \mathbb{R}_h$ in order to travel between meshes in MG–routines. It is easy in this case:

$$ P \, : \, \mathbb{R}_H \stackrel{\mathcal{P}_H}{\longrightarrow} \mathbb{U}_H \subset \mathbb{U}_h \stackrel{\mathcal{P}_h^{-1}}{\longrightarrow} \mathbb{R}_h, $$

so for linear Lagrange elements $P$ is a sparse matrix:

You can see that coarse DOFs, $i = 0, 1, \dots, 16$, are multiplied by unity (i.e. they remain the same), and fine DOFs are just means of DOFs associated with the ribs they lie on (since the shapes are linear functions).

Let’s fix some $\xi \in \mathbb{R}_H$. I obtain the following results:

$\mathcal{P}_H \, \xi$ (green) and $\mathcal{P}_h \, P \, \xi$ (blue)

So you can see that everything works fine.

ii. Prolongation, $\mathbb{U}_H \not\subset \mathbb{U}_h$

Let’s stick to Crouzeix–Raviart elements. In this case DOFs are associated with ribs, so we should enumerate them:

As one may notice, we do not have $\mathbb{U}_H \not\subset \mathbb{U}_h$ since $u_H \in \mathbb{U}_H$ may be discontinuous at midpoints of fine ribs. So we have to use some tricks in order to define $P$.

Namely, we take a space $\mathbb{V} := \{ \, \text{functions that are linear on each fine triangle of } \mathcal{T}_h \, \}$, $\mathbb{U}_H, \mathbb{U}_h \subset \mathbb{V}$; then we define a mapping $\phi \, : \, \mathbb{V} \longrightarrow \mathbb{U}_h$ as follows:

$$ (\phi \, v)(x) = \frac{1}{2} \left( v|_{t_1}(x) + v|_{t_2}(x) \right) $$

for each pair of fine triangles $t_1$ and $t_2$ that share a rib ($x$ is a midpoint of the rib). Now we are able to define our operator:

$$ P \, : \, \mathbb{R}_H \stackrel{\mathcal{P}_H}{\longrightarrow} \mathbb{U}_H \subset \mathbb{V} \stackrel{\phi}{\longrightarrow} \mathbb{U}_h \stackrel{\mathcal{P}_h^{-1}}{\longrightarrow} \mathbb{R}_h. $$

Pattern of sparse matrix $P$,
$\mathcal{P}_H \, \xi$ (red), and $\mathcal{P}_h \, P \, \xi$ (yellow)

So you can see that everything works fine here, too.

iii. Restriction Operators: Here Comes a Problem

In the corresponding literature it is common to see that the rule of thumb of defining a restriction operator is that it should be “somewhat transpose of $P$.” And by “somewhat” they usually mean “multiply by a scalar.”
For one, in [1, p. 436] the prolongation / restriction operators are defined via interpolation / weighting (without information extraction about FE–spaces at hand). In this sense I prefer approaches of [2] and [3] more.

The question is, given $P$ (from (i) and (ii)), how can one canonically define the corresponding restriction $R$?

For the case (i), if I fix some vector $\xi \in \mathbb{R}_h$ and blindly multiply it by $P^T$, I will get the following (I used 3 mesh levels here for the sake of clarity):

$\mathcal{P}_2 \, \xi$ (green), $\mathcal{P}_1 \, P_{1 \rightarrow 2}^T \, \xi$ (blue), and $\mathcal{P}_0 \, P_{0 \rightarrow 1}^T \, P_{1 \rightarrow 2}^T \, \xi$ (red)

So you can see that such “restrictions” are not good at all. And I doubt that multiplication by a scalar will do here. For the case (ii) I have similar problems.

I bet the solution is “hidden” in definitions of the following inner products:

---

[3, p.160]

---

[2, p.110]

---

Please help me to clarify this so I will be able to implement restrictions correctly.

References:

1. Yousef Saad
   Iterative Methods for Sparse Linear Systems (2^nd Edition)
   2003
2. Maxim A. Olshanskii, Eugene E. Tyrtyshnikov
   Iterative Methods for Linear Systems
   2014
3. Susanne C. Brenner, L. Ridgway Scott
   The Mathematical Theory of Finite Element Methods (3^rd Edition)
   2008