The Role of Energy Minimization in Algebraic Multigrid Interpolation
For researchers in algebraic multigrid methods, this work provides theoretical insights and a new preconditioner, but the proposed method is incremental and does not achieve practical improvements.
This paper reviews AMG convergence theory and proposes a weighted energy minimization functional for interpolation, alongside a novel diagonal preconditioner for Sylvester/Lyapunov equations. Numerical results show the approach underperforms compared to fully constrained energy minimization but offers new insights into energy minimization and constraint vectors in AMG interpolation.
Algebraic multigrid (AMG) methods are powerful solvers with linear or near-linear computational complexity for certain classes of linear systems, Ax=b. Broadening the scope of problems that AMG can effectively solve requires the development of improved interpolation operators. Such development is often based on AMG convergence theory. However, convergence theory in AMG tends to have a disconnect with AMG in practice due to the practical constraints of (i) maintaining matrix sparsity in transfer and coarse-grid operators, and (ii) retaining linear complexity in the setup and solve phase. This paper presents a review of fundamental results in AMG convergence theory, followed by a discussion on how these results can be used to motivate interpolation operators in practice. A general weighted energy minimization functional is then proposed to form interpolation operators, and a novel `diagonal' preconditioner for Sylvester- or Lyapunov-type equations developed simultaneously. Although results based on the weighted energy minimization typically underperform compared to a fully constrained energy minimization, numerical results provide new insight into the role of energy minimization and constraint vectors in AMG interpolation.