on order-invariance of a binomial over a nullifying cell
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(x 1 , ..., x r ) is said to be order-invariant in a subset c of R r 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 drawback 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(x 1 , ..., x r ) of the special form h = a(x 1 , ..., x r-1 )x r k + b(x 1 , ldots, x r-1 ) (which we shall call a binomial in x r ) to be 1 throughout the entire cylinder over a nullifying point p in R r-1 for h (that is, a point p for which h(p, x r ) = 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.
order-invariance projection cad