AMG Preconditioners based on Parallel Hybrid Coarsening and Multi-objective Graph Matching

We describe preliminary results from a multiobjectivegraph matching algorithm, in the coarsening step of anaggregation-based Algebraic MultiGrid (AMG) preconditioner,for solving large and sparse linear systems of equations on highendparallel computers. We have two objectives. First, we wishto improve the convergence behavior of the AMG method whenapplied to highly anisotropic problems. Second, we wish to extendthe parallel package PSCToolkit to exploit multi-threadedparallelism at the node level on multi-core processors. Ourmatching proposal balances the need to simultaneously computehigh weights and large cardinalities by a new formulation ofthe weighted matching problem combining both these objectivesusing a parameter ?. We compute the matching by a parallel2/3 - ?-approximation algorithm for maximum weight matchings.Results with the new matching algorithm show that for a suitablechoice of the parameter ? we compute effective preconditionersin the presence of anisotropy, i.e., smaller solve times, setup times,iterations counts, and operator complexity.