Computing with semi-algebraic sets: Relaxation techniques and effective boundaries

We discuss parametric polynomial systems, with algorithms for real root classification and triangular decomposition of semi-algebraic systems as our main applications. We exhibit new results in the theory of border polynomials of parametric semi-algebraic systems: in particular a geometric characterization of its "true boundary" (Definition 1). In order to optimize the corresponding decomposition algorithms, we also propose a technique, that we call relaxation, which can simplify the decomposition process and reduce the number of components in the output. This paper extends our earlier works (Chen et al., 2010, 2011). (C) 2012 Elsevier B.V. All rights reserved.Computer Science, Theory & MethodsMathematics, AppliedSCI(E)0ARTICLE,SI72-965