Technical Report 2017-022

Function-Based Algebraic Multigrid Method for the 3D Poisson Problem on Structured Meshes

Ali Dorostkar

October 2017

Abstract:

Multilevel methods, such as Geometric and Algebraic Multigrid, Algebraic Multilevel Iteration, Domain Decomposition-type methods have been shown to be the methods of choice for solving linear systems of equations, arising in many areas of Scientific Computing. The methods, in particular the multigrid methods, have been efficiently implemented in serial and parallel and are available via many scientific libraries.

The multigrid methods are primarily used as preconditioners for various Krylov subspace iteration methods. They exhibit convergence that is independent or nearly independent on the number of degrees of freedom and can be tuned to be also robust with respect to other problem parameters. The methods also possess optimal computational complexity. As a drawback, of particular importance when solving very large scale problems, we point out their high demand for computer memory. Since the methods utilize hierarchical structures, where the amount of computations decreases and that of communication increases, their parallel implementation might exhibit lesser scalability. Further, as the implementation usually relies on sparse matrix-vector multiplications, this may also decrease parallel performance for very large problems.

In this work we utilize a different framework to construct multigrid methods, based on an analytical function representation of the matrix, that may keep the amount of computation high and local and may reduce significantly the memory requirements. The approach is particularly suitable for modern computer architectures. An implementation of the latter for the three-dimensional discrete Laplace operator is derived and implemented. The same function representation technology is used to construct smoothers of approximate inverse type.

Note: Updated 2017-10-26.

Available as PDF (503 kB, no cover)

Download BibTeX entry.