Algebraic Multigrid

Algebraic Multigrid (AMG) Solvers

AMG solvers are iterative solvers for discrete classical field problems. Ideally they should require no input other than the system matrix. The iterative process uses a successive relaxation of residual errors to drive successive approximations to an acceptable level of convergence. If the solvers are to qualify as broadband solvers, both long-range and short-range errors must be relaxed simultaneously (within each iterative cycle). For a true broadband solver, the convergence rate will be constant, independent of the iteration count and of the discretization bandwidth. This is achieved by the local relaxation of the errors (smoothing) on a hierarchy of algebraically-reduced (coarsened) representations of the system which may be viewed as a hierarchy of grids (the directed graphs of the associated matrices). They span the entire range from the finest reference grid (on which the shortest-range errors are relaxed) to the coarsest grid (on which the longest-range errors are relaxed). The latter may consist of just a few grid points (or even a single point). Each iterative cycle begins by relaxing the errors on the finest grid and then recursively relaxing and restricting the residual errors down through the hierarchy to the coarsest. The full-bandwidth correction is then assembled by reversing the procedure, with a recursive prolongation and addition of corrections up through the hierarchy, at each stage smoothing out any short range errors that may be introduced by the process.

Stained glass artist Moira Webster's depiction of algebraic coarsening ( see The Glass Stramash )

The two AMG solver types are Classical AMG (C-AMG) and Aggregation AMG (SA-AMG). In C‑AMG, system reduction is based on subset selection coarsening. In SA-AMG, system reduction is based on aggregation coarsening. Either method can be used as long as the grid points (equations) can be sensibly combined in the case of SA-AMG and as long as subsets of grid points are sensibly representative in the case of C-AMG. However, contrary to the AMG aspiration (of requiring no information other than that contained in the system matrix) it may not always be possible to meet these criteria using the system matrix alone. Additional, explicit, topological information about the equations may be necessary in order to decide. Not satisfying them does not necessarily prevent solutions, but it can compromise the consistency of the coarse-grid approximations. This would, in turn, compromise the bandwidth of each iterative correction and, thereby, the most important AMG aspiration, constant rates of convergence.

The following graph compares the relative cost of solving 4th-order discrete-difference

equations of incompressible fluid flow using:-

Algebraic Multigrid methods (A & B) and Krylov methods (C & D).

The field variable computed is a scalar (an integrated stream function) see amg_sn.pdf.

The solvers are described in reprints given in “Publications”.

It is clear that the relative cost of AMG methods (unlike those of established Krylov methods) is independent of the bandwidth, Q, of the discretization. This reflects the fact that for AMG convergence factors can be independent of the bandwidth or the size of the computational mesh.

The difference between cases A and B is that A is a solution for a uniform unstructured mesh whereas B is for a non-uniform unstructured mesh.

The algebraic grid

Within the solver we refer to matrix equation systems using the grid concept. A grid may be viewed as the directed graph of the system matrix. Thus there is a one-to-one correspondence between the diagonal entries of the matrix and the nodes (points) of the corresponding grid; likewise there is a one-to-one correspondence between off-diagonal entries of the matrix and the connections between grid points. When the input equation system is prepared in block matrix form, the block classification of each equation is immediately evident from its position in the matrix. However, to allow the block structure to be respected within the solver without any such explicit ordering, this information needs to be explicitly included with the grid-point data.

Classification of grid points

A proper classification of grid points facilitates the enforcement of the appropriate coarsening criterion. Thus within any particular class only those points are included that will admit a sensible aggregation (in the case of SA-AMG) or a valid subset selection (in the case of C-AMG). Each class can then be coarsened separately so that classes are conserved during coarsening and thus consistently represented at each coarse level.

Clearly an obvious qualification for class membership is that grid points within the class should refer to the same field equation. If we are limited to scalar algebra, points within a class should also refer to the same vector component when dealing with a vector field. Likewise, grid points within a class should also refer to similar, and similarly oriented, space elements of the mesh so that grid points can be consistently combined (in the case of SA-AMG coarsening) and subsets consistently representative (in the case of C‑AMG coarsening). Where grid points within a class do not satisfy the criteria, the class must be subdivided so that aggregation or subset selection is admissible within the subdivisions.

As an example, consider the case of a 2D vector field problem which is discretised on an unstructured mesh of triangular elements for which there is a fixed, face-based variable; say the normal component of the fluid flux. Here we have a system of simple scalar equations that might be solved for the normal fluxes by standard iterative methods (such as Krylov methods). Nevertheless, without a knowledge of the orientation of the faces to which they refer, the equations cannot be consistently combined. Moreover, the faces could be quite randomly oriented, so it would not be possible to partition them into a few classes of high occupancy. In effect it would be as if each equation is in a class of its own. As there are no subsets of sets whose occupancy is unity, the system could not therefore be reduced consistently. So, although it may be solved by SA-AMG or by C-AMG (by putting all grid points into one class regardless) the solution could not be efficient from a multigrid perspective since the CGA could not be consistent. Without a consistent CGA, convergence rates for the longer range errors will be poor and mesh dependent. Convergence factors will asymptotically approach unity as mesh bandwidth is increased and the time required to achieve an acceptable level of convergence may be impractically long (without the help of some additional accelerator).

As a more favourable example, consider the case where grid points refer to a point-based vector field variable. If the AMG algorithm had had a capability for vector algebra then all N points of the grid could have been placed in a single class. When however, the C-AMG and SA-AMG coarsening algorithms only allow for scalar algebra, each grid point can only represent a scalar variable. The vector equation must therefore be split into several orthogonal scalar equations one for each of the Cartesian components. Consequently, this will extend the number of field equations, grid points and required classes by a factor d for a d-dimensional problem. The occupancy of each class will still be N, so there is the same scope for coarsening in each class (which may or may not be correlated between classes).