  This paper is to give an overview of AMG methods for solving large scale
systems of equations such as those from the discretization of partial
differential equations. AMG is often understood as the acronym of "Algebraic
Multi-Grid", but it can also be understood as "Abstract Muti-Grid". Indeed, as
it demonstrates in this paper, how and why an algebraic multigrid method can be
better understood in a more abstract level. In the literature, there are a
variety of different algebraic multigrid methods that have been developed from
different perspectives. In this paper, we try to develop a unified framework
and theory that can be used to derive and analyze different algebraic multigrid
methods in a coherent manner. Given a smoother $R$ for a matrix $A$, such as
Gauss-Seidel or Jacobi, we prove that the optimal coarse space of dimension
$n_c$ is the span of the eigen-vectors corresponding to the first $n_c$
eigenvalues of $\bar RA$ (with $\bar R=R+R^T-R^TAR$). We also prove that this
optimal coarse space can be obtained by a constrained trace-minimization
problem for a matrix associated with $\bar RA$ and demonstrate that coarse
spaces of most of existing AMG methods can be viewed some approximate solution
of this trace-minimization problem. Furthermore, we provide a general approach
to the construction of a quasi-optimal coarse space and we prove that under
appropriate assumptions the resulting two-level AMG method for the underlying
linear system converges uniformly with respect to the size of the problem, the
coefficient variation, and the anisotropy. Our theory applies to most existing
multigrid methods, including the standard geometric multigrid method, the
classic AMG, energy-minimization AMG, unsmoothed and smoothed aggregation AMG,
and spectral AMGe.
