The data structure derived from non-overlapping domain decomposition can be used easily in iterative solvers. Problems appear with those local matrices containing also information from other subdomains. As long as we accumulate them only locally no problems appear, (distributed) matrices from FEM are typical for that class. Globally accumulated matrices have to fulfill a special admissible pattern property to preserve their easy parallel handling.

If the coarsest grid is distributed statically and if all refined elements belong to the same subdomain as their father element then the standard prolongation/restriction in a MG algorithm requires no communication at all. The same holds for all matrix-by-vector products with the distributed FEM-matrices of all levels.

The situation changes in the case of AMG.
In order to apply the non-overlapping data structure and subroutines of the finest grid also on the coarser grids we have to do the following modifications in comparison with the classical AMG:

• The coarsening is locally hierarchic.
• The prolongation/restriction has to be restricted to admissible matrix patterns, i.e., we use a modification of the classical approach.
• Then, the coarse grid matrices resulting from the Galerkin approach behave again as locally accumulated matrices.

This parallelization strategy is already very useful in an AMG algorithm for matrices without M-matrix property.