What is the global problem in the two-level additive Schwarz?

Question

The two-level additive Schwarz method (additive Schwarz with a coarse space correction) is often written like this: $$ \mathbf{v} = \sum_{i=0}^N \mathbf{R}_i^T \mathbf{A}^{-1}_i\mathbf{R}_i\mathbf{w} $$

where the term $i=0$ is said to be the coarse space correction. $\mathbf{A}_0$ is the solver for a global coarse grid problem, $\mathbf{R}_0$ and $\mathbf{R}_0^T$ the restriction and interpolation operators, respectively.

My question is, how to construct $\mathbf{A}_0$? Which problem does it correspond to? I get the idea of creating a coarse mesh, in fact, I am already using a coarse mesh to make an initial guess for what the solution of the global problem should be. But the two-level additive Schwarz method solves a coarse problem in each iteration and I don't understand what problem this is supposed to be. I assume we are not solving the same coarse grid problem over and over, something must change in between the iterations.

Answer 1

Continuous finite elements

Typically, if $A$ is your finite element discretization on the finest mesh, $A_i = R_i * A * R_i^T$. So, for $i=0$, $A_0$ corresponds to the finite element discretization of your problem on the coarsest mesh.

If $R_0$ and $R_0^T$ are algebraically defined, you can use the "Galerkin" triple product to form $A_0=R_0 * A * R_0^T$. This is what is done in algebraic multigrid. If $R_0$ and $R_0^T$ have geometric meaning, $A_0$ can be constructed by simply assembling your finite element problem on the coarsest mesh.

Within the two-level additive Schwarz iteration, usually the matrices $A$ and $A_0$ remain fixed. If you are trying to solve $Ax=b$, and $x_j$ is your previous guess to the problem, then the $j+1$ iteration of the two-level additive Schwarz method looks like

$$x_{j+1} = x_j + \sum_{i=0}^N R_i^T A_i^{-1}R_i (b-Ax_j).$$

In other words, the matrices $A_0$ and $A_i$ do not depend on $j$. Chapter 4 in this free book explains why a coarse space is useful.

Nonlinear problems

For Nonlinear problems that are resolved with an outer Newton or Picard iteration, the matrices $A$ and $A_0$ are dependent on the outer iteration.

Spectral elements

In the case of spectral elements, many authors select $A_0$ so that it corresponds to a finite element problem on the coarsest mesh with a smaller polynomial order (for example look at Fischer et al and Pasquetti et al).

Discontinuous Galkerin methods

It has been shown that the selection of coarse spaces for discontinuous Galkerkin methods can be a little more sensitive. Further details can be seen in the following references Olson et al, Dobrev et al, Antonietti, and Collins.