An implementation of Sub-CAD in Maple
arXiv:1503.06599
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 {\scad}s), and an algorithm to return only those cells on which given polynomials are zero (variety {\scad}s). 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 are freely available online at http://opus.bath.ac.uk/43911/.
9 pages
References in corpus (9)
- Truth Table Invariant Cylindrical Algebraic Decomposition
- Cylindrical Algebraic Decompositions for Boolean Combinations
- Program Verification in the presence of complex numbers, functions with branch cuts etc
- Truth Table Invariant Cylindrical Algebraic Decomposition by Regular Chains
- Using the Regular Chains Library to build cylindrical algebraic decompositions by projecting and lifting
- Problem formulation for truth-table invariant cylindrical algebraic decomposition by incremental triangular decomposition
- An implementation of CAD in Maple utilising problem formulation, equational constraints and truth-table invariance
- An implementation of CAD in Maple utilising McCallum projection
- An Incremental Algorithm for Computing Cylindrical Algebraic Decompositions