Projects per year
Abstract
Cylindrical algebraic decomposition (CAD) is an important tool for the investigation of semialgebraic sets. Originally introduced by Collins in the 1970s for use in quantifier elimination it has since found numerous applications within algebraic geometry and beyond. Following from his original
work in 1988, McCallum presented an improved algorithm, CADW, which offered a huge increase in the practical utility of CAD.
In 2009 a team based at the University of Western Ontario presented a new and quite separate algorithm for CAD, which was implemented and included in the computer algebra system Maple.
As part of a wider project at Bath investigating CAD and its applications, Collins and McCallum’s CAD algorithms have been implemented in Maple. This report details these implementations and compares them to Qepcad and the Ontario algorithm.
The implementations were originally undertaken to facilitate research into the connections between the algorithms. However, the ability of the code to guarantee orderinvariant output has led to its use in new research on CADs which are minimal for certain problems. In addition, the implementation
described here is of interest as the only full implementation of CADW, (since Qepcad does not currently make use of McCallum’s delineating polynomials), and hence can solve problems not admissible to other CAD implementations.
work in 1988, McCallum presented an improved algorithm, CADW, which offered a huge increase in the practical utility of CAD.
In 2009 a team based at the University of Western Ontario presented a new and quite separate algorithm for CAD, which was implemented and included in the computer algebra system Maple.
As part of a wider project at Bath investigating CAD and its applications, Collins and McCallum’s CAD algorithms have been implemented in Maple. This report details these implementations and compares them to Qepcad and the Ontario algorithm.
The implementations were originally undertaken to facilitate research into the connections between the algorithms. However, the ability of the code to guarantee orderinvariant output has led to its use in new research on CADs which are minimal for certain problems. In addition, the implementation
described here is of interest as the only full implementation of CADW, (since Qepcad does not currently make use of McCallum’s delineating polynomials), and hence can solve problems not admissible to other CAD implementations.
Original language  English 

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

No.  CSBU201302 
ISSN (Print)  17409497 
Bibliographical note
The code and example file were written for the Maple computer algebra system, version 16. Additionally the code may be viewed as a text file. For information on working with the code see the example file and Section 3.1 of the report.Fingerprint
Dive into the research topics of 'An Implementation of CAD in Maple Utilising McCallum Projection'. Together they form a unique fingerprint.Projects
 1 Finished

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