Adam Strzeboński
ABSTRACT
We present an algorithm which computes a cylindrical algebraic decomposition of a semialgebraic set using projection sets computed for each cell separately. Such local projection sets can be significantly smaller than the global projection set used by the Cylindrical Algebraic Decomposition (CAD) algorithm. This leads to reduction in the number of cells the algorithm needs to construct. We give an empirical comparison of our algorithm and the classical CAD algorithm.
- S. Basu, R. Pollack, and M. Roy. Algorithms in real algebraic geometry, volume 10. Springer-Verlag New York Inc., 2006. Google Scholar
Digital Library
- C. W. Brown. Improved projection for cylindrical algebraic decomposition. J. Symbolic Comp., 32:447--465, 2001. Google ScholarDigital Library
- C. W. Brown. Qepcad b - a program for computing with semi-algebraic sets using cads. ACM SIGSAM Bulletin, 37:97--108, 2003. Google ScholarDigital Library
- C. W. Brown. Constructing a single open cell in a cylindrical algebraic decomposition. In Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC 2013, pages 133--140. ACM, 2013. Google ScholarDigital Library
- B. Caviness and J. Johnson, editors. Quantifier Elimination and Cylindrical Algebraic Decomposition, New York, 1998. Springer Verlag.Google ScholarCross Ref
- C. Chen, M. M. Maza, B. Xia, and L. Yang. Computing cylindrical algebraic decomposition via triangular decomposition. In Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC 2009, pages 95--102. ACM, 2009. Google ScholarDigital Library
- G. E. Collins. Quantifier elimination for the elementary theory of real closed fields by cylindrical algebraic decomposition. Lect. Notes Comput. Sci., 33:134--183, 1975. Google ScholarDigital Library
- G. E. Collins and H. Hong. Partial cylindrical algebraic decomposition for quantifier elimination. J. Symbolic Comp., 12:299--328, 1991. Google ScholarDigital Library
- A. Dolzmann, T. Sturm, and V. Weispfenning. Real quantifier elimination in practice. In Algorithmic Algebra and Number Theory, pages 221--247. Springer, 1998.Google Scholar
- D. Grigoriev and N. Vorobjov. Solving systems of polynomial inequalities in subexponential time. J. Symb. Comput., 5(1/2):37--64, 1988. Google ScholarDigital Library
- H. Hong. An improvement of the projection operator in cylindrical algebraic decomposition. In Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC 1990, pages 261--264. ACM, 1990. Google ScholarDigital Library
- H. Hong and M. S. E. Din. Variant quantifier elimination. J. Symb. Comput., 47:883--901, 2012. Google ScholarDigital Library
- D. Jovanovic and L. M. de Moura. Solving non-linear arithmetic. In IJCAR, pages 339--354, 2012. Google ScholarDigital Library
- S. Łojasiewicz. Ensembles semi-analytiques. I.H.E.S., 1964.Google Scholar
- R. Loos and V. Weispfenning. Applying linear quantifier elimination. The Computer Journal, 36(5):450--462, 1993.Google Scholar
- S. McCallum. An improved projection for cylindrical algebraic decomposition of three dimensional space. J. Symbolic Comp., 5:141--161, 1988. Google ScholarDigital Library
- S. McCallum. An improved projection for cylindrical algebraic decomposition. In B. Caviness and J. Johnson, editors, Quantifier Elimination and Cylindrical Algebraic Decomposition, pages 242--268. Springer Verlag, 1998.Google ScholarCross Ref
- J. Renegar. On the computational complexity and geometry of the first order theory of the reals. J. Symbolic Comp., 13:255--352, 1992.Google ScholarDigital Library
- A. Strzeboński. Computing in the field of complex algebraic numbers. J. Symbolic Comp., 24:647--656, 1997. Google ScholarDigital Library
- A. Strzeboński. Solving systems of strict polynomial inequalities. J. Symbolic Comp., 29:471--480, 2000. Google ScholarDigital Library
- A. Strzeboński. Cylindrical algebraic decomposition using validated numerics. J. Symbolic Comp., 41:1021--1038, 2006.Google ScholarCross Ref
- A. Strzeboński. Computation with semialgebraic sets represented by cylindrical algebraic formulas. In Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC 2010, pages 61--68. ACM, 2010. Google ScholarDigital Library
- A. Strzeboński. Solving polynomial systems over semialgebraic sets represented by cylindrical algebraic formulas. In Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC 2012, pages 335--342. ACM, 2012. Google ScholarDigital Library
- A. Strzeboński. Cylindrical Algebraic Decomposition Using Local Projections. arXiv:1405.4925, 2014.Google Scholar
- A. Tarski. A decision method for elementary algebra and geometry. University of California Press, 1951.Google Scholar
- V. Weispfenning. Quantifier elimination for real algebra - the quadratic case and beyond. AAECC, 8:85--101, 1993.Google ScholarCross Ref
- D. Wilson. Real geometry and connectedness via triangular description: Cad example bank, 2012. http://opus.bath.ac.uk/29503/.Google Scholar
Index Terms
- Cylindrical algebraic decomposition using local projections
Recommendations
Quantifier elimination by cylindrical algebraic decomposition based on regular chains
ISSAC '14: Proceedings of the 39th International Symposium on Symbolic and Algebraic ComputationA quantifier elimination algorithm by cylindrical algebraic decomposition based on regular chains is presented. The main idea is to refine a complex cylindrical tree until the signs of polynomials appearing in the tree are sufficient to distinguish the ...
Cylindrical algebraic decomposition using local projections
We present an algorithm which computes a cylindrical algebraic decomposition of a semialgebraic set using projection sets computed for each cell separately. Such local projection sets can be significantly smaller than the global projection set used by ...
Computation with semialgebraic sets represented by cylindrical algebraic formulas
ISSAC '10: Proceedings of the 2010 International Symposium on Symbolic and Algebraic ComputationCylindrical algebraic formulas are an explicit representation of semialgebraic sets as finite unions of cylindrically arranged disjoint cells bounded by graphs of algebraic functions. We present a version of the Cylindrical Algebraic Decomposition (CAD) ...
Comments