Parallel Algebraic Multigrid

Klaus Stüben
Arnold Krechel
GMD/SCAI, Germany


In contrast to geometric multigrid methods, in algebraic multigrid (AMG) methods the construction of a hierarchy of coarser levels, including the corresponding transfer operators, is part of the algorithm. The information required for an automatic coarsening is taken from the given finest-level matrix. For various types of matrices, this approach has proven to be robust, efficient and very flexible. In particular, AMG can directly be applied to a wide range of discretized elliptic PDEs on unstructured grids, both in 2D and 3D.

Since the hierarchy of coarser levels and the related operators develop dynamically during the setup phase of an AMG algorithm, it is quite difficult to parallelise AMG efficiently. A "native" parallelisation would, in general, require unpredictable and highly complex communication patterns which seriously limit the achievable efficiency, in particular of the setup phase. In addition, the original AMG approach contains inherently sequential algorithmic components to construct the coarser levels.

A parallelisation approach is presented which limits the communication without sacrificing convergence in complex situations. Results will be presented for industrial CFD applications on various parallel machines.