Algebraic multigrid methods for Laplacians of graphs (Q2431144)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Algebraic multigrid methods for Laplacians of graphs |
scientific article |
Statements
Algebraic multigrid methods for Laplacians of graphs (English)
0 references
11 April 2011
0 references
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.
0 references
algebraic multigrid
0 references
singular systems
0 references
convergence analysis
0 references
graph partitioning
0 references
Laplacians of graphs
0 references
Moore-Penrose inverse
0 references
coarse grid correction
0 references
numerical results
0 references
0 references