LIP6 2000/009
- Rapports de recherche
Résolution réelle des systèmes polynomiaux en dimension positive - Ph. Aubry, F. Rouillier, M. Safey El Din
- 16 pages - 21/03/2000- document en - http://www.lip6.fr/lip6/reports/2000/lip6.2000.009.ps.gz - 110 Ko
- Contact : Philippe.Aubry (at) nulllip6.fr, Fabrice.Rouillier (at) nullloria.fr, Mohab.Safey (at) nulllip6.fr
- Ancien Thème : CALFOR
- Mots clés : Racines réelles, variété algébrique réelle, Composantes connexes, Systèmes polynomiaux, Bases de Grobner, Ensembles traingulaires
- Directeur de la publication : David.Massot (at) nulllip6.fr
Trouver au moins un point par composante semi-algébriquement connexe d'une variété algébrique réelle, ou décider du vide d'une telle variété est un des problèmes algorithmiques fondamentaux de la géométrie algébriques réelle effective. Malgré le nombre important d'études existantes sur ce sujet, il existe très peu d'implantations efficaces résolvant ce problème de manière satisfaisante.
Dans cet article, nous proposons un nouvel algorithme, efficace en pratique qui calcule au moins un point par composante connexe d'une variété algébrique réelle. En étudiant les points critiques de la restriction de la fonction distance à une telle variété, on montre comment calculer des systèmes zéro-dimensionnels dont les solutions contiennent au moins un point par composante connexe de la variété que l'on veut étudier, sans faire la moindre hypothèse de compacité, de régularité, ou de généricité.
Une fois ces systèmes zéro-dimensionnels obtenus, on peut alors leur appliquer un algorithme (symbolique ou numérique) pour compter et isoler leurs solutions réelles. Dans nos tests, nous n'utilisons que des méthodes symboliques.
L'efficacité de notre méthode tient dans le fait que nous ne faisons aucune déformation infinitésimale, contrairement aux autres méthodes basées sur des stratégies similaires.
Dans cet article, nous proposons un nouvel algorithme, efficace en pratique qui calcule au moins un point par composante connexe d'une variété algébrique réelle. En étudiant les points critiques de la restriction de la fonction distance à une telle variété, on montre comment calculer des systèmes zéro-dimensionnels dont les solutions contiennent au moins un point par composante connexe de la variété que l'on veut étudier, sans faire la moindre hypothèse de compacité, de régularité, ou de généricité.
Une fois ces systèmes zéro-dimensionnels obtenus, on peut alors leur appliquer un algorithme (symbolique ou numérique) pour compter et isoler leurs solutions réelles. Dans nos tests, nous n'utilisons que des méthodes symboliques.
L'efficacité de notre méthode tient dans le fait que nous ne faisons aucune déformation infinitésimale, contrairement aux autres méthodes basées sur des stratégies similaires.