A Theory of Relaxation-Based Algebraic Multigrid
This work provides a foundational theory for AMG methods, potentially enhancing their efficiency and applicability in numerical simulations, though it appears incremental as it builds on existing formalisms.
The authors tackled the problem of analyzing algebraic multigrid (AMG) methods by proposing a theoretical approach centered on relaxation, treating error relaxation as a dynamical system to derive exact expressions for coarse-level equations and interpolation operations. This framework recovers known results for non-symmetric systems and identifies dynamical corrections that could improve convergence, robustness, and adaptivity in future AMG methods.
Algebraic multigrid (AMG) methods derive their optimal efficiency from the interplay between a relaxation process and a corresponding coarse grid correction. In many standard formulations, relaxation and coarse-graining are analyzed and treated as largely separate of one another. Here we propose an alternative theoretical approach centered entirely on the relaxation process, which exposes its fundamental role in the coarse-graining of the fine-scale problem. By treating the relaxation of the error as a dynamical system and applying a dimensional-reduction procedure analogous to the Mori-Zwanzig-Nakajima formalism, we derive exact expressions for the coarse-level equations and the interpolation operations, as well as a natural way of computing complementary transfer operators. We illustrate the unifying nature of this framework by recovering several well-known results for general non-symmetric systems, including ideal and optimal restriction and interpolation, as well as the limiting case of exact elimination. We further emphasize the pivotal importance of compatible-relaxation and identify dynamical corrections that naturally arise in our theory, which have the potential to enhance the convergence, robustness, and adaptivity of future algebraic multigrid methods.