טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentZemach Ran
SubjectAlgebraic Collocation Coarse Approximation (ACCA) in
Multigrid
DepartmentDepartment of Computer Science
Supervisor Professor Irad Yavneh
Full Thesis textFull thesis text - English Version


Abstract

Most algebraic multigrid (AMG) methods define 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 affect 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 diffusion problems with sharply varying coefficients, as well as unstructured problems in two and in three dimensions, demonstrate the efficacy and potential of this new multigrid algorithm.