Algebraic multigrid methods for Laplacians of graphs

作者：Bolten Matthias^*; Friedhoff Stephanie; Frommer Andreas; Heming Matthias; Kahl Karsten

来源：Linear Algebra and Its Applications, 2011, 434(11): 2225-2243.

DOI：10.1016/j.laa.2010.11.008

• Graph partitioning
• Algebraic multigrid methods
• Singular systems
• Laplacians of graphs
• Convergence analysis

Classical algebraic multigrid theory relies on the fact that the system matrix is positive definite. We extend this theory to cover the positive semidefinite case as well, by formulating semiconvergence results for these singular systems. For the class of irreducible diagonal dominant singular M-matrices we show that the requirements of the developed theory hold and that the coarse level systems are still of the same class, if the C/F-splitting is good enough. An important example for matrices that are irreducible diagonal dominant M-matrices are Laplacians of graphs. Recent shape optimizing methods for graph partitioning require to solve singular linear systems involving these Laplacians. We present convergence results as well as experimental results for numerous graphs arising from finite element discretizations with up to 10(6) vertices.

• 出版日期2011-6-1