An Implementation of Sub-CAD in Maple

Matthew England, David Wilson

Research output: Book/ReportOther report

153 Downloads (Pure)

Abstract

Cylindrical algebraic decomposition (CAD) is an important tool for the investigation of semi-algebraic sets, with applications in algebraic geometry and beyond. We have previously reported on an implementation of CAD in Maple which offers the original projection and lifting algorithm of Collins along with subsequent improvements.

Here we report on new functionality: specifically the ability to build cylindrical algebraic sub-decompositions (sub-CADs) where only certain cells are returned.
We have implemented algorithms to return cells of a prescribed dimensions or higher (layered sub-CADs), and an algorithm to return only those cells on which given polynomials are zero (variety sub-CADs). These offer substantial savings in output size and computation time.

The code described 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 pages11
Publication statusPublished - Mar 2015

Publication series

NameDepartment of Computer Science Technical Report Series
No.CSBU-2015-01
ISSN (Electronic)1740-9497

Fingerprint

Dive into the research topics of 'An Implementation of Sub-CAD in Maple'. Together they form a unique fingerprint.

Cite this