On order-invariance of a binomial over a nullifying cell

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 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(x1, ..., xr) of the special form h = a(x1, ..., xr-1)xr^k + b(x1, ldots, xr-1) (which we shall call a binomial in xr) 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, 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.

REFERENCES

• 1: Dennis S. Arnon , George E. Collins , Scott McCallum, Cylindrical algebraic decomposition I: the basic algorithm, SIAM Journal on Computing, v.13 n.4, p.865-877, Nov. 1984 [doi>10.1137/0213054]
• 2: Dennis S. Arnon , Maurice Mignotte, On mechanical quantifier elimination for elementary algebra and geometry, Journal of Symbolic Computation, v.5 n.1-2, p.237-259, February/April 1988 [doi>10.1016/S0747-7171(88)80014-2]
• 3: Christopher W. Brown, Improved projection for cylindrical algebraic decomposition, Journal of Symbolic Computation, v.32 n.5, p.447-465, November 2001 [doi>10.1006/jsco.2001.0463]
• 4: Brown, C. W. The Mccallum projection, lifting and order-invariance. Available at http://www.cs.usna.edu/˜wcbrown/research/, 2001.
• 5: Christopher W. Brown, Simple CAD construction and its applications, Journal of Symbolic Computation, v.31 n.5, p.521-547, May 2001 [doi>10.1006/jsco.2000.0394]
• 6: Caviness, B., and Johnson, J. R., Eds. Quantifier Elimination and Cylindrical Algebraic Decomposition. Texts and Monographs in Symbolic Computation. Springer-Verlag, 1998.
• 7: George E. Collins, Hauptvortrag: Quantifier elimination for real closed fields by cylindrical algebraic decomposition, Proceedings of the 2nd GI Conference on Automata Theory and Formal Languages, p.134-183, May 20-23, 1975
• 8: Loos, R. Computing in algebraic extensions. In Computing, Supplementum 4, R. L. B. Buchberger, G. E. Collins, Ed. Springer-Verlag, Vienna, 1982, pp. 173--187.
• 9: Scott McCallum, An improved projection operation for cylindrical algebraic decomposition of three-dimensional space, Journal of Symbolic Computation, v.5 n.1-2, p.141-161, February/April 1988 [doi>10.1016/S0747-7171(88)80010-5]
• 10: McCallum, S. An improved projection operator for cylindrical algebraic decomposition. In Quantifier Elimination and Cylindrical Algebraic Decomposition (1998), B. Caviness and J. Johnson, Eds., Texts and Monographs in Symbolic Computation, Springer-Verlag, Vienna.
• 11: Walker, R. J. Algebraic Curves. Springer-Verlag, New York, 1978.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE

General Terms:
Algorithms, Theory

Keywords:
CAD, order-invariance, projection