On the Spectral Clustering of a Class of Multigrid Preconditioners
This work addresses the design of efficient preconditioners for numerical linear algebra, offering incremental improvements in optimizing AMG cycles for specific matrix classes.
The paper tackles the problem of optimizing algebraic multigrid (AMG) schemes for solving complex-valued linear systems by analyzing the spectral behavior of a symmetric cycle variant, resulting in an explicit choice of smoothing parameters that collapses eigenvalues to a known value and provides a new closed-form formula for matrix inversion.
We consider an algebraic multigrid (AMG) scheme for the direct solution of complex- valued square linear systems based on a recursive 2 x 2 block partitioning of the coefficient matrix and study the optimal choices of its components. In particular, we complement existing results that characterize the optimal choices for a nonsymmetric cycle method by analyzing the spectral behavior of its symmetric cycle variant. We analyze the error propagation operator of a specific two-level symmetric cycle method by calculating its invariant subspaces and its nonzero eigenvalues that influence the behavior of the error after a single cycle. We show that the error propagation operator can be studied separately for pairs of modes, working as bases of the invariant subspaces. The main result is an explicit choice of smoothing parameters that makes all the pairs of modes respond identically, forcing the nontrivial eigenvalues of the error propagation operator to collapse to a single, a priori known value. As a consequence, we give a new closed form formula for the inverse of a general square matrix. Additionally, the framework provides a clear, self-contained description of an ideal AMG K-cycle, offering a concrete target for the design of related schemes. We illustrate the theory with direct applications to general matrices and with analyses of representative matrices arising in numerical methods.