Conception d’un solveur linéaire creux parallèle hybride direct-itératif

Jérémie Gaidamour

Description

Sous la direction de Jean Roman, Pascal Henon
Thèse soutenue le 08 décembre 2009: Bordeaux 1
Cette thèse présente une méthode de résolution parallèle de systèmes linéaires creux qui combine efficacement les techniques de résolutions directes et itératives en utilisant une approche de type complément de Schur. Nous construisons une décomposition de domaine. L'intérieur des sous-domaines est éliminé de manière directe pour se ramener à un problème sur l'interface. Ce problème est résolu grâce à une méthode itérative préconditionnée par une factorisation incomplète. Un réordonnancement de l'interface permet la construction d'un préconditionneur global du complément de Schur. Des algorithmes minimisant le pic mémoire de la construction du préconditionneur sont proposés. Nous exploitons un schéma d'équilibrage de charge utilisant une répartition de multiples sous-domaines sur les processeurs. Les méthodes sont implémentées dans le solveur HIPS et des résultats expérimentaux parallèles sont présentés sur de grands cas tests industriels.
-Calcul haute performance
-Parallélisme
-Algèbre linéaire creuse
-Solveur parallèle de systèmes linéaires creux
-Méthode hybride directe-itérative
-Factorisation incomplète
-Complément de Schur
-Décomposition de domaine
This thesis presents a parallel resolution method for sparse linear systems which combines effectively techniques of direct and iterative solvers using a Schur complement approach. A domain decomposition is built ; the interiors of the subdomains are eliminated by a direct method in order to use an iterative method only on the interface unknowns. The system on the interface (Schur complement) is solved thanks to an iterative method preconditioned by a global incomplete factorization. A special ordering on the Schur complement allows to build a scalable preconditioner. Algorithms minimizing the memory peak that appears during the construction of the preconditioner are presented. The memory is balanced thanks to a multiple domains per processors parallelization scheme. The methods are implemented in the HIPS solver and parallel experimental results are presented on large industrial test cases.
-High-performance computing
-Parallelism
-Sparse linear algebra
-Parallel solver for sparse linear systems
-Direct-iterative hybrid method
-Incomplete factorization
-Schur complement
-Domain decomposition
Source: http://www.theses.fr/2009BOR13904/document

Sujets

• Superordinateur
• Parallélisme
• Complément de Schur

Informations

• Publié par: Thesee
• Nombre de lectures: 57
• Langue: Français
• Poids de l'ouvrage: 3 Mo

Extrait

