Abstract
In this paper, we discuss the convergence of an Algebraic MultiGrid
(AMG) method for general symmetric positive-definite matrices. The
method relies on an aggregation algorithm, named coarsening based on
compatible weighted matching, which exploits the interplay between the
principle of compatible relaxation and the maximum product matching
in undirected weighted graphs. The results are based on a general convergence analysis theory applied to the class of AMG methods employing
unsmoothed aggregation and identifying a quality measure for the coarsening; similar quality measures were originally introduced and applied to
other methods as tools to obtain good quality aggregates leading to optimal convergence for M-matrices. The analysis, as well as the coarsening procedure, is purely algebraic and, in our case, allows an a posteriori evaluation of the quality of the aggregation procedure which we apply to analyze
the impact of approximate algorithms for matching computation and the
definition of graph edge weights. We also explore the connection between
the choice of the aggregates and the compatible relaxation convergence,
confirming the consistency between theories for designing coarsening procedures in purely algebraic multigrid methods and the effectiveness of the
coarsening based on compatible weighted matching. We discuss various
completely automatic algorithmic approaches to obtain aggregates for
which good convergence properties are achieved on various test cases.
Anno
2022
Autori IAC
Tipo pubblicazione
Altri Autori
D;Ambra P., Durastante F., Filippone S.,L. Zikatanov