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

Question

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?

Answer 1

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.

Answer 2

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