Abstract
A key component of the cylindrical algebraic decomposition (cad) algorithm is the projection (or elimination) operation: the projection of a set A of r-variate integral polynomials, where r ≥ 2 is defined to be a certain set PROJ(A) of (r − l)-variate integral polynomials. The property of the map PROJ of particular relevance to the cad algorithm is that, for any finite set A of r-variate integral polynomials, where r ≥ 2, if S is any connected subset of (r − 1)-dimensional real space ℝ(r−1) in which every element of PROJ(A) is invariant in sign then the portion of the zero set of the product of those elements of A which do not vanish identically on S that lies in the cylinder S × ℝ over S consists of a number (possibly 0) of disjoint “layers” (or sections) over S in each of which every element of A is sign-invariant: that is, A is “delineable” on S. It follows from this property that, for any finite set A of r-variate integral polynomials, r ≥ 2, any decomposition of ℝ(r−1) into connected regions such that every polynomial in PROJ (A) is invariant in sign throughout every region can be extended to a decomposition of ℝr (consisting of the union of all of the above-mentioned layers and the regions in between successive layers, for each region of ℝ(r−1) such that every polynomial in A is invariant in sign throughout every region of ℝr.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1998 Springer-Verlag/Wien
About this paper
Cite this paper
McCallum, S. (1998). An Improved Projection Operation for Cylindrical Algebraic Decomposition. In: Caviness, B.F., Johnson, J.R. (eds) Quantifier Elimination and Cylindrical Algebraic Decomposition. Texts and Monographs in Symbolic Computation. Springer, Vienna. https://doi.org/10.1007/978-3-7091-9459-1_12
Download citation
DOI: https://doi.org/10.1007/978-3-7091-9459-1_12
Publisher Name: Springer, Vienna
Print ISBN: 978-3-211-82794-9
Online ISBN: 978-3-7091-9459-1
eBook Packages: Springer Book Archive