THÈSE

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/93Ré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. Heureusement 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