Stephane Pralet, PhD defense : September 21, 2004

Ordonnancement sous contraintes et sequencement en algebre lineaire creuse parallele.

Constrained orderings and scheduling for parallel sparse linear algebra.



Stephane PRALET
Tuesday September 21, 10h00 at CERFACS


 

Jury

  • IE. Ng (Rapporteur)
  • A. Pothen (Rapporteur)
  • P. Amestoy (Examinateur)
  • I.S. Duff (Examinateur)
  • I.S. Duff (Examinateur)
  • J.Y. L'Excellent (Examinateur)
  • J. Roman (Examinateur)

Résumé

Nous nous interessons a la resolution de systemes lineaires creux de grande taille par des solveurs directs creux operant en 3 phases qui sont l'analyse, la factorisation et la resolution. L'analyse est le lieu de pretraitements et doit dans la mesure du possible assurer a la fois des facteurs aussi creux que possible et une factorisation numeriquement stable. La factorisation doit exploiter l'independance des calculs pour etre efficace dans un environnement parallele distribue. Cette etude contribue a l'amelioration de ces comportements sur des classes de problemes connues comme etant difficiles ou mal apprehendees par des strategies classiques.

Dans une premiere partie, nous developpons des techniques de pretraitements numeriques et structurels pour les matrices symetriques indefinies. Nous etudions aussi de maniere plus prospective des approches de factorisation $LDL^T$ avec pivotage statique et l'elaboration d'ordonnancements pour les systemes augmentes.
Dans une deuxieme partie, nous presentons des techniques d'ordonnancements pour les matrices tres non symetriques visant a la fois a reduire le remplissage et a stabiliser la factorisation. Ces ordonnancements reposent sur des metriques hybrides prenant en compte des informations structurelles et numeriques.
Dans une troisieme partie, nous discutons des strategies de sequencement des taches dans un solveur multifrontal parallele, MUMPS.

Dans un premier temps, nous essayons de prendre en compte l'heterogeneite des milieux. Dans un second temps, nous melangeons des criteres de charge de travail et de memoire pour une prise de decision dynamique optimale.


Abstract

We consider the three different phases (analysis, factorization, solution) for the direct solution of large sparse systems of linear equations. During the analysis phase, preprocessing is applied in order to, on the one hand, permute the matrix to decrease the number of nonzeros in the factors and, on the other hand, to determine pivots that ensure as much as possible a stable factorization. During the factorization phase, the independence of the computations must be exploited to achieve a good performance on a distributed memory parallel computer. Our study contributes to the improvement of these aspects for some classes of matrices which are known for being difficult or for which default strategies clearly do not perform well.

In the first part of our thesis, we develop numerical and structural preprocessing strategies for symmetric indefinite matrices. We also study, in a more prospective way, static pivoting approaches for $LDL^T$ factorizations and orderings for augmented systems.
In the second part, we present orderings for highly unsymmetric matrices that aim at decreasing the fill-in and at stabilizing the factorization. These orderings are based on hybrid metrics which take into account both structural and numerical information.
In the last part, we discuss task scheduling strategies in a parallel multifrontal solver, MUMPS. We study two kinds of strategies.

Firstly, we investigate strategies that take into account heterogeneous architectures. Secondly, we study strategies that mix information about workload and memory to make optimal dynamic decisions.
CNESEADSEDFMeteo FranceONERASAFRANTotal
English | French | Intranet | FTP | Site Map | Legal Information | © CERFACS 2009 | Conception: CERFACS - Oréalys