Multigrid methods (MG) are known to be optimal solvers for elliptic
PDE's, i.e. they only require

Algebraic Multigrid methods (AMG) overcome this problem. These methods first
employ a *setup phase* to create a hierarchy of meshes,
transfer and coarse grid operators using with information from the
matrix *solution
phase*, i.e. the multigrid cycle.

While the parallelization of the solution phase is straightforward,
this is not true for the setup phase. Especially the classical
algorithm for the construction of the coarse grids is inherently
sequential.

Different approaches to the parallelization have been proposed over
the years. Some of them use the classical Ruge-Stüben
coarsening scheme in the interior of each processor subdomain an a
employ a special treatment at the boundaries to fix
inconsistencies. Other algorithms employ parallel Maximal Independent
Set techniques to create the coarse grid.

In our parallel coarsening scheme, the **Coarse grid Classification
(CGC)** algorithm, we aim to keep the classical Ruge-Stüben coarsening scheme,
which works excellent in the sequential case. Furthermore, we avoid
inconsistencies at the subdomain boundaries instead of fixing them. We do so by first creating
*multiple candidate coarse grids* on each processor
subdomain. In a second stage, we assemble a consistent coarse grid,
i.e. out of the candidate coarse grids we choose one coarse grid per
processor subdomain such that they match at the interfaces.

The CGC coarsening algorithm is included in two software packages.

- A parallel AMG solver library was build using the PETSc framework. This implementation is used inside our multiphase CFD software NaSt3DGPF based on the free flow solver NaSt3DGP.
- We have contributed an implementation of the CGC coarsening
algorithm for
*BoomerAMG*, the parallel AMG solver in*hypre*(high performance preconditioners) developed at Lawrence Livermore National Laboratory, Center for Applied Scientific Computing, Scalable Linear Solvers Group. The CGC is available in*hypre*version 2.2.0b and higher.

AMG methods discover this density jump and construct suitable coarse grids to provide an efficient preconditioner or solver. To reduce the memory overhead, a parallel AMG coarsening scheme should construct grids that stay as close as possible to the grid produced by the sequential algorithm. In the following, we present the three finest grids produced by the sequential algorithm (left) and by our parallel CGC method (right), where the domain is distributed on four processors.