Projects per year
Abstract
Cylindrical algebraic decomposition (CAD) is an important tool for the study of real algebraic geometry with many applications both within mathematics and elsewhere. It is known to have doubly exponential complexity in the number of variables in the worst case, but the actual computation time can vary greatly. It is possible to offer different formulations for a given problem leading to great differences in tractability. In this paper we suggest a new measure for CAD complexity which takes into account the real geometry of the problem. This leads to new heuristics for choosing the variable ordering for a CAD problem, choosing a designated equational constraint and choosing clause formulation for truthtable invariant CADs (TTICADs). We then consider the possibility of using Groebner bases to precondition TTICAD and when such formulations constitute the creation of a new problem.
Original language  English 

Title of host publication  Intelligent Computer Mathematics 
Subtitle of host publication  MKM, Calculemus, DML, and Systems and Projects 2013, Held as Part of CICM 2013, Bath, UK, July 812, 2013. Proceedings 
Editors  Jacques Carette, David Aspinall, Christoph Lange, Petr Sojka, Wolfgang Windsteiger 
Place of Publication  Berlin 
Publisher  Springer 
Pages  1934 
Number of pages  15 
ISBN (Electronic)  9783642393204 
ISBN (Print)  9783642393198 
DOIs  
Publication status  Published  2013 
Event  Conferences on Intelligent Computer Mathematics: CICM 2013  Bath, UK United Kingdom Duration: 7 Jul 2013 → 11 Jul 2013 
Publication series
Name  Lecture Notes in Computer Science 

Publisher  Springer 
Volume  7961 
ISSN (Print)  03029743 
Conference
Conference  Conferences on Intelligent Computer Mathematics: CICM 2013 

Country/Territory  UK United Kingdom 
City  Bath 
Period  7/07/13 → 11/07/13 
Keywords
 cylindrical algebraic decomposition
 Groebner bases
 problem formulation
 symbolic computation
 equational constraint
Fingerprint
Dive into the research topics of 'Optimising problem formulation for cylindrical algebraic decomposition'. Together they form a unique fingerprint.Projects
 1 Finished

Real Geometry and Connectedness via Triangular Description
Davenport, J., Bradford, R., England, M. & Wilson, D.
Engineering and Physical Sciences Research Council
1/10/11 → 31/12/15
Project: Research council