Projects per year
Abstract
Cylindrical algebraic decomposition (CAD) is an important tool for the investigation of semialgebraic sets, with applications within algebraic geometry and beyond. We recently reported on a new implementation of CAD in Maple which implemented the original algorithm of Collins and the subsequent improvement to projection by McCallum. Our implementation was in contrast to Maple’s inbuilt CAD command, based on a quite separate theory. Although initially developed as an investigative tool to compare the algorithms, we found and reported that our code offered functionality not currently available in any other existing implementations.
One particularly important piece of functionality is the ability to produce orderinvariant CADs. This has allowed us to extend the implementation to produce CADs invariant with respect to either equational constraints (ECCADs) or the truthtables of sequences of formulae (TTICADs). This new functionality is contained in the second release of our code, along with commands to consider problem formulation which can be a major factor in the tractability of a CAD.
In the report we describe the new functionality and some theoretical discoveries it prompted. We describe how the CADs produced using equational constraints are able to take advantage of not just improved projection but also improvements in the lifting phase. We also present an extension to the original TTICAD algorithm which increases both the applicability of TTICAD and its relative benefit over other algorithms. The code and an introductory Maple worksheet / pdf demonstrating the full functionality of the package should accompany this report.
One particularly important piece of functionality is the ability to produce orderinvariant CADs. This has allowed us to extend the implementation to produce CADs invariant with respect to either equational constraints (ECCADs) or the truthtables of sequences of formulae (TTICADs). This new functionality is contained in the second release of our code, along with commands to consider problem formulation which can be a major factor in the tractability of a CAD.
In the report we describe the new functionality and some theoretical discoveries it prompted. We describe how the CADs produced using equational constraints are able to take advantage of not just improved projection but also improvements in the lifting phase. We also present an extension to the original TTICAD algorithm which increases both the applicability of TTICAD and its relative benefit over other algorithms. The code and an introductory Maple worksheet / pdf demonstrating the full functionality of the package should accompany this report.
Original language  English 

Place of Publication  Bath, U. K. 
Publisher  Department of Computer Science, University of Bath 
Number of pages  14 
Publication status  Published  May 2013 
Publication series
Name  Department of Computer Science Technical Report Series 

No.  CSBU201304 
ISSN (Print)  17409497 
Fingerprint Dive into the research topics of 'An Implementation of CAD in Maple Utilising Problem Formulation, Equational Constraints and TruthTable Invariance'. 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