Andreas Dolzmann
Thomas Sturm
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.
- D. S. Arnon, G. E. Collins, and S. McCallum. Cylindrical algebraic decomposition I: The basic algorithm. SIAM Journal on Computing, 13(4):865--877, Nov. 1984.]] Google Scholar
Digital Library
- D. S. Arnon, G. E. Collins, and S. McCallum. Cylindrical algebraic decomposition II: An adjacency algorithm for the plane. SIAM Journal on Computing, 13(4):878--889, Nov. 1984.]] Google ScholarDigital Library
- C. W. Brown. Improved projection for cylindrical algebraic decomposition. Journal of Symbolic Computation, 32(5):447--465, Nov. 2001.]] Google ScholarDigital Library
- G. E. Collins. Quantifier elimination for the elementary theory of real closed fields by cylindrical algebraic decomposition. In H. Brakhage, editor, Automata Theory and Formal Languages. 2nd GI Conference, volume 33 of Lecture Notes in Computer Science, pages 134--183. Springer-Verlag, Berlin, Heidelberg, New York, 1975.]] Google ScholarDigital Library
- G. E. Collins and H. Hong. Partial cylindrical algebraic decomposition for quantifier elimination. Journal of Symbolic Computation, 12(3):299--328, Sept. 1991.]] Google ScholarDigital Library
- D. Cox, J. Little, and D. O'Shea. Ideals, Varieties and Algorithms. Undergraduate Texts in Mathematics. Springer-Verlag, New York, Berlin, Heidelberg, 1992.]] Google ScholarDigital Library
- A. Dolzmann and T. Sturm. Redlog: Computer algebra meets computer logic. ACM SIGSAM Bulletin, 31(2):2--9, June 1997.]] Google ScholarDigital Library
- H. Hong. An improvement of the projection operator in cylindrical algebraic decomposition. In S. Watanabe and M. Nagata, editors, Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC~90), pages 261--264. ACM Press, New York, Aug. 1990.]] Google ScholarDigital Library
- W. Kahan. An ellipse problem. ACM SIGSAM Bulletin, 9(3):11, Aug. 1975. SIGSAM Problem #9.]] Google ScholarDigital Library
- D. Lazard. Quantifier elimination: Optimal solution for two classical examples. Journal of Symbolic Computation, 5(1 &2):261--266, Feb. 1988.]] Google ScholarDigital Library
- 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.]]Google Scholar
- S. McCallum. An Improved Projection Operation for Cylindrical Algebraic Decomposition. Ph.D. dissertation, Computer Sciences Department, University of Wisconsin, Madison, 1984.]] Google ScholarDigital Library
- S. McCallum. Solving polynomial strict inequalities using cylindrical algebraic decomposition. Technical Report 87-25.0, RISC, Johannes Kepler University, Linz, Austria, 1987.]]Google Scholar
- S. McCallum. An improved projection operation for cylindrical algebraic decomposition of three-dimensional space. Journal of Symbolic Computation, 5(1--2):141--161, Feb.--Apr. 1988.]] Google ScholarDigital Library
- 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.]]Google ScholarDigital Library
- A. Seidl and T. Sturm. A generic projection operator for partial cylindrical algebraic decomposition. In R. Sendra, editor, Proceedings of the 2003 International Symposium on Symbolic and Algebraic Computation (ISSAC 03), Philadelphia, Pennsylvania, pages 240--247. ACM Press, New York, NY, 2003.]] Google ScholarDigital Library
Index Terms
- Efficient projection orders for CAD
Recommendations
A generic projection operator for partial cylindrical algebraic decomposition
ISSAC '03: Proceedings of the 2003 international symposium on Symbolic and algebraic computationThis paper provides a starting point for generic quantifier elimination by partial cylindrical algebraic decomposition pcad. On input of a first-order formula over the reals generic pcad outputs a theory and a quantifier-free formula. The theory is a ...
Lorentzian discriminant projection and its applications
ACCV'09: Proceedings of the 9th Asian conference on Computer Vision - Volume Part IIIThis paper develops a supervised dimensionality reduction method, Lorentzian Discriminant Projection (LDP), for discriminant analysis and classification Our method represents the structures of sample data by a manifold, which is furnished with a ...
Isometric projection
AAAI'07: Proceedings of the 22nd national conference on Artificial intelligence - Volume 1Recently the problem of dimensionality reduction has received a lot of interests in many fields of information processing. We consider the case where data is sampled from a low dimensional manifold which is embedded in high dimensional Euclidean space. ...
Comments