Communication Avoiding ILU0 Preconditioner

Laura Grigori 1 Sophie Moufawad 1
1 ALPINES - Algorithms and parallel tools for integrated numerical simulations
LJLL - Laboratoire Jacques-Louis Lions, Inria Paris-Rocquencourt, Institut National des Sciences Mathématiques et de leurs Interactions
Abstract : In this paper we present a communication avoiding ILU0 preconditioner for solving large linear systems of equations by using iterative Krylov subspace methods. Recent research has focused on communication avoiding Krylov subspace methods based on so called s-step methods. However there is no communication avoiding preconditioner yet, and this represents a serious limitation of these methods. Our preconditioner allows to perform s iterations of the iterative method with no communication, through ghosting some of the input data and performing redundant computation. It thus reduces data movement by a factor s between different levels of the memory hierarchy in a serial computation and between different processors in a parallel computation. To avoid communication, an alternating reordering algorithm is introduced for structured matrices, that requires the input matrix to be ordered by using nested dissection. We show that the reordering does not affect the convergence rate of the ILU0 preconditioned system as compared to nested dissection ordering, while it reduces data movement and should improve the expected time needed for convergence.
Type de document :
Rapport
[Research Report] RR-8266, INRIA. 2013, pp.21
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00803250
Contributeur : Laura Grigori <>
Soumis le : jeudi 21 mars 2013 - 14:42:58
Dernière modification le : vendredi 31 août 2018 - 09:06:03
Document(s) archivé(s) le : dimanche 2 avril 2017 - 18:26:13

Fichier

RR-8266.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00803250, version 1

Collections

Citation

Laura Grigori, Sophie Moufawad. Communication Avoiding ILU0 Preconditioner. [Research Report] RR-8266, INRIA. 2013, pp.21. 〈hal-00803250〉

Partager

Métriques

Consultations de la notice

942

Téléchargements de fichiers

1894