oN D’ORDRE 2623 THÈSE présenté en vue de l’obtention du titre de DOCTEUR DE L’INSTITUT NATIONAL POLYTECHNIQUE DE TOULOUSE Spécialité: Mathématiques, Informatique et Télécommunications par Azzam HAIDAR CERFACS Sur l’extensibilité parallèle de solveurs linéaires hybrides pour des problèmes tridimensionels de grandes tailles On the parallel scalability of hybrid linear solvers for large 3D problems Thèse présentée le 23 Juin 2008 à Toulouse devant le jury composé de: Fréderic Nataf Directeur de Recherche CNRS, Lab Jacques Louis Lions France Rapporteur Ray Tuminaro Chercheur senior, Sandia National Laboratories USA Rapporteur Iain Duff Directeur de Recherche RAL et CERFACS Royaume Uni Examinateur Luc Giraud Professeur, INPT ENSEEIHT France Directeur Stéphane Lanteri Directeur de Recherche INRIA France Examinateur Gérard Meurant Directeur de Recherche CEA France Examinateur Jean Roman Professeur, ENSEIRB INRIA France Examinateur Thèse préparée au Cerfacs, Report Ref:TH/PA/08/93Résumé La résolution de très grands systèmes linéaires creux est une composante de base algorithmique fondamentale dans de nombreuses applications scientifiques en calcul intensif. La résolution per formante de ces systèmes passe par la conception, le développement et l’utilisation d’algorithmes parallèles performants. Dans nos travaux, nous nous intéressons au développement et l’évaluation d’une méthode hybride (directe/itérative) basée sur des techniques de décomposition de domaine sans recouvrement. ...
oN D’ORDRE 2623
THÈSE
présenté en vue de l’obtention du titre de
DOCTEUR DE L’INSTITUT NATIONAL POLYTECHNIQUE DE TOULOUSE
Spécialité: Mathématiques, Informatique et Télécommunications
par
Azzam HAIDAR
CERFACS
Sur l’extensibilité parallèle de solveurs linéaires hybrides pour des
problèmes tridimensionels de grandes tailles
On the parallel scalability of hybrid linear solvers for large 3D problems
Thèse présentée le 23 Juin 2008 à Toulouse devant le jury composé de:
Fréderic Nataf Directeur de Recherche CNRS, Lab Jacques Louis Lions France Rapporteur
Ray Tuminaro Chercheur senior, Sandia National Laboratories USA Rapporteur
Iain Duff Directeur de Recherche RAL et CERFACS Royaume Uni Examinateur
Luc Giraud Professeur, INPT ENSEEIHT France Directeur
Stéphane Lanteri Directeur de Recherche INRIA France Examinateur
Gérard Meurant Directeur de Recherche CEA France Examinateur
Jean Roman Professeur, ENSEIRB INRIA France Examinateur
Thèse préparée au Cerfacs, Report Ref:TH/PA/08/93Résumé
La résolution de très grands systèmes linéaires creux est une composante de base algorithmique
fondamentale dans de nombreuses applications scientifiques en calcul intensif. La résolution per
formante de ces systèmes passe par la conception, le développement et l’utilisation d’algorithmes
parallèles performants. Dans nos travaux, nous nous intéressons au développement et l’évaluation
d’une méthode hybride (directe/itérative) basée sur des techniques de décomposition de domaine
sans recouvrement. La stratégie de développement est axée sur l’utilisation des machines mas
sivement parallèles à plusieurs milliers de processeurs. L’étude systématique de l’extensibilité et
l’efficacité parallèle de différents préconditionneurs algébriques est réalisée aussi bien d’un point
de vue informatique que numérique. Nous avons comparé leurs performances sur des systèmes de
plusieurs millions ou dizaines de millions d’inconnues pour des problèmes réels 3D.
Mots-clés: Décomposition de domaines, Méthodes itératives, Méthodes directes, Méthodes hy
brides, Complément de Schur, Systèmes linéaires denses et creux, Méthodes de Krylov, GMRES,
Flexible GMRES, CG, Calcul haute performace, Deux niveaux de parallèlisme, Calcul parallèle
distribué, Calcul sientifique, Simulation numériques de grande taille, Techniques de précondition
nement, Préconditionneur de type Schwarz additive.
Abstract
Large scalescientific applicationsandindustrial simulationsarenowadaysfully integratedin many
engineering areas. They involve the solution of large sparse linear systems. The use of large high
performance computers is mandatory to solve these problems. The main topic of this research
work was the study of a numerical technique that had attractive features for an efficient solution
of large scale linear systems on large massively parallel platforms. The goal is to develop a high
performance hybrid direct/iterative approach for solving large 3D problems. We focus specifically
onthe associateddomaindecompositiontechniquesforthe parallelsolutionoflargelinearsystems.
We have investigated several algebraic preconditioning techniques, discussed their numerical be
haviours, their parallel implementations and scalabilities. We have compared their performances
on a set of 3D grand challenge problems.
Keywords: Domaindecomposition, Iterativemethods, Direct methods, Hybrid methods, Schur
complements Linear systems, Krylov methods, GMRES, flexible GMRES, CG, High performance
computing, Two levels of parallelism, Distributed computing, Scientific computing, Large scale
numerical simulations, Preconditioning techniques, Additive Schwarz preconditioner.Remerciements
C’est une habitude saine que de rendre mérite, avec mon enthousiasme le plus vif et le plus
sincère à tous ceux qui à leur manière ont contribué mener ce travail à bien. Je désire alors ex
primer ma profonde gratitude :
Envers Luc GIRAUD, pour avoir accepté de me diriger patiemment, mais aussi spécialement
pour m’avoir accordé sa confiance en me laissant toute liberté dans mes initiatives, tout en étant
suffisamment attentif pour que je ne m’égare pas sur des pistes peu prometteuses. Mais également
pour sa disponibilité et sa générosité exceptionnelles, il s’est montré très disponible pour toutes
mes questions et problèmes à résoudre. Pour sa gentillesse, il a pris le temps de lire, relire et
corriger soigneusement cette thèse. J’ai pu profiter des ses compétences scientifiques, de ses con
seils pertinents et précieux. Par son charisme, son dynamisme et sa passion exceptionnelle pour la
recherche, il m’a beaucoup appris pour évoluer dans le monde de la recherche et de l’industrie.
Envers le directeur de l’équipe algorithme parallèle Iain DUFF, je tiens à lui exprimer ma très
vive reconnaissance. Monsieur j’ai eu l’honneur de travailler ces trois années au sein de votre
équipe. Cette expérience professionnelle me sera très bénéfique en ce qui concerne mes projets
d’avenir. Je tiens à vous remercier pour toutes vos remarques toujours pertinentes et vos idées
attentives.
A Serge GRATTON, et Xavier VASSEUR, je tiens à vous adresser mes sincères remerciements
pour vos encouragements généreux et vos suggestions judicieuses : ils m’ont été précieux. Vous
vous êtes montrés très disponibles pour toutes mes discussions vous m’avez aidé avec grande gen
tillesse ce qui m’a permis de m’ouvrir à d’autres horizons.
A l’assistancede plusieurs personnesde l’équipe MUMPS. Particulièrementje tiens à remercier
Jean Yves L’EXCELLENT et Patrick AMESTOY pour leur support et leurs aides très précieuses
de tous moments. Vous avez pris le temps de développer et de débuguer de nouvelles fonctionnal
ités qui m’ont été très bénéfiques.
Aux membresdu Jury qui m’ont honoré en acceptant d’évaluer mon travailet d’être présent ici
aujourd’hui. Chacund’eux mérite un remerciementparticulierpourm’avoiraccordéson attention.
UnsincèreremerciementàFrédericNATAFetRayTUMINAROquim’ontfaitl’honneurd’accepté
la charge d’être rapporteurs. Je leur suis reconnaissant pour le temps qu’ils ont consacré à la lec
ture de ce manuscrit et pour l’intérêt qu’ils ont montré pour mon travail. J’aimerais remercier
sincèrement Iain DUFF qui m’a fait l’honneur de présider mon jury, qui m’a beaucoup encouragé
etinspiré. AussibienégalementLucGIRAUDquim’amotivéetquim’aconsidérablementsoutenu
durant toutes mes recherches de thèse. Je désire aussi remercier vivement Stéphane LANTERI
pour ces conseils amicaux ainsi que ses discussions importantes et son accueil passionnant lors de
mon séjour dans son équipe à l’INRIA Sophia Antipolis. Je désire aussi remercier très vivement
Gérard MEURANT pour toutes ses remarques scientifiques, ses suggestions et ses conseils judi
cieux qu’il m’a souvent transmis grâce à son caractère chaleureux : ils m’ont été très précieux. Il
n’a jamais manqué une occasion pour m’encourager. Enfin je tiens à remercier profondément Jean
ROMAN pour avoir accepté de participer à ce jury, ainsi que pour ses conversationsenrichissantes
lors de mes visites à l’INRIA Bordeaux. Egalement je tiens à remercier toutes les personnes qui
ont assisté à cette soutenance de thèse.
C’est un grand privilège d’effectuer sa thèse au CERFACS, j’exprime ma très vive reconnais
sance à Jean Claude ANDRE le directeur du laboratoire. Monsieur, le CERFACS est un bon en
droitdeconvivialitéetj’aieul’honneurd’effectuermathèseauseindevotrelaboratoire. Heureusement que l’équipe CSG du CERFACS était là pour m’aider à me dépatouiller avec les expériences
etpourvenirmesauverlorsquej’étaisperduaufinfonddestracasinformatiques. Mercipourvotre
délicatesse et votre attention. Merci également au travail et à la gentillesse de l’administration,
Brigitte, Chantal, Dominique, Lydia, Michèle, et Nicole.
Egalement une pensée pour tous ceux avec qui j’ai partagé les moments qui font la vie d’un
étudiant, les discussions dans les couloirs. Un remerciement particulier aux membres de l’équipe
ALGO avec qui j’ai partagé de très beaux moments chaleureux, les déjeuners (départ à 12h30
tapante !), les pauses café/thé, les sudokus, les affaires de logiques du “le Monde”, les sorties, je
glisse un remerciement amical à cette joyeuse bande.
To the Samcef project, especially to Stéphane PRALET, who provided us with the structural
mechanics problems support, for the help he gave me among this work, and for kindly developing
special functionality allowing me to use the samcef code, for his advice and numerous suggestions.
To all the members of the Consortium Seiscope project with whom I had fruitful discussion
and who, provides me the seismic applications that enables me to progress in my work: Florent
SOURBIER, Jean VIRIEUX, Romain BROSSIER and StÂťephane OPERTO.
To the INRIA NACHOS team. I must thank Stéphane LANTERI who opened me the door of
an enriching collaboration, who interest in my work and who gave me constructive advice.
To Masha SOSONKINA and Layne WATSON whose deserve grateful thanks for providing me
with an huge amount of simulations hours on the Virginia Tech supercomputer, and for many
helpful discussions and advices.
Un grand grand Merci également a toutes celles et ceux qui ont participé directement ou indi
rectement à ce travail. Tous celles et ceux qui m’ont témoigné leur amitié, qui m’ont apporté leur
aide,quim’ontaccompagnépendantcetteaventureetquejenepeuxciterici,vousêtesnombreux...
Cette aventure de m’est pas propre, enfin, c’est quand même l’aboutissement de toute une
scolarité, je voudrais remercier chaleureusement ma petite maman à qui je dois beaucoup et qui a
toujours été une fervente supportrice avecmes deux sœurset mon frère. Kamil, un grand merci du
cœur a toi mon père, pour m’avoir donné l’envie d’être heureux et pour m’avoir toujours soutenu
dans mes choix. Et tout le reste de ma famille, Merci pour votre soutien, vos encouragements et
votre présence dans les moments difficiles. Je vous témoigne ici toute ma reconnaissance et tout
mon amour.Contents
I Solving large linear systems on large parallel platforms 3
1 Introducti