Optimising problem formulation for cylindrical algebraic decomposition
From MaRDI portal
Abstract: Cylindrical algebraic decomposition (CAD) is an important tool for the study of real algebraic geometry with many applications both within mathematics and elsewhere. It is known to have doubly exponential complexity in the number of variables in the worst case, but the actual computation time can vary greatly. It is possible to offer different formulations for a given problem leading to great differences in tractability. In this paper we suggest a new measure for CAD complexity which takes into account the real geometry of the problem. This leads to new heuristics for choosing: the variable ordering for a CAD problem, a designated equational constraint, and formulations for truth-table invariant CADs (TTICADs). We then consider the possibility of using Groebner bases to precondition TTICAD and when such formulations constitute the creation of a new problem.
Recommendations
- Problem formulation for truth-table invariant cylindrical algebraic decomposition by incremental triangular decomposition
- Choosing a variable ordering for truth-table invariant cylindrical algebraic decomposition by incremental triangular decomposition
- Cylindrical algebraic sub-decompositions
- Cylindrical algebraic decompositions for Boolean combinations
- The complexity of cylindrical algebraic decomposition with respect to polynomial degree
Cited in
(26)- Using machine learning to improve cylindrical algebraic decomposition
- Choosing better variable orderings for cylindrical algebraic decomposition via exploiting chordal structure
- New heuristic to choose a cylindrical algebraic decomposition variable ordering motivated by complexity analysis
- Enhancements to Lazard's method for cylindrical algebraic decomposition
- Identifying the parametric occurrence of multiple steady states for some biological networks
- Cylindrical algebraic decomposition with equational constraints
- Need polynomial systems be doubly-exponential?
- Improving the use of equational constraints in cylindrical algebraic decomposition
- The complexity of cylindrical algebraic decomposition with respect to polynomial degree
- Choosing a variable ordering for truth-table invariant cylindrical algebraic decomposition by incremental triangular decomposition
- Speeding up cylindrical algebraic decomposition by Gröbner bases
- Recent advances in real geometric reasoning
- Simplification of Cylindrical Algebraic Formulas
- Cylindrical algebraic sub-decompositions
- Improved Cross-Validation for Classifiers that Make Algorithmic Choices to Minimise Runtime Without Compromising Output Correctness
- A Machine Learning Based Software Pipeline to Pick the Variable Ordering for Algorithms with Polynomial Inputs
- Problem formulation for truth-table invariant cylindrical algebraic decomposition by incremental triangular decomposition
- Applying machine learning to the problem of choosing a heuristic to select the variable ordering for cylindrical algebraic decomposition
- Improved projection for cylindrical algebraic decomposition
- Truth table invariant cylindrical algebraic decomposition
- Explainable AI insights for symbolic computation: a case study on selecting the variable ordering for cylindrical algebraic decomposition
- Exploring alternative machine learning models for variable ordering in cylindrical algebraic decomposition
- Constrained neural networks for interpretable heuristic creation to optimise computer algebra systems
- Lessons on datasets and paradigms in machine learning for symbolic computation: a case study on CAD
- Choosing the variable ordering for cylindrical algebraic decomposition via exploiting chordal structure
- Optimizing a particular real root of a polynomial by a special cylindrical algebraic decomposition
This page was built for publication: Optimising problem formulation for cylindrical algebraic decomposition
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2843003)
