Reproduce “New heuristic to choose a cylindrical algebraic decomposition variable ordering motivated by complexity analysis” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Tereso del Río, Matthew England
Researchers at Coventry University developed `gmods`, a new computationally inexpensive heuristic for Cylindrical Algebraic Decomposition (CAD) variable ordering, achieving performance on average 17% slower than the optimal choice, outperforming previous human-designed heuristics. Their `mods` heuristic also demonstrated superior predictive power, exhibiting performance 13% slower than optimal when its own computational cost was not considered.
Key insights
- Theoretical complexity analyses of CAD can effectively inspire practical, efficient algorithmic heuristics, as demonstrated by the improved performance of `mods` and `gmods`.
- A greedy, localized decision-making approach (like `gmods`) can be more practically effective than comprehensive, expensive pre-computation when the total computational cost (including heuristic execution) is considered.
- The failure of `logmods` suggests that polynomials found in SMT-LIB benchmarks do not conform to simple models of random polynomials regarding the distribution of real roots.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.