An improvement of the projection operator in cylindrical algebraic decomposition

ABSTRACT

The Cylindrical Algebraic Decomposition (CAD) method of Collins [5] decomposes r-dimensional Euclidean space into regions over which a given set of polynomials have constant signs. An important component of the CAD method is the projection operation: given a set A of r-variate polynomials, the projection operation produces a set P of (r - 1)-variate polynomials such that a CAD of r-dimensional space for A can be constructed from a CAD of (r-1)-dimensional space for P. In this paper, we present an improvement to the projection operation. By generalizing a lemma on which the proof of the original projection operation is based, we are able to find another projection operation which produces a smaller number of polynomials. Let m be the number of polynomials contained in A, and let n be a bound for the degree of each polynomial in A in the projection variable. The number of polynomials produced by the original projection operation is dominated by m2n3 whereas the number of polynomials produced by our projection operation is dominated by m2n2.

REFERENCES

• 1: D.S. Arnon, G. E. Collins, and S. McCMlum. Cylindrical algebraic decomposition I: The basic algorithm. Technical Report CSD-427, Computer Science Dept, Purdue U aiversity, 1982.
• 2: 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]
• 3: 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]
• 4: G. E. Collins and R. Loos. The ALDES-SAC2 computer algebra system. Technical report, 1980.
• 5: 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
• 6: George E. Collins and H oon H ong. Partial cad construction in quantifier elimination. Technical Report OSU- CISRC-10/89 TR45, Computer Science Dept, The Ohio State University, 1989. Submitted to Journal of Symbolic Computation.
• 7: James H. Davenport , Joos Heintz, Real quantifier elimination is doubly exponential, Journal of Symbolic Computation, v.5 n.1-2, p.29-35, February/April 1988 [doi>10.1016/S0747-7171(88)80004-X]
• 8: Hoon Hong. An improvement of the projection operator in cylindrical algebraic decomposition. Technical Report OSU-CISRC-12/89 TR55, Computer Science Dept, The Ohio State University, 1989.
• 9: Scott McCallum, An Improved Projection Operation for Cylindrical Algebraic Decomposition, Research Contributions from the European Conference on Computer Algebra-Volume 2, p.277-278, April 01-03, 1985

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on polynomials

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Algebraic algorithms

General Terms:
Algorithms