Projects per year
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.
| 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. | CSBU-2013-02 |
| ISSN (Print) | 1740-9497 |
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