Graph explorer

Algebraic Multigrid Methods

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