Using the Regular Chains library to build cylindrical algebraic decompositions by projecting and lifting

DOI10.1007/978-3-662-44199-2_69zbMATH Open1437.14008DBLPconf/icms/EnglandWBD14arXiv1405.6090OpenAlexW126540604WikidataQ59590583 ScholiaQ59590583MaRDI QIDQ2879161FDOQ2879161

Authors: Matthew England, David Wilson, Russell Bradford, James H. Davenport 

Publication date: 8 September 2014

Published in: Mathematical Software – ICMS 2014 (Search for Journal in Brave)

Abstract: Cylindrical algebraic decomposition (CAD) is an important tool, both for quantifier elimination over the reals and a range of other applications. Traditionally, a CAD is built through a process of projection and lifting to move the problem within Euclidean spaces of changing dimension. Recently, an alternative approach which first decomposes complex space using triangular decomposition before refining to real space has been introduced and implemented within the RegularChains Library of Maple. We here describe a freely available package ProjectionCAD which utilises the routines within the RegularChains Library to build CADs by projection and lifting. We detail how the projection and lifting algorithms were modified to allow this, discuss the motivation and survey the functionality of the package.

Full work available at URL: https://arxiv.org/abs/1405.6090

Recommendations

• Cylindrical algebraic decomposition in the RegularChains library
• Cylindrical algebraic decomposition using local projections
• Cylindrical algebraic decomposition using local projections
• Quantifier elimination by cylindrical algebraic decomposition based on regular chains
• Improved projection for cylindrical algebraic decomposition

zbMATH Keywords

RegularChains library

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10) Software, source code, etc. for problems pertaining to algebraic geometry (14-04) Geometric aspects of numerical algebraic geometry (14Q65)

Cited In (10)

• Using machine learning to improve cylindrical algebraic decomposition
• Cylindrical algebraic decomposition with equational constraints
• The complexity of cylindrical algebraic decomposition with respect to polynomial degree
• Identifying the parametric occurrence of multiple steady states for some biological networks
• Truth table invariant cylindrical algebraic decomposition
• Improved Cross-Validation for Classifiers that Make Algorithmic Choices to Minimise Runtime Without Compromising Output Correctness
• A repository for CAD examples
• What does ``without loss of generality mean, and how do we detect it
• Cylindrical algebraic decomposition in the RegularChains library
• Recent advances in real geometric reasoning

Uses Software

• Maple
• RegularChains
• ProjectionCAD

This page was built for publication: Using the Regular Chains library to build cylindrical algebraic decompositions by projecting and lifting

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2879161)