On the quality of matching-based aggregates for algebraic coarsening of SPD matrices in AMG.

In this paper, we discuss a quality measure for an aggregation-based coarsening algorithm, named {\em coarsening based on compatible weighted ma\-tch\-ing}, which relies on the interplay between the principle of compatible relaxation and the maximum product matching in weighted graphs. The measure we propose is based on a recent general convergence analysis theory applied to the class of multigrid methods employing unsmoothed aggregation. The analysis, as well as the coarsening procedure, is purely algebraic and allows a \emph{a posteriori} evaluation of the quality of the aggregates. The connection between the choice of the aggregates and the compatible relaxation principle is highlighted, confirming the consistency between available theories for designing effective coarsening procedure in purely algebraic multigrid methods and the effectiveness of the coarsening based on compatible weighted matching. We discuss general methods to obtain aggregates for which good convergence properties are achieved, as well as their application to various test cases.