Efficient projection orders for CAD

ABSTRACT

We introduce an efficient algorithm for determining a suitable projection order for performing cylindrical algebraic decomposition. Our algorithm is motivated by a statistical analysis of comprehensive test set computations. This analysis introduces several measures on both the projection sets and the entire computation, which turn out to be highly correlated. The statistical data also shows that the orders generated by our algorithm are significantly close to optimal.

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 , George E. Collins , Scott McCallum, Cylindrical algebraic decomposition II: an adjacency algorithm for the plane, SIAM Journal on Computing, v.13 n.4, p.878-889, Nov. 1984 [doi>10.1137/0213055]
• 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: 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
• 5: 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]
• 6: D. Cox, J. Little, and D. O'Shea. Ideals, Varieties and Algorithms. Undergraduate Texts in Mathematics. Springer-Verlag, New York, Berlin, Heidelberg, 1992.
• 7: Andreas Dolzmann , Thomas Sturn, REDLOG: computer algebra meets computer logic, ACM SIGSAM Bulletin, v.31 n.2, p.2-9, June 1997 [doi>10.1145/261320.261324]
• 8: 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]
• 9: W. Kahan, Problem #9: an ellipse problem, ACM SIGSAM Bulletin, v.9 n.3, p.11-12, August 1975 [doi>10.1145/1088309.1088312]
• 10: Daniel Lazard, Quantifier elimination: optimal solution for two classical examples, Journal of Symbolic Computation, v.5 n.1-2, p.261-266, February/April 1988 [doi>10.1016/S0747-7171(88)80015-4]
• 11: D. Lazard. An improved projection for cylindrical algebraic decomposition. In C. L. Bajaj, editor, Algebraic Geometry and its Applications: Collections of Papers from Shreeram S. Abhyankar's 60th Birthday Conference. Springer, Berlin, 1994.
• 12: Scott McCallum, An improved projection operation for cylindrical algebraic decomposition (computer algebra, geometry, algorithms), 1984
• 13: S. McCallum. Solving polynomial strict inequalities using cylindrical algebraic decomposition. Technical Report 87-25.0, RISC, Johannes Kepler University, Linz, Austria, 1987.
• 14: 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]
• 15: J. T. Schwartz and M. Sharir. On the piano movers' problem. II. General techniques for computing topological properties of real algebraic manifolds. Advances in Applied Mathematics, 4:298--351, 1983.
• 16: Andreas Seidl , Thomas Sturm, A generic projection operator for partial cylindrical algebraic decomposition, Proceedings of the 2003 international symposium on Symbolic and algebraic computation, p.240-247, August 03-06, 2003, Philadelphia, PA, USA [doi>10.1145/860854.860903]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

General Terms:
Algorithms, Experimentation, Performance, Theory

Keywords:
partial cad, projection operator, redlog