HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

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.
Document type :
Complete list of metadata

Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Monday, October 16, 2006 - 10:22:28 AM
Last modification on : Friday, February 4, 2022 - 3:13:43 AM
Long-term archiving on: : Monday, September 20, 2010 - 5:09:33 PM


  • 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⟩



Record views


Files downloads