Recently, we proposed the use of maximum weighted matching on the adjacency graph of SPD matrices as a reliable and completely automated way to coarsen sparse matrices in Algebraic Multigrid Methods (AMG).
The algorithm, named coarsening based on compatible weighted matching, exploits a maximum product matching in the original matrix graph to enhance matrix diagonal dominance, reflecting the convergence properties of an appropriately defined compatible relaxation scheme.
The matched nodes are aggregated to form coarse index spaces and standard, piecewise constant or smoothed, interpolation operators are applied for the construction of a multigrid hierarchy, without referring to any a priori knowledge of matrix origin and/or any assumed strength of connection definition. Instead, information about the smooth error is generated and used to de ne edge weights assigned to the original matrix graph.
A key issue in this approach is to find an efficient yet accurate enough computation of a maximum product matching; this accounts for the largest part of the computational time needed to build the AMG solver. The most widely used algorithm for maximum weighted matching generally exhibits a superlinear computational complexity; for our purposes, we needed a linear cost algorithm, thus we resorted to an approximate algorithm producing matchings whose weight is at least 1/2 of the optimum.
Currently, we are considering the use of an auction algorithm for solving the maximum product maximum cardinality matching problem. Auction algorithms have been demonstrated to compute highquality matchings for scaling sparse matrices in Sparse Direct Linear Algebra Computations and they are also readily parallelizable. We show that they can also improve the quality of the coarsening with respect to the previously studied halfapproximate algorithm, giving results which are comparable to the ones obtained by using exact maximum product matching at a reasonable computational cost.
This work is in collaboration with Panayot S. Vassilevki (CASCLLNL) and Salvatore Filippone (University of Cranfiled).
