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$:

enter image description here

$\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:

enter image description here

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:

enter image description here

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:

enter image description here

$\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:

enter image description here enter image description here

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. $$

enter image description here enter image description here

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):

enter image description here enter image description here $\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:

enter image description here

[3, p.160]

enter image description here

[2, p.110]

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


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.