Computing with semi-algebraic sets: relaxation techniques and effective boundaries (Q1940931)

This work develops the study of \textit{parametric polynomial systems}, especially looking at \textit{real root classification} and \textit{triangular decomposition} for semi-algebraic systems (see [\textit{C. Chen, J. H. Davenport, M. Moreno Maza, B. Xia} and \textit{R. Xiao}, Proc. of ISSAC, 187--194 (2010)]) from an algorithmic point of view. The algorithms solving parametric polynomial systems via triangular decomposition are mainly based on the algebraic notion of \textit{border polynomial}. In this paper, the authors substitute the notion of border polynomial with a more geometric one, the \textit{effective boundary}, underlining the main differences among the two. Moreover, they show that effective boundaries describe the topological properties of semi-algebraic sets in a more precise way and they can be used to improve algorithms computing \textit{finger polynomial sets}. Given a parametric polynomial system \(S\) in \(\mathbb{Q}[\mathbf{u},\mathbf{y}]\) an important problem is to find the values of \(\mathbf{u}\) making \(S\) have a fixed number \(k\) of distinct solutions in \(\mathbb{R}\). Nevertheless, for many applications, given a well determined system \(S\) with border polynomial \(b\), such that \(b(\mathbf{u})\neq 0\), it turns out to be enough to know the necessary and sufficient conditions to give \(\mathbf{u}\) to have \(k\) distinct real solutions for \(S\). The search for the conditions above entails the analysis of the set \(B\) of irreducible factors of \(b\), looking for a disjunction of strict sign conditions. If such a disjunction cannot be found, \(B\) is extended to a larger set. Heavy computations can be avoided introducing the \textit{relaxation} technique. It essentially decides if the strict sign conditions of polynomials not belonging to the original set \(B\) can be ``transformed'' into non-strict conditions. Considering some significant examples, the authors compare the execution of the algorithm with and without relaxation, and provide the running time and the number of components found in the two cases. The procedure is implemented in Maple16.