# Galerkin projection in AMG

In the context of Classical AMG for elliptic problems discretised with finite elements (DG or CG), one has the (fine) matrix of the problem, say $$A_0$$, and the coarser operators of the hierarchy $$\{A_k\}_k$$ are built through Galerkin projection:

$$A_{k+1}=P_k^TA_kP_k \qquad (\star)$$ being $$P_k$$ the interpolation operator on level $$k$$.

I am wondering the following: suppose that we actually have a coarser grid $$T_{k+1}$$ and a finite element space $$V_{k+1} \subset V_k$$, for which the operator $$P_k$$ is precisely the canonical injection $$V_{k+1} \rightarrow V_k$$. Is $$A_{k+1}$$ defined in ($$\star$$) identical to the matrix one would get by assembling the matrix of the problem explicitely on the space $$V_{k+1}$$ associated to grid $$T_{k+1}$$?

• Sort of yes, but not when $P_k$ is the canonical injection and not with algebraic multigrid. I believe the best intuition for this can be obtained by studying p-multigrid methods. If I have time later, I will try to turn this to an answer; right now I am in a rush and wanted to give a short answer/ask for further clarification. What do you want to achieve in the end? Apr 9 at 3:12
• @AbdullahAliSivas In a nutshell: I want to know if the matrix $A_{k+1}$, obtained through Galerkin projection when $P_k$ is the canonical injection, is the same I would get by explicitly assembling it on a coarser, nested, grid. (Think about the case of a hierarchy of squares). I know GMG would be the best in such case, but I wanted to see the relationships between the projected version of AMG and the explicitely assembled matrix. From your comment it looks like they are not the same :) Apr 9 at 8:38
• Oh, in that case, yes. AMG does not produce the same sequence of matrices as GMG (except maybe for 1-st order continuous galerkin on uniform tensor product grids and Lagrange basis). However, AMG is still unreasonable effective in solving Laplacian discretizated with DG for example. I rarely needed geometric multigrid for "toy" problems, and even for some of more difficult problems where multigrid can be a viable option. Apr 10 at 16:15
• @AbdullahAliSivas So, to summarise, the answer to the question in the original post is no :) Could you please elaborate on that? I was trying to argue by contradiction but I was not able to prove that GMG matrices and AMG matrices are different. Apr 10 at 16:53
• You would have to write the PDE and the elements that you use. Then whether it holds depends on $P_k$ as well as the elements and mesh you have used. Say you have $\Delta u = f$. Then what you want to prove is essentially that linear combinations of the integrals forming your stiffness matrix on the finer grid result in the integral on the coarser grid. That may be the case sometimes, but there is no reason to expect that this is true in general. Apr 14 at 9:20

Sorry, I have been busy lately. I don't have enough time to write the answer I want to, however, here is the short one: In GMG you define the prolongation and restriction operators based on the finite element space you are using. In AMG, matrix is analyzed based on some definition of "strength" of connection between degrees of freedom and that gives the prolongation/restriction operators. Now, there are some cases, for example first order CG discretization of Laplacian equation on uniform grid, these two may be equivalent. In general, they are not.

Imagine that, you are using two finite element spaces with $$V_{k+1} \subset V_k$$, e.g. every function $$f\in V_{k+1}$$ is also a member of $$V_k$$. But the degrees of freedom doesn't have the same property, for example Discontinuous Galerkin Methods. With GMG, you would actually project between these two finite element spaces. With AMG, you take the degrees of freedom in the "fine" space, and separate them into two groups "fine" and "coarse". The "coarse" degrees of freedom may not have a corresponding degree of freedom in the "fine" space.

As an illustration

(--+--+--+--) This is the fine space, end nodes ( and )are not included. + are the degrees of freedom

(---+---+---) This is the coarse space you defined in your method

Given the fine space, AMG may pick (as it only has the matrix as source of information)

(--C--F--C--), resulting in a coarse space approximation

(--+-----+--).

• I see the difference between AMG and GMG more in the sense that in GMG you have coarser meshes where you discretise the problem anew. While in AMG you have the fine matrix $A_k$ which you then compress $A_{k+1} = P^T_kA_k P_k$ to get the matrix on the coarser level. I do not think that it is required that $V_{k+1}\subset V_k$. The latter may not even make sense in AMG. And in GMG if you don't have hierarchical functions this may also not hold. For example having a Delaunay triangulation on a fine and coarse set of vertices with $P_1$ elements - then the spaces are not typically nested. Apr 14 at 9:11
• This is what I wanted say @lightxbulb, but put much better into words :) Apr 14 at 17:03