Clément Pernet - Calcul exact fiable et haute performance

08:30
Friday
21
Nov
2014
  • Habilitation
Place: 
Organized by: 
Clément Pernet
Speaker: 
Clément Pernet
Teams: 

Lieu de soutenance : grand amphithéâtre du centre Inria Grenoble-Alpes, 655 avenue de l'Europe 38330 Montbonnot

Jury :

  • Daniel Augot (DR LIX - Inria Saclay - Ile de France), rapporteur
  • Jean-Guillaume Dumas (PR LJK - Université J. Fourier Grenoble 1), examinateur
  • Jean-Charles Faugère (DR LIP6 - Inria Paris - Rocquencourt), examinateur
  • Mark Giesbrecht (PR - University of Waterloo, Canada), rapporteur
  • Laura Grigori (DR LJLL - Inria Paris - Rocquencourt), rapporteure
  • Erich Kaltofen (PR - North Carolina State University, USA), examinateur
  • Brigitte Plateau (PR LIG - Grenoble INP), examinatrice
 
 

Les contributions présentées concernent le calcul exact haute performance, à l'interface entre calcul formel, théorie des codes et calcul parallèle.

L'algèbre linéaire exacte, sur des corps finis ou le corps des nombres rationnels est au coeur de nombreuses applications recourant au calcul algébrique intensif: de la cryptanalyse basée sur les cribles algébriques ou sur la résolution de systèmes polynomiaux au test de conjectures en théorie algorithmique des nombres, ou encore au décodage en liste... Le développement aussi bien de l'algorithmique que des implantations efficaces en algèbre linéaire exacte a atteint ces dernières années un grand niveau de maturité. Nous évoquons les grandes lignes de ces avancées, illustrées par nos contributions, en dégageant quelques principes généraux qui les sous-tendent, comme celui de rendre les réductions algorithmiques effectives. Le produit de matrices, combinant conversions entres arithmétiques modulaires, entières et flottantes, usage des BLAS numériques et d'algorithmes sous-cubiques à faible empreinte mémoire, sert de brique de base. L'élimination de Gauss en tire parti par ses multiples réductions récursives. La déficience de rang et le calcul des profils de rang est une spécificité du calcul algébrique que nous explorons en détails. Enfin, le calcul du polynôme caractéristique et de la forme de Frobenius illustre le cas d'une amélioriation de complexité asymptotique se révélant aussi avantageuse en pratique. Nous proposons une parallélisation des ces algorithmes par tâches récursives permettant de préserver les performances asymptotiques. Des implantations efficaces du vol travail de tâches récursives et basées sur des dépendances par flot de données, permettent d'atteindre des performances similaires aux meilleures bibliothèques numériques, et passant à l'échelle.
 
Dans le contexte du calcul distribué à grande échelle, la fiabilité des ressources distantes est mise en question. Pour remédier aux erreurs, d'origine soit physique soit malicieuse, nous proposons des schémas de tolérance aux fautes algorithmiques (ABFT) reposant sur les techniques d'évaluation-interpolation communes en calcul formel. Les codes correcteurs classiques (Reed-Solomon et codes CRT) basés sur l'interpolation sont étudiés et généralisés au cas des fractions rationnelles et leur entrelacement. Nous introduisons par ailleurs les codes d'interpolation creuse dont l'étude des capacité des correction peine à révéler leur efficacité en  pratique. Ces travaux ouvrent en outre des perspectives sur des techniques de décodage symbolique-numérique, supportant conjointement les erreurs et le bruit numérique.