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

DOI10.1007/978-3-662-44199-2_68zbMATH Open1350.68294DBLPconf/icms/EnglandBDW14arXiv1405.6094OpenAlexW1560494575WikidataQ59590577 ScholiaQ59590577MaRDI QIDQ2879160FDOQ2879160

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)

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.

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

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

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)

Cited In (15)

• 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
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• 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
• Variable ordering selection for cylindrical algebraic decomposition with artificial neural networks
• Recent advances in real geometric reasoning

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)