Résolution réelle des systèmes polynomiaux en dimension positive

M. Safey El Din

LIP6 2001/028: THÈSE de DOCTORAT de l'UNIVERSITÉ PARIS 6 LIP6 / LIP6 research reports
197 pages - Janvier/January 2001 - French document.

Get it : 1509 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é : 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.

Abstract : The subject of this thesis is the study of real solutions of algebraic systems. More precisely, the aim is to design efficient algorithms in practice to compute at least one point in each connected component of a real algebraic set.
The used algorithmic tools are inspired by the critical point method. Its principle is the following~: compute the critical points of a reagular application reaching its local extremal values on each connected component of the studied real algebraic set. The aim of the method is to reduce the problem to counting and isolating real solutions of zero-dimensional algebraic systems. Problems occur in the cases of non compact or non smooth algebraic sets.
The first proposed algorithm deals with the hypersurface case. The chosen regular application is the distance function to a generic point, thus it reaches its local extremal values on each connected component even if they are not compact. In the case where the hypersurface contains an infinity, an infinetsimal deformation is performed. We give several algorithmic tools to solve zero-dimensional systems with infinitesimal coefficients. This algorithm has been implemented and tested on several problems. In the case of non singular hypersurfaces, these implementations are more efficient to the best implementations of Cylindrical Algebraic Decomposition. Some progress have to be done in the singular case.
The second algorithm generalizes the first one~: it deals with polynomial systems and does not introduce any infinitesimal even in the singular case. Singularities are isolated studied as an algebraic variety of dimension strictly inferior to the dimension of the initial variety. Hence, the obtained algorithm performs a recursion on the dimension of the studied varieties. Its implementation speeds up the preceeding algorithm and allows to solve some problems which were untractable by the previous methods.
Finally, the tools and implementations described above are used to solve automaticall a case of the Birkhoff Interpolation Problem which was not solved.

Mots-clés : Calcul Formel, Systèmes polynomiaux, Solutions réelles

Key-words : Computer Algebra, Polynomial systems, real solutions

Publications internes LIP6 2001 / LIP6 research reports 2001

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