I need detailed explanation of the formula below


I suppose this formula computes matrix A2 on a coarse grid and here A1 is original matrix on fine grid.

So A1 is given, but I don't know I1 and I2. That is why I am asking where I can get these matrices I1 and I2.

In "Briggs, Multigrid Tutorial, SIAM, 2000" at page 52 "1D Restriction by injection" is explained. There they simply drop every second point in a graph to move into coarse grid and then calculate average of neighbouring points to come back to the fine grid.

But I am working with two-dimensional matrix A1. Does that mean that I must drop every second element in one row of matrix or drop every second row to get smaller matrix in coarser grid?

Because I want to solve system of linear algebraic equations using multigrid method.My question is how to relate technique explained at that book(page 52) to the two dimensional matrix A? If formula above is a way, then what is I1 and I2 and how to find them?


1 Answer 1


Given interpolation $I_H^h$ and restriction $I_h^H$ (where restriction is typically $(I_H^h)^T$ for symmetric problems), with fine grid discretized operator $A^h$, there are two common approaches for constructing the coarse grid operator $A^H$.

(Petrov-)Galerkin coarse operators

This explicitly computes the matrix triple product $$ A^H = I_h^H A^h I_H^h .$$ This has well-developed convergence theory for symmetric problems (including those with low regularity) and is a black-box procedure, requiring only the matrices with no information about the underlying problem. When used with finite element methods, the coarse operators can be interpreted as a FEM discretization in some coarse grid with "multiscale" basis functions. For unstructured problems, coarse Galerkin operators often have "stencil growth", in which the number of nonzeros per row grows "excessively". Aggressive coarsening helps reduce stencil growth at the expense of less robustness/slower convergence. Computing the triple product is relatively expensive, especially in parallel, usually representing the majority of the setup time for algebraic multigrid.

Rediscretized coarse operators

If your coarse grids are geometrically meaningful, you can defined $A^H$ by explicitly rediscretizing your equations on the coarse grid. This can be generalized further, e.g., to discretize a different equation set that is more appropriate at that coarse scale. Extreme examples of this include using lower-dimensional integrated models for coarse grids, or even combining fine-grid Monte-Carlo simulations with macro-scale deterministic PDEs. Rediscretization is much more popular than Galerkin coarse operators for steady-state fluids solvers, and fixes the "stencil growth" problem at the expense of requiring more problem knowledge and typically lower robustness for problems with multiscale coefficients. When rediscretization is used, it is usually possible to eliminate all assembled matrices from the algorithm, thus reducing memory requirements.

  • $\begingroup$ @NurlanKenzhebekov I interpreted your question as asking how to define the operator $A$ on coarse grids. Asking precise questions is an essential part of this site. If you want someone to spend X minutes writing an answer, you should spend at least that long writing a precise question that makes it clear what research you have done and where exactly you are stuck. You were pointed to these references two weeks ago. Tell us which of those references you are reading and where you got stuck. $\endgroup$
    – Jed Brown
    Commented Jan 23, 2013 at 12:42
  • $\begingroup$ @NurlanKenzhebekov When ready, you can edit your question to ask about whatever you're stuck on. Note that this site is intended for targeted questions rather than broad overviews. It's meant to augment books and other resources rather than to replace them. $\endgroup$
    – Jed Brown
    Commented Jan 23, 2013 at 12:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.