Choosing better variable orderings for cylindrical algebraic decomposition via exploiting chordal structure

DOI10.1016/j.jsc.2022.10.009OpenAlexW4307046631MaRDI QIDQ2100061

Huiying Zhang, Haokun Li, Bican Xia, Tao Zheng

Publication date: 21 November 2022

Published in: Journal of Symbolic Computation (Search for Journal in Brave)

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

zbMATH Keywords

polynomialcylindrical algebraic decompositionchordalityvariable ordering

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Computational aspects and applications of commutative rings (13Pxx) Algebraic geometry (14-XX)

Uses Software

• QEPCAD
• DISCOVERER
• Chordal

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Variant quantifier elimination
• Proving inequalities and solving global optimization problems via simplified CAD projection
• A complete algorithm for automated discovering of a class of inequality-type theorems
• An improved projection operation for cylindrical algebraic decomposition of three-dimensional space
• Partial cylindrical algebraic decomposition for quantifier elimination
• Open weak CAD and its applications
• Maximum cardinality search for computing minimal triangulations of graphs
• Chordal graphs in triangular decomposition in top-down style
• Comparing machine learning models to choose the variable ordering for cylindrical algebraic decomposition
• Cylindrical algebraic decomposition using validated numerics
• Exploiting Chordal Structure in Polynomial Ideals: A Gröbner Bases Approach
• Open Non-uniform Cylindrical Algebraic Decompositions
• Optimising Problem Formulation for Cylindrical Algebraic Decomposition
• Computing cylindrical algebraic decomposition via triangular decomposition
• The Use of Linear Graphs in Gauss Elimination
• Efficient projection orders for CAD
• On the Chordality of Simple Decomposition in Top-Down Style
• Chordality Preserving Incremental Triangular Decomposition and Its Implementation
• Variable Ordering Selection for Cylindrical Algebraic Decomposition with Artificial Neural Networks
• Chordal Networks of Polynomial Ideals
• Sums of Squares and Semidefinite Program Relaxations for Polynomial Optimization Problems with Structured Sparsity
• 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
• Cylindrical algebraic decomposition using local projections

This page was built for publication: Choosing better variable orderings for cylindrical algebraic decomposition via exploiting chordal structure