On order-Invariance of a binomial over a nullifying cell

Scott McCallum*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contributionpeer-review


The improved projection operation for cylindrical algebraic decomposition (CAD) described in [10] requires for its validity the crucial concept of order-invariance, A real polynomial f(x1,..., Xr] is said to be order-invariant in a subset c of Rr if the order (of vanishing) of f at the point p is constant as p varies throughout c. The application of the improved projection which is perhaps simplest conceptually is in the construction of a CAD for a set of polynomials which is well-oriented in a certain sense. Given a well-oriented set A of r-variate integral polynomials algorithm CADW [10] uses the improved projection to construct a CAD of R r which is order-invariant for each polynomial in A. A draw-back of CADW is that it halts in failure, reporting that A is not well-oriented, when presented with a non-well-oriented set A as input. Such failure of CADW is potentially serious, because it forces the user to fall back on less efficient projection operators (such as the Collins-Hong projection) for CAD. The present paper describes an efficient method for avoiding the failure of CADW in certain special non-well-oriented cases. The method is based upon a sufficient criterion for the order of a polynomial h(x1,..., xr] of the special form h = a(x1,...,xr-1)xr k + b(x1,...,xr-1) (which we shall call a binomial in xr) to be 1 throughout the entire cylinder over a nullifying point p ∈ Rr-1 for h (that is, a point p for which h(p, xr) = 0 identically). Following a review of CADW, the sufficient criterion referred to is motivated and proved. The algorithmic application of the criterion is carefully described and validated, and an example discussed.

Original languageEnglish
Title of host publicationProceeding ISSAC '03 Proceedings of the 2003 international symposium on Symbolic and algebraic computation
EditorsJ. Rafael Sendra
Place of PublicationNew York, NY
PublisherAssociation for Computing Machinery (ACM)
Number of pages7
ISBN (Print)1581136412
Publication statusPublished - Aug 2003
EventProceedings of the 2003 International Symposium on Symbolic and Algebraic Computation, (ISSAC 2003) - Philadelphia, PA., United States
Duration: 3 Aug 20036 Aug 2003


OtherProceedings of the 2003 International Symposium on Symbolic and Algebraic Computation, (ISSAC 2003)
CountryUnited States
CityPhiladelphia, PA.

Fingerprint Dive into the research topics of 'On order-Invariance of a binomial over a nullifying cell'. Together they form a unique fingerprint.

Cite this