An Improved Projection Operation for Cylindrical Algebraic Decomposition

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.

Editors and Affiliations

1. Department of Computer and Information Sciences, University of Delaware, Newark, Delaware, USA

   Bob F. Caviness

2. Department of Mathematics and Computer Science, Drexel University, Philadelphia, Pennsylvania, USA

   Jeremy R. Johnson

Reprints and permissions

© 1998 Springer-Verlag/Wien

Policies and ethics