Function-based Algebraic Multigrid method

Geometric or Algebraic Multigrid are among the methods to solve linear systems of equations that are most often used today. The origin of these methods is found in the works of Radiy Fedorenko in 1964 and Nikolay Bakhvalov in 1966. Their algorithmic framework has been developed and enhanced in the 70s with the significant contributions of Archi Brandt, Wolfgang Hackbusch and many others. Today MG is one of the methods of choice for a vast amount of algebraic systems arising from discretized partial differential equations (PDEs).

The reason for MG/AMG to be so attractive lies in the optimality properties of the method. Namely, MG has an optimal convergence rate, independent of the number of degrees of freedom, N (and in many cases, independent on other problem parameters). In other words, MG converges in a fixed number of iterations, that does not depend on the matrix size. Furthermore, the number of arithmetic operations per iteration is linearly proportional to the number of degrees of freedom, ensuring that the total computational cost of the AMG solve is O(N).

As the name suggests, MG are related to a sequence of nested (conforming) meshes or algebraically constructed levels. Its ingredients consist of a sequence of matrices of decreasing order, restriction and prolongation operators, usually available also in the form of rectangular matrices, again of decreasing order and the so-called smoothers – cheap and simple iterative solution methods that are evoked on each level of the hierarchy. The method traverses the so constructed hierarchy and contributes to error reduction in each level.

Although possessing these optimality properties, MG has its drawbacks. For instance, for large systems of equations it might require a lot of memory and large construction times. The smoothers are problem dependent and have to be chosen carefully. In AMG setting the coarse level matrices have to be carefully constructed to possess approximation properties, thus, they should somehow approximate the equation on these levels. Also, an important issue to take care of is that MG requires communications between levels, and on the coarse levels the distances to communicate over become larger.

In this project we consider a case when the matrix on the fine level can be characterized by an analytic function, referred to as the symbol. Such a function can be associated with certain structured matrices of Toeplitz form. Toeplitz matrices possess the property that their entries along each diagonal are the same. Many matrices that arise from partial differential equations, discretized for example using finite differences or finite elements, possess such structure. The theory is also generalized for block-Toepltz matrices, i.e., instead of entries, we have the same blocks along the diagonals.

Some methods have been developed to construct MG algorithms, based on the matrix symbol. There exists a working code in Matlab that constructs a symbol-based MG for the linear elasticity equation.

Tasks:
1: Get acquainted with the Multigrid algorithm.
2: Understand the theory of matrix symbols (in general terms).
3: Convert the existing MATLAB code to equivalent C (or C++) code.
4: Work on the efficiency of the new code with respect to memory. This task requires reconsideration of the implementation in Matlab, where all matrices, prolongations and restrictions are constructed explicitly. Instead, consider the option to recompute these matrices whenever needed. This would make the method of potential interest to be run on multicore computer architectures or GPUs, where the expensive part is the communication and the computations are fast and relatively cheap.

(Parallelization of the code lies beyond this course.)

Bibliography:
R. P. Fedorenko (1961), A relaxation method for solving elliptic difference equations. USSR Comput. Math. Math. Phys. 1, p. 1092.
R. P. Fedorenko (1964), The speed of convergence of one iterative process. USSR Comput. Math. Math. Phys. 4, p. 227.
N. S. Bakhvalov (1966), On the convergence of a relaxation method with natural constraints on the elliptic operator. USSR Comp. Math. Math. Phys. 6, 101–13.
Achi Brandt (April 1977), "Multi-Level Adaptive Solutions to Boundary-Value Problems", Mathematics of Computation, 31: 333–90.
William L. Briggs, Van Emden Henson, and Steve F. McCormick (2000), A Multigrid Tutorial (2nd ed.), Philadelphia: Society for Industrial and Applied Mathematics, ISBN 0-89871-462-1.

Supervisors:
Ali Dorostkar, Maya Neytcheva