Marc Baboulin, PhD defense : March 21, 2006

Résolution de problèmes de moindres carrés linéaires denses de grande taille sur des calculateurs parallèles distribués. Application au calcul de champ de gravité terrestre.

Solving large dense linear least squares problems on parallel distributed computers. Application to the Earth's gravity field computation.

Marc BABOULIN
Tuesday March 21, 10h30 at CERFACS

 

Jury

• Georges BALMINO : CNES-CNRS, France
• Jack DONGARRA : University of Tennessee, USA (Referee)
• Iain S. DUFF : RAL, UK and CERFACS, France
• Luc GIRAUD : ENSEEIHT, France (Advisor)
• Serge GRATTON : CERFACS, France (Co-advisor)
• Nicholas J. HIGHAM : University of Manchester, UK (Referee)
• Joseph NOAILLES : ENSEEIHT, France
  
  

Résumé

Cette thèse concerne le calcul scientifique haute performance et plus particulièrement le développement de logiciels parallèles efficaces permettant de traiter des problèmes de moindres carrés linéaires denses de très grande taille. Notre travail se situe dans le cadre de la mission GOCE (Gravity field and steady-state Ocean Circulation Explorer - Agence Spatiale Européenne) dont l’objectif est de fournir un modèle très précis du champ de gravité terrestre. Le lancement de ce satellite est prévu pour début 2007.

Après avoir présenté les stratégies numériques possibles pour prendre en compte les observations fournies par GOCE, nous décrivons le solveur parallèle distribué que nous avons développé pour le Centre National d’Etudes Spatiales. Les performances obtenues sont compétitives par rapport à celles des librairies parallèles standards sur les machines opérationnelles utilisées dans l’industrie spatiale tout en nécessitant un stockage mémoire deux fois moins important.

Afin d’améliorer la scalabilité et la portabilité de notre solveur, nous avons défini un format packed distribué qui repose sur des noyaux ScaLAPACK. Cette approche constitue une amélioration significative car il n’existe pas à ce jour de format packed dans les librairies parallèles standards pour les matrices symétriques et triangulaires. Nous présentons des exemples d’implantations pour la factorisation de Cholesky et la mise à jour d’une factorisation QR. Ce format peut être étendu à d’autres opérations d’algèbre linéaire.

L’objectif de précision sur la détermination du champ de gravité a conduit à l’élaboration de nouveaux outils d’analyse d’erreur dans le domaine de la sensibilité des moindres carrés linéaires résultant de problèmes d’estimation de paramètres. Nous proposons notamment une formule exacte, des bornes précises et des estimateurs statistiques pour évaluer le conditionnement de tout ou partie de la solution d’un problème de moindres carrés. Le choix entre ces formules dépendra de la taille du problème et du niveau de précision souhaité.

Abstract

In this thesis, we present our research in high performance scientific computing for linear least squares. More precisely we are concerned with developing efficient parallel software that can solve very large dense linear least squares problems and with providing numerical tools that can assess the quality of the solution. This thesis is also a contribution to the GOCE mission that strives for a very accurate model of the Earth's gravity field. This satellite is scheduled for launch in 2007 and in this respect, our work represents a step in the definition of algorithms for the project.

We present an overview of the numerical strategies that can be used for updating the solution with new observations coming from GOCE mesurements. Then we describe a parallel distributed solver that we implemented in order to be used in the CNES software package for orbit determination and gravity field computation. This solver compares well in terms of performance with the standard parallel libraries ScaLAPACK and PLAPACK on the operational platforms used in the space industry while saving about half the memory, thanks to taking into account the symmetry of the problem.

In order to improve the scalability and the portability of our solver, we define a packed distributed format that is based on ScaLAPACK kernel routines. This approach is a significant improvement since there is no packed distributed format available for symmetric or triangular matrices in the existing dense parallel libraries. Examples are given for the Cholesky factorization and for the updating of a QR factorization. This format can easily be extended to other linear algebra calculations.

This thesis also contains new results in the area of sensitivity analysis for linear least squares resulting from parameter estimation problems. Specifically we provide a closed formula, bounds of correct order of magnitude and also statistical estimates that enable us to evaluate the condition number of linear functionals of least squares solution. The choice between the different expressions will depend on the problem size and on the desired level of accuracy.