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

Solving Parametric Polynomial Systems

Daniel Lazard 1, 2 Fabrice Rouillier 1, 2
2 SALSA - Solvers for Algebraic Systems and Applications
LIP6 - Laboratoire d'Informatique de Paris 6, Inria Paris-Rocquencourt
Abstract : We present a new algorithm for solving basic parametric constructible or semi-algebraic systems like $\mathcal{C} = \{ x \in \Cp_1 ( x ) = 0, \ldots, p_s ( x ) = 0, f_1 ( x ) \neq 0, \ldots, f_l ( x ) \neq 0 \}$ or $\mathcal{S} = \{ x \in \Cp_1 ( x ) = 0, \ldots, p_s ( x ) = 0, f_1 ( x ) > 0, \ldots, f_l ( x ) > 0 \}$, where $p_i, f_i \in \Q [ U, X ]$, $U = [ U_1, \ldots, U_d ]$ is the set of parameters and $X = [ X_{d + 1}, \ldots, X_n ]$ the set of unknowns. If $\Pi_U$ denotes the canonical projection on the parameter's space, solving $\mathcal{C}$ or $\mathcal{S}$ remains to compute sub-manifolds $\mathcal{U} \subset \C(resp. $\mathcal{U} \subset \R^d$) such that $( \Pi_U^{- 1} ( \mathcal{U} ) \cap \mathcal{C}, \Pi_U )$ is an analytic covering of $\mathcal{U}$ (we say that $\mathcal{U}$ has the $( \Pi_U, \mathcal{C} )$-\textit{covering property}). This guarantees that the cardinal of $\Pi_U^{- 1} ( \mathcal{u} ) \cap \mathcal{C}$ is locally constant on $\mathcal{U}$ and that $\Pi_U^{- 1} ( \mathcal{U} ) \cap \mathcal{C}$ is a finite collection of sheets which are all locally homeomorphic to $\mathcal{U}$. In the case where $\Pi_U ( \mathcal{C} )$ is dense in $\C all the known algorithms for solving $\mathcal{C}$ or $\mathcal{S}$ compute implicitly or explicitly a Zariski closed subset $W$ such that any sub-manifold of $\Csetminus W$ have the ($\Pi_U, \mathcal{C}$)-covering property. We introduce the \textit{discriminant varieties of $\mathcal{C}$ w.r.t. $\Pi_U$} which are algebraic sets with the above property (even in the cases where $\Pi_U$ is not dense in $\C. We then show that the set of points of $\overline{\Pi_U ( \mathcal{C} )}$ which do not have any neighborhood with the ($\Pi_U,\mathcal{C}$)-covering property is a Zariski closed set and thus the \textit{minimal discriminant variety of $\mathcal{C}$ w.r.t. $\Pi_U$} and we propose an algorithm to compute it efficiently. Thus, solving the parametric system $\mathcal{C}$ (resp. $\mathcal{S}$) then remains to describe $\Csetminus W_D$ (resp. $\R^d \setminus W_D$) which can be done using critical points method or partial CAD based strategies. We did not fully study the complexity, but in the case of systems where $\overline{\Pi_U ( \mathcal{C} )} = \C the degree of the minimal discriminant variety as well as the running time of an algorithm able to compute it are singly exponential in the number of variables according to already known results.
Document type :
Complete list of metadata

Cited literature [28 references]  Display  Hide  Download

Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Friday, May 19, 2006 - 9:11:34 PM
Last modification on : Friday, February 4, 2022 - 3:07:41 AM
Long-term archiving on: : Sunday, April 4, 2010 - 9:42:24 PM


  • HAL Id : inria-00070678, version 1


Daniel Lazard, Fabrice Rouillier. Solving Parametric Polynomial Systems. [Research Report] RR-5322, INRIA. 2004, pp.23. ⟨inria-00070678⟩



Record views


Files downloads