![Cover Image for System.Linq.Enumerable+EnumerablePartition`1[System.Char]](https://coverimages.igi-global.com/images/search-article.png)
An Implementation of CAD in Maple Utilising McCallum Projection
OAI: oai:purehost.bath.ac.uk:openaire_cris_publications/7ee5353c-4a11-417d-bbd7-5fd32f5b9ed2
Published by: Department of Computer Science, University of Bath
Abstract
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.
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.