oN d’ordre : 3904
THÈSE
PRÉSENTÉE À
L’UNIVERSITÉ DE BORDEAUX I
ÉCOLE DOCTORALE DE MATHÉMATIQUES ET
D’INFORMATIQUE
Par Jérémie Gaidamour
POUR OBTENIR LE GRADE DE
DOCTEUR
SPÉCIALITÉ : INFORMATIQUE
Conception d’un solveur linéaire creux parallèle
hybride direct-itératif
Soutenue le : 8 décembre 2009
Après avis des rapporteurs :
Serge Gratton ..... Professeur, ENSEEIHT
Yousef Saad ........ Université du Minnesota
Devant la commission d’examen composée de :
Oliver Coulaud ..... Directeur de recherche, INRIA .... Président du Jury
Luc Giraud ......... de recherche, .... Examinateur
Serge Gratton ..... Professeur, ENSEEIHT ........... Rapporteur
Pascal Hénon ....... Chargé de recherche, INRIA ....... Directeur de Thèse
Jean-Jacques Pesqué Chercheur, CEA .................. Examinateur
Jean Roman ........ Professeur, ENSEIRB ............. Directeur de Thèse
2009Remerciements
Cher lecteur, c’est par cette page que j’achève la rédaction de mon manuscrit. Je suis pro-
fondément heureux d’écrire enfin ces remerciements et de pouvoir ainsi exprimer ma sincère
reconnaissance à tous ceux qui m’ont accompagné pendant ces trois dernières années pour me-
ner à bien ce travail.
Je voudrais commencer par remercier Serge Gratton pour avoir accepté de rapporter sur
mon travail et pour les remarques qu’il a formulées sur mon manuscrit. Je remercie aussi parti-
culièrement Yousef Saad pour avoir suivi avec intérêt mon travail tout au long de ma thèse et
pour m’avoir accueilli plusieurs mois à l’université du Minnesota. Ces échanges ont considéra-
blement contribué à ouvrir des perspectives sur mes travaux de recherche et je suis honoré qu’il
ait accepté d’être mon second rapporteur.
Je remercie également tous les membres de mon jury de thèse. En premier lieu, je remercie
Oliver Coulaud, pour avoir accepté d’être mon directeur de jury; Luc Giraud pour l’intérêt qu’il
a porté à mes travaux et Jean-Jacques Pesqué à travers qui je remercie également l’ensemble
des personnes du CEA/CESTA avec lesquelles j’ai eu l’occasion de travailler. Je remercie aussi
tout naturellement Jean Roman, mon directeur de thèse, notamment pour m’avoir encouragé à
prolonger mes études par une thèse, avoir facilité et guidé mes premiers pas dans le monde de
la recherche.
Je ne sais comment exprimer toute ma gratitude envers Pascal Hénon qui m’a encadré tout
au long de cette thèse. J’ai initialement travaillé sous sa direction en projet à l’ENSEIRB puis
en Master Recherche et je fus très heureux qu’il accepte de continuer à m’encadrer pour ma
thèse. Tout au long de ce parcours, sa disponibilité a été sans faille. Il a su m’expliquer, me
ré-expliquer et m’expliquer encore avec patience tout ce qui a pu longtemps m’échapper. Son
encadrement a permis un déroulement idéal de ma thèse. Il a su à la fois maintenir le cap
et me laisser une totale liberté de manœuvre dans la réalisation des objectifs. Je ne sais pas si
c’est normal, mais il a rendu ces trois années de travail plus qu’agréable. Merci pour tout Pascal.
Impossible de ne pas remercier ici l’ensemble des membres des équipes ScAlApplix, Bacchus
et HiePACS. Je remercie tout d’abord l’ancienne génération, c’est-à-dire les MdC et les thésards
« super-sérieux » pour avoir aussi bien accueilli les petits nouveaux. Grâce à vous, j’ai beau-
coup appris sur les techniques d’organisation «juste-à-temps» ou «zéro-délai». J’ai une pensée
particulière pour ceux de ma génération et spécialement pour les ENSEIRBiens qui ont suivi
la même voie que moi. Les moulte déménagements m’ont permis de connaître rapidement et
d’apprécier toute la nouvelle génération de thésards. Je les félicite pour avoir plutôt bien toléré
ma méchanceté. Cela va me manquer de ne plus pouvoir vous embêter;-).
iiiiv Remerciements
Sur un ton plus léger, je remercie tout ceux qui ont participé à des missions mémorables,
notamment en Suisse, au Brésil et en Chine (trop dure la vie de thésard). Merci à ceux qui ont
accepté d’être photographié ou filmé pour la postérité, pas toujours en possession de tous leurs
moyens... D’un point de vue culinaire, je remercie les organisateurs de l’épiphanie journalière,
des barbecues mais aussi le restaurant du CNRS et les « BDI » qui m’y ont accompagné. Je me
dois de remercier ici l’incendie des locaux de l’INRIA qui m’a évité d’avoir à trier mes documents
à la fin de ma thèse...
Au-delà des relations de travail et des amis, il y a toute ma famille dont l’influence a été
déterminante dans la réalisation de ce projet. Je souhaite donc remercier mes parents pour le
soutien qu’ils m’ont apporté pendant toutes ces années d’études. Je vous suis très reconnaissant
de m’avoir toujours encouragé dans la voie que j’avais choisie et de m’avoir toujours offert les
meilleures conditions d’études. Merci aussi d’avoir réalisé un rêve d’enfant en me permettant de
devenir pilote pendant mes années de thèse.
Ces remerciements ne pourraient être complets sans un grand merci à Laure qui m’a accom-
pagné pendant toutes ces années. Merci pour le bonheur que tu m’offres chaque jour.Résumé
Cette thèse présente une méthode de résolution parallèle de systèmes linéaires creux qui
combine efficacement les techniques de résolutions directes et itératives en utilisant une approche
de type complément de Schur. Nous construisons une décomposition de domaine. L’intérieur des
sous-domaines est éliminé de manière directe pour se ramener à un problème sur l’interface.
Ce problème est résolu grâce à une méthode itérative préconditionnée par une factorisation
incomplète. Un réordonnancement de l’interface permet la construction d’un préconditionneur
global du complément de Schur. Des algorithmes minimisant le pic mémoire de la construction
du préconditionneur sont proposés. Nous exploitons un schéma d’équilibrage de charge utilisant
une répartition de multiples sous-domaines sur les processeurs. Les méthodes sont implémentées
dans le solveur Hips et des résultats expérimentaux parallèles sont présentés sur de grands cas
tests industriels.
Mots-clés: calcul haute performance, parallélisme, algèbre linéaire creuse, solveur parallèle de
systèmes linéaires creux, méthode hybride directe-itérative, factorisation incomplète, complé-
ment de Schur, décomposition de domaine.
Abstract
This thesis presents a parallel resolution method for sparse linear systems which com-
bines effectively techniques of direct and iterative solvers using a Schur complement approach.
A domain decomposition is built; the interiors of the subdomains are eliminated by a direct
method in order to use an iterative method only on the interface unknowns. The system on the
interface (Schur complement) is solved thanks to an iterative method preconditioned by a global
incomplete factorization. A special ordering on the Schur complement allows to build a scalable
preconditioner. Algorithms minimizing the memory peak that appears during the construction
of the preconditioner are presented. The is balanced thanks to a multiple domains per
processors parallelization scheme. The methods are implemented in the Hips solver and parallel
experimental results are presented on large industrial test cases.
Keywords: high-performance computing, parallelism, sparse linear algebra, parallel solver for
sparse linear systems, direct-iterative hybrid method, incomplete factorization, Schur comple-
ment, domain decomposition.Table des matières
Introduction générale 1
1 État de l’art 3
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2 Méthodes de résolution directe . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2.1 Renumérotation des inconnues . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2.2 Factorisation symbolique . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.2.3 F numérique . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.3 Méthodes de résolution itérative . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.3.1 Méthode par projection dans un espace de Krylov . . . . . . . . . . . . . 16
1.3.2 Technique de préconditionnement . . . . . . . . . . . . . . . . . . . . . . . 17
1.4 Préconditionnement par factorisation incomplète . . . . . . . . . . . . . . . . . . 19
1.4.1 Factorisations ILU(k)