Choosing a variable ordering for truth-table invariant cylindrical algebraic decomposition by incremental triangular decomposition

DOI10.1007/978-3-662-44199-2_68MaRDI QIDQ2879160zbMATH OpenOpenAlexDBLPWikidataFDO

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

Publication date 8 September 2014

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

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

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Symbolic computation and algebraic computation (68W30) Computational aspects in algebraic geometry (14Q99) Real algebraic and real-analytic geometry (14P99)

Abstract: Cylindrical algebraic decomposition (CAD) is a key tool for solving problems in real algebraic geometry and beyond. In recent years a new approach has been developed, where regular chains technology is used to first build a decomposition in complex space. We consider the latest variant of this which builds the complex decomposition incrementally by polynomial and produces CADs on whose cells a sequence of formulae are truth-invariant. Like all CAD algorithms the user must provide a variable ordering which can have a profound impact on the tractability of a problem. We evaluate existing heuristics to help with the choice for this algorithm, suggest improvements and then derive a new heuristic more closely aligned with the mechanics of the new algorithm.

Recommendations

• Problem formulation for truth-table invariant cylindrical algebraic decomposition by incremental triangular decomposition
• New heuristic to choose a cylindrical algebraic decomposition variable ordering motivated by complexity analysis
• Optimising problem formulation for cylindrical algebraic decomposition
• Truth table invariant cylindrical algebraic decomposition by regular chains
• scientific article; zbMATH DE number 7339173

Cited in

(15)

• Recent advances in real geometric reasoning
• Variable ordering selection for cylindrical algebraic decomposition with artificial neural networks
• New heuristic to choose a cylindrical algebraic decomposition variable ordering motivated by complexity analysis
• Using machine learning to improve cylindrical algebraic decomposition
• Truth table invariant cylindrical algebraic decomposition by regular chains
• Applying machine learning to the problem of choosing a heuristic to select the variable ordering for cylindrical algebraic decomposition
• Problem formulation for truth-table invariant cylindrical algebraic decomposition by incremental triangular decomposition
• A Machine Learning Based Software Pipeline to Pick the Variable Ordering for Algorithms with Polynomial Inputs
• scientific article; zbMATH DE number 7339173 (Why is no real title available?)
• Properness defects and projections and computation of at least one point in each connected component of a real algebraic set
• Fully incremental cylindrical algebraic decomposition
• scientific article; zbMATH DE number 2151199 (Why is no real title available?)
• Truth table invariant cylindrical algebraic decomposition
• Improved Cross-Validation for Classifiers that Make Algorithmic Choices to Minimise Runtime Without Compromising Output Correctness
• Optimising problem formulation for cylindrical algebraic decomposition

This page was built for publication: Choosing a variable ordering for truth-table invariant cylindrical algebraic decomposition by incremental triangular decomposition

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