An Implementation of CAD in Maple Utilising McCallum Projection

M. England

Research output: Book/ReportOther report

263 Downloads (Pure)


Cylindrical algebraic decomposition (CAD) is an important tool for the investigation of semi-algebraic 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 order-invariant 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 languageEnglish
Place of PublicationBath, U. K.
PublisherDepartment of Computer Science, University of Bath
Number of pages11
Publication statusPublished - Jan 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 McCallum Projection'. Together they form a unique fingerprint.

Cite this