Truth table invariant cylindrical algebraic decomposition by regular chains

DOI10.1007/978-3-319-10515-4_4MaRDI QIDQ2879312zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Changbo Chen, Matthew England, Marc Moreno Maza, Russell Bradford, James H. Davenport, David Wilson

Publication date 8 September 2014

Published in Computer Algebra in Scientific Computing (Search for Journal in Brave)

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

zbMATH Keywords

cylindrical algebraic decompositionequational constraintregular chainstriangular decomposition

Mathematics Subject Classification ID

Real algebraic and real-analytic geometry (14P99) Computational aspects in algebraic geometry (14Q99) Symbolic computation and algebraic computation (68W30)

Abstract: A new algorithm to compute cylindrical algebraic decompositions (CADs) is presented, building on two recent advances. Firstly, the output is truth table invariant (a TTICAD) meaning given formulae have constant truth value on each cell of the decomposition. Secondly, the computation uses regular chains theory to first build a cylindrical decomposition of complex space (CCD) incrementally by polynomial. Significant modification of the regular chains technology was used to achieve the more sophisticated invariance criteria. Experimental results on an implementation in the RegularChains Library for Maple verify that combining these advances gives an algorithm superior to its individual components and competitive with the state of the art.

Recommendations

• Truth table invariant cylindrical algebraic decomposition
• Cylindrical algebraic decompositions for Boolean combinations
• 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
• scientific article; zbMATH DE number 1262462

Cited in

(13)

• Using machine learning to improve cylindrical algebraic decomposition
• Cylindrical algebraic decomposition with equational constraints
• \textsf{SC}\(^2\): satisfiability checking meets symbolic computation. (Project paper)
• Need polynomial systems be doubly-exponential?
• 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
• Cylindrical algebraic decompositions for Boolean combinations
• Recent advances in real geometric reasoning
• Improved Cross-Validation for Classifiers that Make Algorithmic Choices to Minimise Runtime Without Compromising Output Correctness
• Variable ordering selection for cylindrical algebraic decomposition with artificial neural networks
• Problem formulation for truth-table invariant cylindrical algebraic decomposition by incremental triangular decomposition
• Quantifier elimination by cylindrical algebraic decomposition based on regular chains
• Truth table invariant cylindrical algebraic decomposition

Describes a project that uses

Uses Software

• Maple
• QEPCAD
• RegularChains

This page was built for publication: Truth table invariant cylindrical algebraic decomposition by regular chains

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