Testing Sign Conditions on a Multivariate Polynomial and Applications

Mohab Safey El Din 1, 2
2 SALSA - Solvers for Algebraic Systems and Applications
LIP6 - Laboratoire d'Informatique de Paris 6, Inria Paris-Rocquencourt
Abstract : Let $f$ be a polynomial in $\Q[X_1, \ldots, X_n]$ of degree $D$. We focus on testing the emptiness and computing at least one point in each connected component of the semi-algebraic set defined by $f>0$ (or $f<0$ or $f\neq 0$). To this end, the problem is reduced to computing at least one point in each connected component of a hypersurface defined by $f-e=0$ for $e\in \Q$ {\em positive and small enough}. We provide an algorithm allowing us to determine a positive rational number $e$ which is small enough in this sense. This is based on the efficient computation of the set of {\em generalized critical values} of the mapping $f: y\in \C^n \rightarrow f(y)\in \C$ which is the union of the classical set $K_0(f)$ of critical values of the mapping $f$ and $K_\infty(f)$ of {\em asymptotic critical values} of the mapping $f$. Then, we show how to use the computation of generalized critical values in order to obtain an efficient algorithm deciding the emptiness of a semi-algebraic set defined by a single inequality or a single inequation. At last, we show how to apply our contribution to determining if a hypersurface contains real regular points. We provide complexity estimates for probabilistic versions of the latter algorithms which are within $\mathcal{O}(n^7D^{4n})$ arithmetic operations in $\Q$. The paper ends with practical experiments showing the efficiency of our approach.
Type de document :
[Research Report] RR-5995, INRIA. 2006
Liste complète des métadonnées

Contributeur : Rapport de Recherche Inria <>
Soumis le : lundi 16 octobre 2006 - 10:22:28
Dernière modification le : jeudi 22 novembre 2018 - 14:31:50
Document(s) archivé(s) le : lundi 20 septembre 2010 - 17:09:33



  • HAL Id : inria-00105835, version 2


Mohab Safey El Din. Testing Sign Conditions on a Multivariate Polynomial and Applications. [Research Report] RR-5995, INRIA. 2006. 〈inria-00105835v2〉



Consultations de la notice


Téléchargements de fichiers