Équipe : PolSys - Systemes Polynomiaux

Axes : SSR (👥👥), TMC (👥👥).

Responsable :

Mohab Safey El Din Campus Pierre et Marie Curie 26-00/317

Les travaux de l'équipe PolSys se concentrent sur la conception d'algorithmes relevant du calcul formel (méthodes algébriques) pour la résolution de systèmes polynomiaux, ainsi que sur l'implantation et les applications de ces algorithmes.
Le problème fondamental de la résolution des systèmes polynomiaux apparaît dans un grand nombre de domaines comme la cryptologie, la géométrie algorithmique ou la vérification de programmes dans les sciences du numérique, des conjectures de nature géométrique ou combinatoire en mathématiques ou bien dans des sciences de l'ingénieur comme la robotique, la biologie et la chimie.
La nature non-linéaire de ces problèmes, le caractère exact ou exhaustif ou global des solutions calculées requis par certaines applications, rendent l'usage de méthodes purement numériques ou d'approximation délicat. Les défis algorithmiques posés par la résolution de systèmes polynomiaux sont donc considérables et ce d'autant que ce problème est NP-dur. En s'appuyant sur des méthodes de calcul formel, notamment le calcul de bases de Gröbner, l'équipe PolSys conçoit des algorithmes qui permettent

• la résolution de systèmes polynomiaux à coefficients dans un corps fini (pour des applications en cryptologie ou théorie des codes correcteurs) ou à coefficients rationnels exacts (pour des applications dans les sciences de l'ingénieur)
• la résolution de systèmes sur les nombres réels même lorsque le nombre de solutions complexes est infini, ou dépendant de paramètres (pour des applications de nature géométrique ou provenant de la robotique)
• la résolution de problèmes d'élimination des quantificateurs sur les nombres réels ou complexes, et notamment les problèmes d'optimisation polynomiale (pour des applications en vérification de programmes ou dans des sciences de l'ingénieur)
• la détermination de propriétés topologiques aux ensembles de solutions réelles (notamment la détermination du nombre de composantes connexes)

Pour résoudre cette large gamme de problèmes, l'équipe PolSys développe plusieurs logiciels dédiés dont notamment la bibliothèque msolve qui est utilisée par des systèmes de calcul formel largement diffusés comme SageMath et OSCAR (voir aussi d'autres logiciels développés par l'équipe).
Enfin, l'équipe développe une activité régulière dans plusieurs domaines d'applications, notamment la cryptologie et la robotique.