Computational problems related to positive polynomials

Fabrice Rouillier 1, 2
1 CALFOR - Calcul formel
LIP6 - Laboratoire d'Informatique de Paris 6
2 SPACES - Solving problems through algebraic computation and efficient software
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : Deciding if a semi-algebraic set is empty or not is critical for the study of problems related to positive polynomials. Only few implemented algorithms exists for this purpose : the Cylindrical Algebraic Decomposition (CAD) is the main one. Unfortunately, only small problems (with few variables and low degrees) can be solved using such methods. On the other hand, many algorithms with a good asymptotic complexity are proposed in the literature. Most of them are based on the so called Critical Points Method, for computing at least on point on each semi-algebraically connected component of a real algebraic set, used as a black box for deciding if a semi-algebraic set is empty or not. Unfortunately, due to the use of various tricks for keeping a good theoretical complexity (sum of squares, infinitesimal deformations, etc.), straightforward implementations of these algorithms are inefficient. We propose a new version of the Critical Points Method using the distance function to one (well chosen) point. Given any algebraic set $V$, we define an algebraic set ${\cal C}(V,A)$ that contains these critical points and a sub-algebraic variety of $V$. Our main result consists in proving that a good point $A$ may be chosen so that ${\cal C}(V,A)$ is the disjoint union of a finite set of points and a sub-algebraic variety $W$ of $V$ with smaller dimension than $V$, without any restriction neither on the variety (do not need to be smooth or compact) nor on the set of polynomials used in the computations for the definition of $V$ (for example, the generated ideal do not need to be prime). We are thus leaded to compute the isolated points of ${\cal C}(V,A)$ and to study, in the same way, the sub-variety $W$. We therefore obtain an algorithm without any infinitesimal deformation whose proof is simply based on the fact that the dimension of the studied varieties strictly decreases at each step. The limitations of such an algorithm are pointed out and solved (number of determinants) : we show how to use the theory of polynomial triangular sets to optimize the computations. We finally presents some practical experiments which illustrate the practical behavior of our algorithm. It shows the interest of our approach and justifies our choices.
Type de document :
Communication dans un congrès
Workshop on positive polynomials, 2002, Oberwolfach, Germany. 2002
Liste complète des métadonnées
Contributeur : Publications Loria <>
Soumis le : mardi 26 septembre 2006 - 14:53:17
Dernière modification le : mercredi 21 mars 2018 - 18:58:14


  • HAL Id : inria-00100983, version 1



Fabrice Rouillier. Computational problems related to positive polynomials. Workshop on positive polynomials, 2002, Oberwolfach, Germany. 2002. 〈inria-00100983〉



Consultations de la notice