Algebraic multigrid methods for Laplacians of graphs (Q2431144)

The authors consider the convergence analysis (in the seminorm of the system matrix) of algebraic multigrid methods in the case of singular, symmetric semidefinite matrices with semisimple zero eigenvalue (i.e., the Jordan blocks belonging to it are trivial). For this, they prove a number of theorems replacing the classical ones (concerning the smoothing and approximation properties) along the lines of the Stüben paper in the book by \textit{U. Trottenberg, C. W. Oosterlee} and \textit{A. Schüller} [Multigrid. With guest contributions by A. Brandt, P. Oswald, K. Stüben. Orlando, FL: Academic Press (2001; Zbl 0976.65106)]. Among other things they show that not only the Moore-Penrose inverse can be used in the coarse grid correction operator. Since the motivation for this research is shape optimized load balancing for graph partitioning, they later specialize to irredubible diagonally dominant singular M-matrices (corresponding to Laplacians of graphs), showing that decisive properties are inherited by the Galerkin projection. A number of numerical results concerning timing of setup and iterative solution show that indeed a linear behaviour is maintained for their systems of several \(10^5\) unknowns.