Improved projection for CAD's of R3

ABSTRACT

This paper presents an improved projection operator for the construction of CAD's of R3. It is shown that, typically, it suffices to include in projection only leading coefficients (along with discriminants and resultants) rather than all coefficients. Cases in which the leading coefficient alone does not suffice can be dealt with, in a sense, even more efficiently. Generalizing the improved projection operator to dimension greater than three is a topic of ongoing research.

REFERENCES

• 1: B. Caviness and J. R. Johnson, editors. Quantifier Elimination and Cylindrical Algebraic Decomposition. Texts and Monographs in Symbolic Computation. Springer-Verlag, 1998.
• 2: 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
• 3: G. E. Collins. Quantifier elimination by cylindrical algebraic decomposition - 20 years of progress. In B. Caviness and J. Johnson, editors, Quantifier Elimination and Cylindrical Algebraic Decomposition, Texts and Monographs in Symbolic Computation. Springer-Verlag, 1998.
• 4: George E. Collins , Hoon Hong, Partial cylindrical algebraic decomposition for quantifier elimination, Journal of Symbolic Computation, v.12 n.3, p.299-328, Sept. 1991 [doi>10.1016/S0747-7171(08)80152-6]
• 5: H. Hong, An improvement of the projection operator in cylindrical algebraic decomposition, Proceedings of the international symposium on Symbolic and algebraic computation, p.261-264, August 20-24, 1990, Tokyo, Japan [doi>10.1145/96877.96943]
• 6: Hoon Hong, Simple solution formula construction in cylindrical algebraic decomposition based quantifier elimination, Papers from the international symposium on Symbolic and algebraic computation, p.177-188, July 27-29, 1992, Berkeley, California, United States [doi>10.1145/143242.143306]
• 7: 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]
• 8: S. McCallum. An improved projection operator for cylindrical algebraic decomposition. In B. Caviness and J. Johnson, editors, Quantifier Elimination and Cylindrical Algebraic Decomposition, Texts and Monographs in Symbolic Computation. Springer-Verlag, Vienna, 1998.
• 9: Scott McCallum, On projection in CAD-based quantifier elimination with equational constraint, Proceedings of the 1999 international symposium on Symbolic and algebraic computation, p.145-149, July 28-31, 1999, Vancouver, British Columbia, Canada [doi>10.1145/309831.309892]

INDEX TERMS

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

General Terms:
Performance, Theory, Verification