Reproduce “An implementation of CAD in Maple utilising McCallum projection” 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

Matthew England

A new Maple package, PCAD, implements Cylindrical Algebraic Decomposition (CAD) based on Collins' and McCallum's projection-lifting algorithms, providing the first full realization of McCallum's CADW including delineating polynomial handling. This implementation also uniquely offers the option to produce order-invariant CADs for the final decomposition of R^n, addressing limitations in existing CAD software like Qepcad.

Key insights

  • The full implementation of McCallum's delineating polynomials, missing in other tools like Qepcad, is critical for correctly solving problems where polynomials are "well-oriented" but not "very well-oriented".
  • Providing order-invariant CADs for the final R^n decomposition enables new avenues of research that require this stronger property, distinguishing it from standard sign-invariant CADs.
  • Implementing both projection-lifting (PCAD) and `RegularChains` based (TCAD) approaches within Maple offers a valuable platform for direct comparison and deeper understanding of CAD algorithms.

Summary by alphaXiv.

Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.