M.Sc Student | Zemach Ran |
---|---|

Subject | Algebraic Collocation Coarse Approximation (ACCA) in Multigrid |

Department | Department of Computer Science |

Supervisor | Professor Irad Yavneh |

Full Thesis text |

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.