Singularités et complexité dans les algorithmes de géométrie réelle

Nous aborderons le problème fondamental de la détermination d'au moins un point par composante connexe de l'ensemble des solutions réelles d'un système d'équations et d'inégalités polynomiales. Nous nous concentrerons plus particulièrement sur le cas d'une équation de degré $D$ en $n$ variables. Après avoir motivé l'importance de cette spécification, nous procéderons dans un premier temps à un panorama des algorithmes récemment proposés et permettant ce calcul. Ces algorithmes s'inscrivent dans la lignée initiée par Grigoriev et Vorobjov, et développée notamment par Basu, Pollack et Roy. Leur complexité est asymptotiquement optimale (polynomiale en $D^n$) et leur efficacité pratique est sensible pour $n\geq 3$ lorsque le lieu solution est sans singularité.

Dans un deuxième temps, nous nous focaliserons sur l'étude du cas singulier réputé pour être géométriquement plus difficile à appréhender. Informatiquement, les solutions algorithmiques proposées précédemment pâtissaient d'un surcoût calculatoire comparativement aux cas sans singularités. Les algorithmes que nous allons exposer gèrent optimalement ces cas singuliers, en ce sens que leur complexité binaire est exponentiellement meilleure que celle des précédentes contributions. Nous montrerons par ailleurs que sur des instances singulières, nos algorithmes effectuent moins d'opérations binaires que sur des instances génériques.

Si le temps le permet, nous terminerons en appliquant ces travaux au calcul des singularités à l'infini d'une application polynomiale et à la résolution d'inégalités polynomiales.