Auxiliary Space Multigrid Method Based on Additive Schur Complement Approximation for Graph Laplacian
For researchers solving large graph Laplacian systems, this provides a flexible multigrid solver that avoids restrictive coarsening assumptions, though results are only demonstrative.
This work applies an auxiliary space multigrid method with additive Schur complement approximation to graph Laplacian matrices, offering a purely algebraic, structure-independent coarsening strategy with analyzable complexity. Numerical experiments demonstrate its effectiveness.
This research explores the application of the auxiliary space multigrid method (ASMG) that is based on additive Schur complement approximation (ASCA) to graph Laplacian matrices arising from general graphs. A major predicament when considering algebraic multigrid (AMG) methods on such graphs is the choice of a general coarsening strategy which has to be both cheap and effective. Such a strategy has been incorporated in the presented approach which in addition has several advantages. First, it is purely algebraic in its construction which makes the algorithm easy to implement. Furthermore, the approach requires no limitation on the graph's structure and itself can be adjusted to the particular problem. Last but not least, its computational complexity can be easily analysed. A demonstrative set of numerical experiments is presented.