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

# Testing Sign Conditions on a Multivariate Polynomial and Applications

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.
Keywords :
Document type :
Reports

https://hal.inria.fr/inria-00105835
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

### Identifiers

• HAL Id : inria-00105835, version 2

### Citation

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

Record views