M. Griebel, B. Metsch, D. Oeltz, and M. A. Schweitzer.
Coarse grid classification: A parallel coarsening scheme for
algebraic multigrid methods.
Numerical Linear Algebra with Applications, 13(2-3):193-214,
Also available as SFB 611 preprint No. 225, Universität Bonn, 2005.
[ bib | .ps.gz 1 | .pdf 1 ]
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 does not involve any 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 all admissible grids such that the composed coarse grid forms a suitable coarse grid for the whole domain, i.e. there is no need for any 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-up behavior of the proposed algorithm is similar to that of other parallel AMG techniques. However a significant improvement with respect to the speed-up performance is achieved.