# Algebraic Multigrid: Why does the product of interpolation and restriction not result in something with norm 1?

I'm currently working with "A Multigrid Tutorial" by Briggs et al, Chapter 8.

The construction of the interpolation operator is given as:

Then construction of restriction operator and fine grid operator are given as:

Let's assume we have three grid points x0, x1, x2 with the middle one x1 is fine and the others are coarse. The middle one is interpolated by x1 = x0*w0 + x2*w2. Therefore, the interpolation operator is (in Matlab):

I = [1, 0, 0; w0, 0, w2; 0, 0, 1]

I =

[  1, 0,  0]
[ w0, 0, w2]
[  0, 0,  1]


The restriction operator is then:

transpose(I)

ans =

[ 1, w0, 0]
[ 0,  0, 0]
[ 0, w2, 1]


Now let's see what would happen if one would restrict and then interpolate directly, what results in a multiplication of I and transpose(I):

I*transpose(I)

ans =

[  1,          w0,  0]
[ w0, w0^2 + w2^2, w2]
[  0,          w2,  1]


I would expect that this matrix is something like an identity matrix or would at least have norm 1 or something. But if we would apply x = [1, 1, 1] for lets say w0 = w2 = 0.5, we would get [1.5 1.5 1.5]. I would assume that repeatedly applied restriction-interpolation operations would at least converge to something. But no, in that case all vector components are multiplied by 1.5 on every restriction-interpolation. That seems very strange to me.

Can anyone explain what's going on?

• Your notation is a bit unhelpful in that you write the restriction operator $I$ as a $3\times 3$ matrix. But it should of course map from the fine space of 3 nodes to the coarse space of 2 nodes, so it would be useful to write it as a $2\times 3$ matrix. – Wolfgang Bangerth Dec 7 '15 at 13:41

## 2 Answers

One simpler explanation - the range of the restriction operator is the coarse grid space, while the range of the interpolation operator is the fine grid space. Unless the two are equal, interpolation + restriction will not result in an identity matrix, because there will always be components of $x$ which are truncated by the restriction operator and lost.

• I understand that. But I would at least assume that repeatedly applying restriction and interpolation would converge against something. But no - in the above case all vector elements will be multiplied by 1.5 for every restriction-interpolation. That seems strange to me. – Michael Dec 2 '15 at 21:09
• Sure - some short responses. (1) Smoothing and normalization aren't taken into account, which are usually applied in tandem with interpolation/restriction. (2) Part of it might be the choice of weights. These often correspond to different choices of interpolation/restriction operators, some of which result in provably better behavior than others. (3) There are other interp/restrict operators for which interp+restrict is a projection. For example, you can do global projections from coarse to fine grids, but this is costly and not worth it for a solver. – Jesse Chan Dec 2 '15 at 21:36

There are two parts of the answer. First, you don't get the identity because you throw away information during the restriction operation (if you think of a larger mesh than just the three points you consider, then you "forget" the values of ever other node during restriction), and you cannot recover this information during the transpose operation. Consequently, you will not be able to get the identity operation when applying $I^TI$.

Second, your intuition that you should get something that has a norm around one is correct, and you would if you would choose the prolongation matrix differently. In your statement, you choose it as the transpose of the restriction matrix. This is a convenient choice because it makes the multigrid cycle a symmetric operator. But the transpose of the restriction is not equivalent to the embedding matrix $E$ that would simply interpolate the function values from the coarse grid to the fine grid. If you considered the operator $EI$, then this one has the property you are looking for. In particular, $EI$ is idempotent: if you apply it twice, the result is the same as if you applied it once: $(EI)(EI)=EI$.