Computing with semi-algebraic sets: relaxation techniques and effective boundaries
type: Item
instance of: scholarly article
title: Computing with semi-algebraic sets: relaxation techniques and effective boundaries
zbMATH Open document ID: 1277.13021
author: Changbo Chen
author: Marc Moreno Maza
author: Bican Xia
author: Rong Xiao
author: James H. Davenport
published in: Journal of Symbolic Computation
publication date: 2013-03-11T00:00:00Z
review text: 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 …
reviewed by: Michela Ceria
Mathematics Subject Classification ID: 13M10
Mathematics Subject Classification ID: 13P10
Mathematics Subject Classification ID: 13-04
zbMATH DE Number: 6143070
zbMATH Keywords: parametric polynomial systems
zbMATH Keywords: triangular decomposition
zbMATH Keywords: regular semi-algebraic system
zbMATH Keywords: border polynomial
zbMATH Keywords: effective boundary
zbMATH Keywords: relaxation
describes a project that uses: Maple
describes a project that uses: RegularChains
MaRDI profile type: Publication
full work available at URL: j.jsc.2012.05.013
OpenAlex ID: W2112151791
Wikidata QID: Q59590585
DOI: 10.1016/J.JSC.2012.05.013
DBLP publication ID: journals/jsc/ChenDMXX13
Recommended article: Computing with semi-algebraic sets represented by triangular decomposition
Recommended article: Effective Set Membership in Computer Algebra and Beyond
Recommended article: Computation with semialgebraic sets represented by cylindrical algebraic formulas
Recommended article: Computing Roadmaps of General Semi-Algebraic Sets
Recommended article: Q4038743
Recommended article: Q4227319
Recommended article: Q4228467
Recommended article: Q4038735
Recommended article: Q4232468
Recommended article: Computing the Hausdorff Boundary Measure of Semialgebraic Sets
description: scientific article; zbMATH DE number 6143070