Etude d'un nouvel algorithme de résolution de systèmes d'équations linéaires modulo p
Équipe
Responsables
Objectifs du stage
- Programmer un algorithme nouveau
- Mesurer son efficacité
- Comparer avec l'état de l'art
- Concevoir une version parallèle (MPI ou GPU)
- Inclure le code dans des librairies open-source
- Réutiliser les idées-clef de l'algorithme dans d'autres contextes
Mots-clefs
calcul scientifique haute performance, parallélisation, algorithmique, algèbre linéaire
Contexte Scientifique
Les systèmes d'équations linéaires comptent parmi les plus simples à
résoudre --- on l'aborde dès la classe de seconde au lycée. D'un point
de vue scientifique, c'est une technique cruciale car leurs
application sont innombrables. Dans le domaine de la simulation
numérique, de nombreux problèmes d'ingénierie nécessitent de résoudre
de grands systèmes linéaires. Dans ce cas-là, les calculs sont
effectués avec des nombres flottants, c'est-à-dire avec une précision
limitée. Ce besoin scientifique a conduit à l'existence de librairies
de calcul open-source, librement utilisables par tous :
ATLAS, GotoBLAS, LAPACK, UMFPACK,
MUMPS, LinPack, la GNU Scientific Library,
GPLU, SuperLU, SciPy, etc. Ces librairies
sont largement utilisées, en général à travers des logiciels payants
tels que MatLab, Mathematica, et Maple, ou
via des logiciels gratuits tels que SAGE, SciLab et
Octave. Les problèmes de performances sont cruciaux, car on
veut sans arrêt pouvoir résoudre des systèmes plus gros.
Résoudre des systèmes d'équations linéaires de manière exacte
est plus compliqué. Cependant, cela possède également de nombreuses
applications, par exemple dans les domaines de la cryptographie ou de
la protection de données. Dans ce monde-là, les coefficients des
systèmes doivent appartenir à un domaine où il est possible
d'effectuer des calculs exacts, comme par exemple, les nombres
entiers, les nombres rationnels, les entiers modulo p, etc. L'offre
logicielle est bien moins importante, et plus "confidentielle". On
trouve les librairies FFLAS-FFPACK, LinBox,
LELA, M4RI(E), NTL, PARI et FLINT.
Là aussi, les problèmes de performances sont cruciaux. Pour ne donner
qu'un seul exemple, factoriser de grands entiers, c'est-à-dire les
décomposer en produit de facteurs premiers, nécessite de résoudre de
manière exacte d'énormes systèmes d'équations linéaires modulo 2
(c'est-à-dire que les coefficients sont soit zéro, soit un). En 2009,
le nombre RSA-768, de 232 chiffres, a pu être factorisé [5]. Ceci a
nécessité la résolution d'un système d'environ 200 millions
d'équations en autant de variables, dont le stockage nécessite plus de
100Go. En réussissant à factoriser un nombre de taille comparable, on
pourrait fabriquer de faux badges "VIGIK" (ceux avec lesquels les
facteurs ouvrent les hall d'immeubles). Un seul code open-source
permet à ce jour de réaliser des calculs de cette taille :
CADO-NFS.
On aurait donc pu croire que le problème de la résolution des systèmes d'équations linéaires aurait été étudié jusqu'à l'os. Que tous les algorithmes possibles et imaginables seraient déjà connus, déjà programmés, et déjà disponibles dans des librairies ou des programmes achevés.
Et pourtant, l'été dernier (2012), un chercheur américain, Prasad Raghavendra, a publié un algorithme nouveau, d'une simplicité désarmante, pour résoudre des systèmes modulo p [1]. Sous sa forme actuelle, l'algorithme de Raghavendra ne semble pas pouvoir améliorer les méthodes classiques [2] dans le cas le plus général, car il a sensiblement la même complexité asymptotique que le pivot de Gauss. Cependant il possède l'intéressante propriété de pouvoir tirer parti automatiquement du caractère ``creux'' des systèmes à résoudre, c'est-à-dire le fait que les équations ne contiennent qu'une petite fraction de l'ensemble des termes qu'elles pourraient contenir (les systèmes issus de la factorisation sont très creux). Dans ce cas, l'algorithme dégénère vers quelque chose qui a sensiblement la même complexité asymptotique que les meilleures méthodes ``creuses'' connues [3], mais il semble qu'il consomme plus de mémoire.
Description du travail à effectuer
L'objectif du stage consiste à tourner autour de l'algorithme de Raghavendra de plusieurs manières. Il s'agira d'abord de le programmer. Ce premier travail permettra de comparer l'efficacité pratique de l'algorithme avec les méthodes classiques pour les systèmes denses (le pivot de Gauss) et les systèmes creux (les méthodes itératives). Dans un deuxième temps, on pourra étudier l'algorithme lui-même un peu plus en détail. Deux pistes parraissent possible :
- On pourrait envisager une version parallèle de l'algorithme. Cela ne semble pas complètement évident car il se présente de manière intrinsèquement séquentielle.
- On pourrait essayer d'isoler l'idée-clef de l'algorithme, et tenter de l'appliquer plus généralement, en bâtissant dessus toute une librairie d'algèbre linéaire. Certains algorithmes seront assez faciles (somme de sous-espaces), d'autres moins (intersection ou quotient de sous-espaces), et certains nécessiteront probablement un effort de recherche (dimension d'un sous-espace).
- On pourrait enfin tenter d'adapter l'algorithmes aux problèmes Learning Parity With Noise et Learning With Errors, deux problèmes NP-complets utilisés en cryptographie, qui consistent à résoudre des équations linéaires modulo p alors que les membres de droite ont subit une "perturbation".
Ce stage peut s'orienter dans plusieurs direction selon le profil de
l'étudiant(e). Si il/elle se sent une vocation pour la programmation
et réalise une implémentation de bonne qualité, on peut envisager de
contribuer à des logiciels libres de calcul formel comme
SAGE [4], auquel l'équipe a déjà contribué. Si le/la stagiaire se sent attiré(e) par la recherche
d'améliorations algorithmiques, alors il est possible de s'engager
dans une voie plus théorique. Les différents aspects de la question ne
sont nullement incompatibles. Par exemple, paralléliser l'algorithme
de Raghavendra pose des questions à la fois théoriques et pratiques.
Ce stage est enfin l'occasion de s'initier en douceur à la problématique du calcul formel, et de se frotter à l'actualité de la recherche en informatique fondamentale.
Ce stage est remunéré par l'équipe Calcul Formel.
Poursuite
Ce stage peut éventuellement se poursuivre par une thèse au sein de l'équipe calcul formel.
Références
[1] Prasad Raghavendra. A randomized algorithm for linear equations over prime fields. unpub- lished note, August 2012. http://www.eecs.berkeley.edu/~prasad/linsystems.pdf.
[2] Nov. 2008:Jean-Guillaume Dumas, Pascal Giorgi and Clément Pernet. Dense Linear Algebra over Finite Fields. ACM Transactions on Mathematical Software. Volume 35, n° 3, 34 pp. article
[3] Douglas H. Wiedemann. Solving sparse linear equations over finite fields. IEEE Transactions on Information Theory, 32(1):54–62, 1986.