Technical Report MSC-2012-25

Title: Algebraic Collocation Coarse Approximation (ACCA) in Multigrid
Authors: Ran Zemach
Supervisors: Irad Yavneh
Abstract: Most algebraic multigrid (AMG) methods de ne the coarse operators by applying the Galerkin or 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 a ect the complexity of the hierarchy of operators and the overall rate of convergence. A new approach, collocation coarse approximation (CCA), was proposed by Wienands and Yavneh in 2009, 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. In this work, an algebraic generalization of CCA is 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. Numerical experiments for two and three dimensional di usion problems with sharply varying coecients, as well as unstructured problems in two and in three dimensions, demonstrate the ecacy and potential of this new multigrid algorithm.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the MSC technical reports of 2012
To the main CS technical reports page

Computer science department, Technion