Direction de recherche : Stef GRAILLAT
Co-encadrement : BERTHOMIEU Jérémy, MARY Théo

Algorithme multimots flottant et efficace pour la multiplication de matrices sur corps finis

Cette soutenance de thèse décrit un nouvel algorithme multimots flottant pour le produit matriciel exact sur un corps fini premier dont les éléments tiennent sur un mot machine. Elle part de la résolution de systèmes polynomiaux : SpFGLM fait porter l'essentiel du temps sur une suite de Krylov par blocs, longue séquence de produits où une matrice reste invariante, comme dans l'algorithme de Wiedemann par blocs. Sur GPU, les BLAS offrent un produit flottant proche du pic ; l'enjeu est d'en conserver les performances avec un résultat exact modulo p.

FFLAS-FFPACK combine déjà flottants et BLAS, mais se limite aux premiers de 26 bits, moitié de la mantisse double : environ 20 bits utiles sur 53. Au-delà, FFLAS-FFPACK et FLINT recourent au système de nombres résidus (RNS, théorème des restes chinois), via plusieurs produits modulo des premiers plus petits.

La thèse propose une voie plus efficace entre 26 et environ 45 bits : étendre l'algorithme de produit matriciel sur corps finis premiers d'une taille allant d'un demi-mot à un mot entier, par arithmétique multimots flottante. Chaque coefficient est décomposé dans une base arithmétique ; les chiffres sont stockés dans des matrices distinctes, ce qui permet d'appeler les BLAS et de paralléliser au niveau matriciel. On concatène ces mots pour améliorer la localité mémoire, enjeu crucial des matrices fines de Wiedemann par blocs. On réutilise la décomposition de la matrice invariante, et on optimise l'espace alloué au résultat.

Une comparaison théorique du nombre de sous-produits, et expérimentale des performances, confronte cette approche au système de résidus de nombres. Deux implémentations, CPU et GPU, sont disponibles à https://gitlab.lip6.fr/lesnoff/phdcode.

Soutenance : 07/09/2026

Membres du jury :

Pascal Giorgi, Professeur à l' Université de Montpellier, LIRMM, [Rapporteur]
Nicolas Brisebarre & Directeur de Recherche & CNRS, LIP, ENS Lyon, [Rapporteur]
Stef Graillat, Professeur à Sorbonne Université, LIP6
Jérémy Berthomieu, Maître de Conférences à Sorbonne Université, LIP6
Théo Mary, Chargé de Recherche au CNRS, LIP6, et Sorbonne Université
Mioara Joldes, Directrice de Recherche & CNRS, LAAS
Clément Pernet, Professeur & Grenoble INP, Université Grenobles Alpes, LJK

Publications 2023-2026

• 2026
  • D. Lesnoff : “Algorithme multimots flottant et efficace pour la multiplication de matrices sur corps finis”, thèse, soutenance 07/09/2026, direction de recherche Graillat, Stef, co-encadrement : Berthomieu, Jérémy, Mary, Théo (2026)
  • J. Berthomieu, S. Graillat, D. Lesnoff, Th. Mary : “Multiword matrix multiplication over large finite fields in floating-point arithmetic”, (2026)
• 2023
  • J. Berthomieu, S. Graillat, D. Lesnoff, Th. Mary : “Modular matrix multiplication on GPU for polynomial system solving”, ACM Communications in Computer Algebra, vol. 57 (2), pp. 35-38, (Association for Computing Machinery (ACM)) (2023)