Solving parametric polynomial systems

We present a new algorithm for solving basic parametric constructible or semi-algebraic systems of the form C = {x is an element of C-n, p(1) (X) = 0,..., p(s)(x) = 0, f(1) (x) not equal 0,..., f(l)(x) not equal 0} or S = {x is an element of R-n p(1) (x) = 0,..., p(s)(x) = 0, f(1) (x) > 0,.., f(1)(x) > 0), where p(i), f(i) is an element of Q[U, X], U = [U-l, U-d] is the set of parameters and X = [Xd+1,...,X-n] the set of unknowns. If Pi(U) denotes the canonical projection onto the parameter's space, solving C or S is reduced to the computation of submanifolds U subset of C-d or U subset of R-d such that (Pi(-1)(U) (U) boolean AND C, H-U) is an analytic covering of U (we say that U has the (H-U, C)-covering property). This guarantees that the cardinality of Pi(-1)(U) (u) boolean AND C is constant on a neighborhood of u, that Pi(-1)(U) (U) boolean AND C is a finite collection of sheets and that Pi(U) is a local diffeomorphism from each of these sheets onto U. We show that the complement in (Pi(U)) over bar (C) (the closure of Pi(U) (C) for the usual topology of C-n) of the union of all the open subsets of (Pi(U)) over bar (C) which have the (Pi(U), C)-covering property is a Zariski closed set which is called the minimal discriminant variety of C w. rt. Pi(U), denoted as W-D. We propose an algorithm to compute W-D efficiently. The variety W-D can then be used to solve the parametric system C (resp. S) as long as one can describe (Pi(U)) over bar (C)\W-D (resp. R-d boolean AND ((Pi(U)) over bar (C.)\W-D)). This can be done by using the critical points method or an "open" cylindrical algebraic decomposition. (c) 2007 Elsevier Ltd. All rights reserved.