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 |
---|---|
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/Territory | United States |
City | Philadelphia, PA. |
Period | 3/08/03 → 6/08/03 |