Thoughts on MGRIT

[JensHahne]

Just a few thoughts from me about MGRIT. I'm still trying to think more in "blocks" than in multiple levels, so maybe it's complete nonsense. But maybe it helps:

1. Formula 3.10 from the review "A unified analysis framework for iterative parallel-in-time algorithms" for FCF-relaxation makes sense to me. But this rule only applies to all blocks n>1, right? To compute n+1 with n-1, we need to restrict ourselves to n-1 >= 0. Do we need an additional block iteration rule for this special case?
   In a multilevel context, I think the number of these special cases would increase. I think that in a multilevel context points which are far before in time effect a point, so that we would have more special cases at the beginning and then a block iteration for the following points.

2. From the perspective of a multigrid model, I really miss a level index \ell. From my point of view we cannot assume that the blocks on each level have the same size, at least this is not the case in MGRIT. I was wondering if it would be possible to write down one block iteration per level and then combine them by somehow "matching" the "(u_n^k)^\ell" (or something with three indices) of the different levels.
   More or less, this is exactly what is done for parareal in the paper in (3.1) and (3.2), and there it is assumed that "(u_n^k)^0" (the fine level blocks) and "(u_n^k)^1" (the coarse level blocks) exactly match.
   This would extend the kn-graphs to three-dimensional knl-graphs. The two-level case would simply be a "special case" where one could get rid of the index l by assuming that both block structures (fine and coarse) match.

Again, these are just a few thoughts on integrating the multi-level MGRIT into the framework. Let me know if this makes sense for you.

[JensHahne]

Hi @tlunet,

I wasn't sure if I needed to tag you to get a notification about the thread. If not, sorry for the spam

[tlunet]

You do need to tag me indeed 😄

[JensHahne]

Ah, good to know.

[tlunet]

About point 1 : yes, that is the main challenge when dealing with non-primary block iteration, i.e depending on index $n-1$, etc ... That happen for MGRIT-FCF, or if you write down a three level TMG with only on pre-relaxation Block Jacobi step before going to coarser level (have those computation written on paper somewhere, still have to write them down properly).

But those non-primary block iteration need to be defined with one primary block iteration for the first block. It's like multistep method : Adam-Bashford method (second order) or Leap Frog need to use Forward-Euler for the first step.

In our case, we can determine what is the associated primary block iteration associated by looking at the first "block" line of the global system. For instance for MGRIT-FCF : apply twice Block Jacobi, then once ABGS. Should not be too hard to write down what the first block line does, just have to not ignore the right hand side $f$ as we did for the primary block iteration.