Back to Search
Start Over
Cylindrical Algebraic Sub-Decompositions
- Source :
- Mathematics in Computer Science: Volume 8, Issue 2, pages 263-288, Springer, 2014
- Publication Year :
- 2014
-
Abstract
- Cylindrical algebraic decompositions (CADs) are a key tool in real algebraic geometry, used primarily for eliminating quantifiers over the reals and studying semi-algebraic sets. In this paper we introduce cylindrical algebraic sub-decompositions (sub-CADs), which are subsets of CADs containing all the information needed to specify a solution for a given problem. We define two new types of sub-CAD: variety sub-CADs which are those cells in a CAD lying on a designated variety; and layered sub-CADs which have only those cells of dimension higher than a specified value. We present algorithms to produce these and describe how the two approaches may be combined with each other and the recent theory of truth-table invariant CAD. We give a complexity analysis showing that these techniques can offer substantial theoretical savings, which is supported by experimentation using an implementation in Maple.<br />Comment: 26 pages
Details
- Database :
- arXiv
- Journal :
- Mathematics in Computer Science: Volume 8, Issue 2, pages 263-288, Springer, 2014
- Publication Type :
- Report
- Accession number :
- edsarx.1401.0647
- Document Type :
- Working Paper
- Full Text :
- https://doi.org/10.1007/s11786-014-0191-z