[en] We consider cylindrical algebraic decomposition (CAD) and the key concept of delineability which underpins CAD theory. We introduce the novel concept of projective delineability which is easier to guarantee computationally. We prove results about this which can allow reduced CAD computations.
Disciplines :
Mathematics Computer science
Author, co-author :
Michel, Lucas ; Université de Liège - ULiège > Département de mathématique > Géométrie différentielle
Nalbach, Jasper; RWTH Aachen University, Germany
Mathonet, Pierre ; Université de Liège - ULiège > Département de mathématique > Géométrie différentielle
Zenaïdi, Naïm ; Université de Liège - ULiège > Département de mathématique
Brown, Christopher W.; United States Naval Academy, United States
Abraham, Erika; RWTH Aachen University, Germany
Davenport, James H.; University of Bath, United Kingdom
England, Matthew; Coventry University, United Kingdom
Language :
English
Title :
On Projective Delineability
Publication date :
2024
Event name :
2024 26th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC)
Event place :
Timisoara, Rou
Event date :
16-09-2024 => 19-09-2024
By request :
Yes
Audience :
International
Main work title :
Proceedings - 2024 26th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2024
Publisher :
Institute of Electrical and Electronics Engineers Inc., United States
DFG - Deutsche Forschungsgemeinschaft COST - European Cooperation in Science and Technology F.R.S.-FNRS - Fonds de la Recherche Scientifique
Funding text :
P.~Mathonet, L.~Michel and N.~Zenaïdi are supported by the FNRS-DFG PDR Weaves (SMT-ART) grant 40019202. E.~Ábrahám and J.~Nalbach are supported by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) as part of AB 461/9-1 \emph{SMT-ART}. J.~Nalbach is supported by the DFG as part of RTG 2236 \emph{UnRAVeL}. M.~England and J.~Davenport are supported by the UKRI EPSRC DEWCAD Project (grant EP/T015748/1 and EP/T015713/1 respectively). J.~Davenport is funded by the DFG under Germany's Excellence Strategy (EXC-2047/1 – 390685813). This publication is based upon work from COST Action EuroProofNet, supported by COST (European Cooperation in Science and Technology, www.cost.eu)
E. Ábrahám, J. H. Davenport, M. England, and G. Kremer. Deciding the consistency of non-linear real arithmetic constraints with a conflict driven search using cylindrical algebraic coverings. J. Logical & Algebraic Methods in Prog., 119, 2021.
S. Basu, R. Pollack, and M.F. Coste-Roy. Algorithms in Real Algebraic Geometry. Algorithms and Computation in Mathematics. Springer, 2007.
C. W. Brown. Improved projection for cylindrical algebraic decomposition. J. Symbolic Computation, 32(5):447–465, 2001.
C. W. Brown. Open non-uniform cylindrical algebraic decompositions. In Proc. ISSAC’15, pages 85–92. ACM, 2015.
G. E. Collins. Quantifier elimination for real closed fields by cylindrical algebraic decomposition. In Automata Theory and Formal Languages. Springer, 1975.
D. A. Cox, J. Little, and D. O’Shea. Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra. Springer, 3rd edition, 2010.
W. Fulton. Algebraic Topology: A First Course. Graduate texts in mathematics. World Publishing Corporation, 1995.
I.M. Gelfand, M. Kapranov, and A. Zelevinsky. Discriminants, Resultants, and Multidimensional Determinants. Birkhäuser, 2009.
D. Jovanovic and L. de Moura. Solving non-linear arithmetic. In Proc. IJCAR’12, pages 339–354. Springer, 2012.
S. McCallum. An improved projection operation for cylindrical algebraic decomposition of three-dimensional space. J. Symbolic Computation, 5(1):141–161, 1988.
S. McCallum. An improved projection operation for cylindrical algebraic decomposition. In Bob F. Caviness and Jeremy R. Johnson, editors, Quantifier Elimination and Cylindrical Algebraic Decomposition, pages 242–268. Springer, 1998.
S. McCallum. On projection in CAD-based quantifier elimination with equational constraint. In Proc. ISSAC’99, pages 145–149. ACM, 1999.
J. Nalbach, E. Abraham, P. Specht, C. W. Brown, J. H. Davenport, and M. England. Levelwise construction of a single cylindrical algebraic cell. J. Symbolic Computation, 123, 2024.
