Real Solving for positive dimensional systems

Ph. Aubry, F. Rouillier, M. Safey El Din

LIP6 2000/009: Rapport de Recherche LIP6 / LIP6 research reports
16 pages - Mars/March 2000 - Document en anglais.

Get it : 107 Ko /Kb

Contact : par mail / e-mail

Thème/Team: Calcul Formel

Titre français : Résolution réelle des systèmes polynomiaux en dimension positive
Titre anglais : Real Solving for positive dimensional systems

Résumé : 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.

Abstract : Finding one point on each semi-algebraically connected component of a real algebraic variety, or at least deciding if such a variety is empty or not, is a fundamental problem of computational real algebraic geometry. Even though numerous studies have been done on the subject, only a few number of efficient implementations exists.
In this paper, we propose a new efficient and practical algorithm for computing such points. By studying the critical points of the restriction to the variety of the distance function to one well chosen point, we show how to provide a set of zero-dimensional systems whose zeroes contain at least one point on each semi-algebraically connected component of the studied variety, without any assumption neither on the variety (smoothness or compactness for example) nor on the system of equations that define it.
Once such a result is computed, one can then apply, for each computed zero-dimensional system, any symbolic or numerical algorithm for counting or approximating the solutions. We have made experiments using a set of pure exact methods.
The practical efficiency of our method is due to the fact that we do not apply any infinitesimal deformations, conversely to the existing methods based on similar strategy.

Mots-clés : Racines réelles, variété algébrique réelle, Composantes connexes, Systèmes polynomiaux, Bases de Grobner, Ensembles traingulaires

Key-words : Real roots, real algebraic variety, Connected components, Polynomial systems, Grobner bases, Triangular sets

Publications internes LIP6 2000 / LIP6 research reports 2000

Responsable Éditorial / Editor :David.Massot@lip6.fr