Testing Sign Conditions on a Multivariate Polynomial and Applications - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2006

Testing Sign Conditions on a Multivariate Polynomial and Applications

Résumé

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.
Fichier principal
Vignette du fichier
vca.pdf (487.41 Ko) Télécharger le fichier

Dates et versions

inria-00105835 , version 1 (12-10-2006)
inria-00105835 , version 2 (16-10-2006)

Identifiants

  • HAL Id : inria-00105835 , version 1

Citer

Mohab Safey El Din. Testing Sign Conditions on a Multivariate Polynomial and Applications. [Research Report] 2006. ⟨inria-00105835v1⟩
150 Consultations
310 Téléchargements

Partager

Gmail Facebook X LinkedIn More