LIP6 2001/028
- Thesis
Résolution réelle des systèmes polynomiaux en dimension positive - M. Safey El Din
- 197 pages - 01/05/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
- Keywords : Computer Algebra, Polynomial systems, real solutions
- Publisher : David.Massot (at) nulllip6.fr
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.
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.