Accelerated multigrid for graph Laplacian operators

Dell’Acqua, Pietro, Antonio Frangioni and Stefano Serra-Capizzano

Applied Mathematics and Computation, 2015, vol. 270, issue C, 193-215

Abstract: We consider multigrid type techniques for the numerical solution of large linear systems, whose coefficient matrices show the structure of (weighted) graph Laplacian operators. We combine ad hoc coarser-grid operators with iterative techniques used as smoothers. Empirical tests suggest that the most effective smoothers have to be of Krylov type with subgraph preconditioners, while the projectors, which define the coarser-grid operators, have to be designed for maintaining as much as possible the graph structure of the projected matrix at the inner levels. The main theoretical contribution of the paper is the characterization of necessary and sufficient conditions for preserving the graph structure. In this framework it is possible to explain why the classical projectors inherited from differential equations are good in the differential context and why they may behave unsatisfactorily for unstructured graphs. Furthermore, we report and discuss several numerical experiments, showing that our approach is effective even in very difficult cases where the known approaches are rather slow. As a conclusion, the main advantage of the proposed approach is the robustness, since our multigrid type technique behaves uniformly well in all cases, without requiring either the setting or the knowledge of critical parameters, as it happens when using the best known preconditioned Krylov methods.

Keywords: Graph matrices; Multigrid; Conditioning and preconditioning (search for similar items in EconPapers)
Date: 2015
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0096300315010887
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:apmaco:v:270:y:2015:i:c:p:193-215

DOI: 10.1016/j.amc.2015.08.033

Access Statistics for this article

Applied Mathematics and Computation is currently edited by Theodore Simos

More articles in Applied Mathematics and Computation from Elsevier
Bibliographic data for series maintained by Catherine Liu ().