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 high-quality 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 half-approximate 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 (CASC-LLNL) and Salvatore Filippone (University of Cranfiled).

Pasqua D'Ambra is senior scientist of the National Research Council of Italy (CNR) at the Institute for Applied Computing "Mauro Picone". She received a PhD in Applied Mathematics and Computer Science and an Ms in Applied Mathematics from the University of Naples Federico II. 
She has been collaborating with Center for Applied Scientific Computing at Lawrence Livermore National Laboratory since 2011.  She has taught various undergraduate courses in both Computer Science and Mathematics. Her research activity is collocated in the context of high-performance scientific computing, with particular emphasis on parallel numerical algorithms and software for scientific simulation.

Current research topics include algebraic multilevel preconditioners for sparse linear systems and numerical solution of partial differential equations, with applications to computational fluid dynamics and image analysis. The research activity is generally carried on within national and international projects where Pasqua D'Ambra is often PI.

Currently she is responsible for CNR of the Energy Oriented Center of Excellence (EoCoE), A Center of Excellence in Computing Applications funded by Horizon 2020 EC Program for Research and Innovation.