- Laboratoire d’informatique

PRÉBET Rémi

Doctorant à Sorbonne Université
Équipe : PolSys
https://rprebet.github.io/
https://rprebet.github.io/

Direction de recherche : Mohab SAFEY EL DIN

Connexité dans les ensembles algébriques réels: algorithmes et applications

Cette thèse de doctorat porte sur la conception et l’analyse d’algorithmes, relevant du calcul formel, pour la résolution de systèmes polynomiaux. Plus précisément, nous considérons le problème du comptage du nombre de composantes connexes de l’ensemble des solutions réelles de systèmes d’équations polynomiales à variables réelles, ainsi que le problème de décider si deux solutions réelles d’un tel système vivent dans une même composante connexe de son ensemble de solutions réelles. Ces problèmes sont centraux en géométrie algébrique réelle et trouvent des applications en robotique.

Le cadre méthodologique choisi est celui du calcul de cartes routières, introduit par Canny en 1988 : il s’agit de calculer une courbe contenue dans l’ensemble des solutions dont l’intersection avec chacune de ses composantes connexes est connexe. Nous décrivons un algorithme calculant de telles cartes routières qui, sous des hypothèses de régularité satisfaites génériquement, a une complexité sous-quadratique en la taille de la sortie, cette dernière étant asymptotiquement quasi optimale. Ceci étend aux cas non compacts les meilleures complexités connues pour ce problème. Nous montrons aussi que le coût du calcul de nombre de composantes connexes d’une courbe algébrique réelle (vivant dans un espace de dimension arbitraire) est similaire au coût du calcul de la topologie de sa projection sur un plan générique. Enfin, nous montrons comment ces avancées, combinées aux algorithmes de la géométrie algébrique réelle permettent de concevoir un algorithme testant la cuspidalité de mécanismes articulés.


Soutenance : 20/12/2023

Membres du jury :

Laurent Busé, Directeur de recherche, INRIA Sophia, France [Rapporteur]
Alicia Dickenstein, Professeure, Universidad de Buenos Aires [Rapporteur]
Peter Bürgisser, Professeur, Technical University of Berlin
Fatemeh Mohammadi, Professeure, KU Leuven
Jean Ponce, Professeur des Universités, École Normale Supérieure-PSL & New York University
Bernd Sturmfels, Professeur, University of California à Berkeley & Directeur du MPI Leipzig
Émmanuel Trélat, Professeur des Universités, Sorbonne Université
Éric Schost, Professeur, University of Waterloo (Invité)
Mohab Safey El Din, Professeur des Universités, Sorbonne Université

Date de départ : 31/12/2023

Publications 2022-2024