The Taub Faculty of Computer Science Events and Talks

Most algebraic multigrid (AMG) methods define the coarse operators by applying the (Petrov-) Galerkin coarse approximation (GCA) where the sparsity pattern and operator complexity of the multigrid hierarchy are dictated by the multigrid transfer operators (prolongation and restriction). Therefore, AMG algorithms must usually settle on some compromise between the quality of the transfer operators and the aggressiveness of the coarsening, which affect the complexity of the hierarchy of operators and the overall rate of convergence. A new approach, collocation coarse approximation (CCA), was proposed in 2009 by Wienands and Yavneh, where the coarse approximation is not based on the Galerkin formula and the choice of the sparsity pattern of the coarse-grid operators is completely independent of the choice of the transfer operators, P and R. In this work, an algebraic generalization of CCA was studied, leading to a new algorithm which is fully algebraic and which is based on the aggregation framework (smoothed and non-smoothed adaptive aggregation). The algorithm determines the coarse-grid operator sparsity pattern using pure aggregation, while it computes the nonzero values using a small set of low-energy eigenvectors by a weighted least squares process. Both CCA and ACCA algorithms are particularly worthwhile for parallel settings. The ACCA algorithm is quite scalable and robust and may be advantageous in cases where strict sparsity constraints prevent us from using high-quality GCA operators. Numerical experiments for two dimensional diffusion problems with sharply varying coefficients, as well as problems with unstructured settings in two and in three dimensions, demonstrate the efficacy and potential of this new multigrid algorithm.