LIP6 2001/028
- Thèse
Résolution réelle des systèmes polynomiaux en dimension positive - M. Safey El Din
- 197 pages - 05/01/2001- document en - http://www.lip6.fr/lip6/reports/2001/lip6.2001.028.pdf - 1,545 Ko
- Contact : Mohab.Safey (at) nulllip6.fr
- Ancien Thème : CALFOR
- Mots clés : Calcul Formel, Systèmes polynomiaux, Solutions réelles
- Directeur de la publication : David.Massot (at) nulllip6.fr
Cette thèse traîte de l'étude des solutions réelles des systèmes polynomiaux en dimension positive. Plus précisement, il s'agit de déterminer au moins un point par composante connexe sur une variété algébrique réelle. Dans le cadre des méthodes étudiées, ceci peut être vu comme une étape du processus de résolution des systèmes d'équations et d'inégalités polynomiales, et du problème d'élimination des quantificateurs.
Les travaux de ma thèse consistent a remanier algorithmiquement une méthode (méthode des points critiques) pour obtenir des algorithmes efficaces en pratique donnant au moins un point par composante connexe sur une variété algébrique réelle.
Le principe de cette méthode est connu : il s'agit de calculer les points critiques d'une application régulière atteignant des extrema locaux sur chaque composante connexe de la variété. L'objectif est de ramener le problème à l'étude de systèmes de dimension zero pour
lesquels il existe des algorithmes de résolution efficaces. La complexité théorique des algorithmes relevant de cette méthode est simplement exponentielle en le nombre de variables (tant en terme de nombre d'opérations qu'en terme de taille de la sortie), ce qui est
optimal pour un problème de cette nature. Néanmoins, les techniques mises en oeuvre (déformations infinitésimales, somme de carrés) pour atteindre cette complexité ne permettent pas d'obtenir des implantations efficaces.
Dans ma thèse, une première étude (menée avec F. Rouillier et M.-F. Roy) traîte du cas des hypersurfaces (une seule équation). Dans les cas sans singularités, le calcul des points critiques de la fonction distance à un point permet de trouver au moins un point par composante connexe sur la variété étudiée. Dans les cas où l'hypersurface contient une infinité de singularités, une seule déformation infinitésimale est requise pour se ramener au cas précédent. Des outils de calcul efficace sont donnés pour la résolution de tels systèmes zéro-dimensionnels à coefficients infinitésimaux. Les implantations de l'algorithme obtenu sont plus efficaces que les meilleures implantations de l'algorithme le plus connu pour resoudre ce type de problème (la décomposition cylindrique algébrique). Dans les cas singuliers, des progrès restent à faire.
Une deuxième étude (avec P. Aubry et F. Rouillier) traîte du cas des systèmes polynomiaux (plusieurs équations). Les singularités sont isolées et étudiées en tant que variétés algébriques dont la dimension est strictement inférieure à celle de la variété initiale, tandis que les points réguliers de la variété, et qui sont critiques pour la fonction distance à un point, sont calculés. L'algorithme obtenu étudie itérativement des variétés équi-dimensionnelles dont la dimension décroît à chaque pas. Ses implantations sont plus efficaces de plusieurs ordres de grandeur que les meilleures implantations de l'algorithme de décomposition cylindrique algébrique.
Dans un troisième temps, ces algorithmes sont significativement améliorés. En tirant profit d'informations sur la projection de la variété, l'etude d'ensembles constructibles est intégrée au processus de résolution. Une déformation infinitésimale est nécessaire et les outils de calcul développés précédemment sont utilisés à bon escient dans ce cadre.
Enfin, les outils et implantations développés sont utilisés pour résoudre de manière automatisée un cas du problème d'interpolation de Birkhoff qui restait un problème ouvert.
Les travaux de ma thèse consistent a remanier algorithmiquement une méthode (méthode des points critiques) pour obtenir des algorithmes efficaces en pratique donnant au moins un point par composante connexe sur une variété algébrique réelle.
Le principe de cette méthode est connu : il s'agit de calculer les points critiques d'une application régulière atteignant des extrema locaux sur chaque composante connexe de la variété. L'objectif est de ramener le problème à l'étude de systèmes de dimension zero pour
lesquels il existe des algorithmes de résolution efficaces. La complexité théorique des algorithmes relevant de cette méthode est simplement exponentielle en le nombre de variables (tant en terme de nombre d'opérations qu'en terme de taille de la sortie), ce qui est
optimal pour un problème de cette nature. Néanmoins, les techniques mises en oeuvre (déformations infinitésimales, somme de carrés) pour atteindre cette complexité ne permettent pas d'obtenir des implantations efficaces.
Dans ma thèse, une première étude (menée avec F. Rouillier et M.-F. Roy) traîte du cas des hypersurfaces (une seule équation). Dans les cas sans singularités, le calcul des points critiques de la fonction distance à un point permet de trouver au moins un point par composante connexe sur la variété étudiée. Dans les cas où l'hypersurface contient une infinité de singularités, une seule déformation infinitésimale est requise pour se ramener au cas précédent. Des outils de calcul efficace sont donnés pour la résolution de tels systèmes zéro-dimensionnels à coefficients infinitésimaux. Les implantations de l'algorithme obtenu sont plus efficaces que les meilleures implantations de l'algorithme le plus connu pour resoudre ce type de problème (la décomposition cylindrique algébrique). Dans les cas singuliers, des progrès restent à faire.
Une deuxième étude (avec P. Aubry et F. Rouillier) traîte du cas des systèmes polynomiaux (plusieurs équations). Les singularités sont isolées et étudiées en tant que variétés algébriques dont la dimension est strictement inférieure à celle de la variété initiale, tandis que les points réguliers de la variété, et qui sont critiques pour la fonction distance à un point, sont calculés. L'algorithme obtenu étudie itérativement des variétés équi-dimensionnelles dont la dimension décroît à chaque pas. Ses implantations sont plus efficaces de plusieurs ordres de grandeur que les meilleures implantations de l'algorithme de décomposition cylindrique algébrique.
Dans un troisième temps, ces algorithmes sont significativement améliorés. En tirant profit d'informations sur la projection de la variété, l'etude d'ensembles constructibles est intégrée au processus de résolution. Une déformation infinitésimale est nécessaire et les outils de calcul développés précédemment sont utilisés à bon escient dans ce cadre.
Enfin, les outils et implantations développés sont utilisés pour résoudre de manière automatisée un cas du problème d'interpolation de Birkhoff qui restait un problème ouvert.