## 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(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 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(x_{1},..., x_{r}] of the special form h = a(x_{1},...,x_{r-1})x_{r} ^{k} + b(x_{1},...,x_{r-1}) (which we shall call a binomial in x_{r}) to be 1 throughout the entire cylinder over a nullifying point p ∈ 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.

Original language | English |
---|---|

Title of host publication | Proceeding ISSAC '03 Proceedings of the 2003 international symposium on Symbolic and algebraic computation |

Editors | J. Rafael Sendra |

Place of Publication | New York, NY |

Publisher | Association for Computing Machinery (ACM) |

Pages | 184-190 |

Number of pages | 7 |

ISBN (Print) | 1581136412 |

DOIs | |

Publication status | Published - Aug 2003 |

Event | Proceedings of the 2003 International Symposium on Symbolic and Algebraic Computation, (ISSAC 2003) - Philadelphia, PA., United States Duration: 3 Aug 2003 → 6 Aug 2003 |

### Other

Other | Proceedings of the 2003 International Symposium on Symbolic and Algebraic Computation, (ISSAC 2003) |
---|---|

Country | United States |

City | Philadelphia, PA. |

Period | 3/08/03 → 6/08/03 |