Description
Date depot: 11 avril 2023
Titre: Towards a new generation of Gröbner bases algorithms for polynomial system solving
Directeur de thèse:
Mohab SAFEY EL DIN (LIP6)
Domaine scientifique: Sciences et technologies de l'information et de la communication
Thématique CNRS : Calcul arithmétique et formel, codage et cryptologie
Resumé: La résolution de systèmes polynomiaux trouve de nombreuses applications, notamment en sécurité de l'information (cryptographie), la physique quantique ou encore la robotique. Ce projet doctoral vise à concevoir et implanter des algorithmes permettant de résoudre ces systèmes et qui soient significativement plus rapides que l'état de l'art. Ces algorithmes réécrivent les systèmes donnés en entrée en un système équivalent, qu'on appelle base de Gröbner, et à partir duquel on peut extraire les solutions. Le changement de paradigme clé qui permettra d'obtenir de telles améliorations consiste à réduire le calcul de bases de Gröbner à des calculs d'algèbre linéaire sur des matrices à entrées polynomiales. L'idée est de tirer profit des techniques de pointe apportées par le calcul formel pour la manipulation de telles matrices.
Résumé dans une autre langue: Polynomial systems arise in a wide range of topical applications related to computer communication
and security, quantum physics, mechanism design and optimization.
This project aims at the significant improvement – by several orders of magnitude – of algorithms
for solving polynomial systems of equations. These algorithms rewrite the input set of equations into
an equivalent one, named Gröbner basis, from which it is easier to extract the solutions.
The key change of paradigm that will enable such improvements is to perform reductions of Gröbner
bases computations to linear algebra operations over matrices with univariate polynomials as entries,
and then benefit from advanced computer algebra algorithms for these operations.
Doctorant.e: Kouba Robin