Efficient and practical tree preconditioning for solving Laplacian systems

Abstract : We consider the problem of designing efficient iterative methods for solving linear systems. In its full generality, this is one of the oldest problems in numerical analysis with a tremendous number of practical applications. In this paper, we focus on a particular type of linear systems, associated with Laplacian matrices of undirected graphs, and study a class of iterative methods for which it is possible to speed up the convergence through the combinatorial preconditioning. In particular, we consider a class of preconditioners, known as tree preconditioners, introduced by Vaidya, that have been shown to lead to asymptotic speed-up in certain cases. Rather than trying to improve the structure of the trees used in preconditioning, we propose a very simple modification to the basic tree preconditioner, which can significantly improve the performance of the iterative linear solvers in practice. We show that our modification leads to better conditioning for some special graph structures, and provide extensive experimental evidence for the drastic decrease in the complexity of the preconditioned conjugate gradient method for several classes of graphs, including 3D meshes and complex networks.
Type de document :
Pré-publication, Document de travail
This work will appear as an extended abstract in the Proc. of the 14th International Symposium on.. 2015
Liste complète des métadonnées

Littérature citée [26 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01138603
Contributeur : Luca Castelli Aleardi <>
Soumis le : jeudi 2 avril 2015 - 12:03:59
Dernière modification le : jeudi 10 mai 2018 - 02:06:48
Document(s) archivé(s) le : mardi 18 avril 2017 - 09:00:30

Fichier

Draft.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01138603, version 1

Citation

Luca Castelli Aleardi, Alexandre Nolin, Maks Ovsjanikov. Efficient and practical tree preconditioning for solving Laplacian systems. This work will appear as an extended abstract in the Proc. of the 14th International Symposium on.. 2015. 〈hal-01138603〉

Partager

Métriques

Consultations de la notice

259

Téléchargements de fichiers

216