On order-Invariance of a binomial over a nullifying cell

*Corresponding author for this work

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

Abstract

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 language English Proceeding ISSAC '03 Proceedings of the 2003 international symposium on Symbolic and algebraic computation J. Rafael Sendra New York, NY Association for Computing Machinery (ACM) 184-190 7 1581136412 https://doi.org/10.1145/860854.860896 Published - Aug 2003 Proceedings of the 2003 International Symposium on Symbolic and Algebraic Computation, (ISSAC 2003) - Philadelphia, PA., United StatesDuration: 3 Aug 2003 → 6 Aug 2003

Other

Other Proceedings of the 2003 International Symposium on Symbolic and Algebraic Computation, (ISSAC 2003) United States Philadelphia, PA. 3/08/03 → 6/08/03