An Implementation of CAD in Maple Utilising Problem Formulation, Equational Constraints and Truth-Table Invariance

M. England

Research output: Book/ReportOther report

238 Downloads (Pure)


Cylindrical algebraic decomposition (CAD) is an important tool for the investigation of semi-algebraic 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 in-built 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 order-invariant CADs. This has allowed us to extend the implementation to produce CADs invariant with respect to either equational constraints (ECCADs) or the truth-tables 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 languageEnglish
Place of PublicationBath, U. K.
PublisherDepartment of Computer Science, University of Bath
Number of pages14
Publication statusPublished - May 2013

Publication series

NameDepartment of Computer Science Technical Report Series
ISSN (Print)1740-9497


Dive into the research topics of 'An Implementation of CAD in Maple Utilising Problem Formulation, Equational Constraints and Truth-Table Invariance'. Together they form a unique fingerprint.

Cite this