Coarse grid classification: a parallel coarsening scheme for algebraic multigrid methods

In this paper, we present a new approach to the parallelization of algebraic multigrid (AMG), i.e. to the parallel coarse-grid selection in AMG. Our approach involves (almost) no special treatment of processor subdomain boundaries and hence avoids a number of drawbacks of other AMG parallelization techniques. The key idea is to select an appropriate (local) coarse grid on each processor from a set of admissible grids such that the composed coarse grid forms a suitable coarse grid for the whole domain, i.e. there is no need for a special boundary treatment. To this end, we first construct multiple equivalent coarse grids on each processor subdomain. In a second step we then select exactly one grid per processor by a graph clustering technique. The results of our numerical experiments clearly indicate that this approach results in coarse grids of high quality which are very close to those obtained with sequential AMG. Furthermore, the operator and grid complexities of our parallel AMG are mostly smaller than those obtained by other parallel AMG methods, whereas the scale-Lip behaviour of the proposed algorithm is similar to that of other parallel AMG techniques. However a significant improvement with respect to the speed-Lip performance is achieved. Copyright (c) 2006 John Wiley & Sons, Ltd.