next up previous
Next: Bibliography

Artem Napov
Algebraic analysis of aggregation-based multigrid

Université Libre de Bruxelles
Service de Métrologie Nucléaire (CP 165/84)
Avenue F D Roosevelt 50
B-1050 Bruxelles - Belgique
anapov@ulb.ac.be
Yvan Notay

Algebraic multigrid techniques based on coarsening by aggregation [1,2] have gained in popularity over the last years [3,4]. The growing interest for such approaches is motivated by their low setup cost and memory requirements, combined with a (close to) optimal convergence when used with K-cycle [5].

In this talk, we present a convergence analysis of two-grids methods based on aggregation [6]. For diagonally dominant symmetric (M-)matrices, we show that the analysis can be conducted locally; that is, the convergence factor can be bounded above by computing separately for each aggregate a parameter which in some sense measures its quality. The procedure is purely algebraic and can be used to control the quality of automatic coarsening algorithms. Assuming the aggregation pattern sufficiently regular, we show that the resulting bound is asymptotically sharp for a large class of elliptic boundary value problems, including problems with variable and discontinuous coefficients. In particular, the analysis of typical examples reveals that the convergence rate is insensitive to discontinuities under some reasonable assumptions on the aggregation scheme.




next up previous
Next: Bibliography
root 2010-03-09