An incremental algorithm for computing cylindrical algebraic decompositions
From MaRDI portal
Abstract: In this paper, we propose an incremental algorithm for computing cylindrical algebraic decompositions. The algorithm consists of two parts: computing a complex cylindrical tree and refining this complex tree into a cylindrical tree in real space. The incrementality comes from the first part of the algorithm, where a complex cylindrical tree is constructed by refining a previous complex cylindrical tree with a polynomial constraint. We have implemented our algorithm in Maple. The experimentation shows that the proposed algorithm outperforms existing ones for many examples taken from the literature.
Recommendations
- Cylindrical algebraic decomposition using local projections
- Constructing a single cell in cylindrical algebraic decomposition
- Cylindrical algebraic decomposition using local projections
- Computing cylindrical algebraic decomposition via triangular decomposition
- Fully incremental cylindrical algebraic decomposition
Cites work
- scientific article; zbMATH DE number 517393 (Why is no real title available?)
- An improved projection operation for cylindrical algebraic decomposition of three-dimensional space
- Computing triangular systems and regular systems
- Cylindrical algebraic decomposition using validated numerics
- Decomposing polynomial systems into simple systems
- Improved projection for cylindrical algebraic decomposition
- Interval arithmetic in cylindrical algebraic decomposition
- Optimizations of the subresultant algorithm
- Partial cylindrical algebraic decomposition for quantifier elimination
- QEPCAD B
- Solving Polynomial Strict Inequalities Using Cylindrical Algebraic Decomposition
- Solving systems of strict polynomial inequalities
Cited in
(23)- Recent advances in real geometric reasoning
- Variable ordering selection for cylindrical algebraic decomposition with artificial neural networks
- Quantifier elimination by cylindrical algebraic decomposition based on regular chains
- Adapting real quantifier elimination methods for conflict set computation
- New heuristic to choose a cylindrical algebraic decomposition variable ordering motivated by complexity analysis
- Using machine learning to improve cylindrical algebraic decomposition
- Enhancements to Lazard's method for cylindrical algebraic decomposition
- An adjacency algorithm for cylindrical algebraic decompositions of three- dimensional space
- Problem formulation for truth-table invariant cylindrical algebraic decomposition by incremental triangular decomposition
- Chordality preserving incremental triangular decomposition and its implementation
- Computing with Tarski formulas and semi-algebraic sets in a web browser
- Fully incremental cylindrical algebraic decomposition
- Local box adjacency algorithms for cylindrical algebraic decompositions
- Improved projection for cylindrical algebraic decomposition
- A geometric approach to cylindrical algebraic decomposition
- Interval arithmetic in cylindrical algebraic decomposition
- Cylindrical algebraic sub-decompositions
- scientific article; zbMATH DE number 1157654 (Why is no real title available?)
- Improved Cross-Validation for Classifiers that Make Algorithmic Choices to Minimise Runtime Without Compromising Output Correctness
- A Modular Algorithm for Computing the Intersection of a One-Dimensional Quasi-Component and a Hypersurface
- A dataset for suggesting variable orderings for cylindrical algebraic decompositions
- What does ``without loss of generality mean, and how do we detect it
- scientific article; zbMATH DE number 3921970 (Why is no real title available?)
This page was built for publication: An incremental algorithm for computing cylindrical algebraic decompositions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2799562)
