Description
Date depot: 5 avril 2024
Titre: Fast algorithms for solving systems of polynomial constraints over the reals
Directeur de thèse:
Jérémy BERTHOMIEU (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é: Les systèmes polynomiaux apparaissent dans un large éventail d'applications liées à la communication et à la sécurité informatiques, à la physique quantique, à la conception de mécanismes et à l'optimisation.
Ce projet vise à améliorer considérablement - de plusieurs ordres de grandeur - les algorithmes de résolution de systèmes d'équations et d'inégalités polynomiales sur les réels.
Ces algorithmes ont la capacité de calculer des points d'échantillonnage par composantes connexes dans l'ensemble des solutions réelles.
Le changement clé de paradigme qui permettra de telles améliorations consiste à s'appuyer sur des réductions efficaces des problèmes d'optimisation polynomiale avec une saveur géométrique, combinées à des algorithmes avancés de calcul formel.
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 and inequalities over the reals.
These algorithms have the ability to compute sample points per connected components in the set of real solutions.
The key change of paradigm that will enable such improvements is to rely on efficient reductions to polynomial optimization problems with a geometric flavour combined with advanced computer algebra algorithms.