Cylindrical algebraic decomposition using local projections

DOI10.1016/J.JSC.2015.11.018MaRDI QIDQ5963393zbMATH OpenOpenAlexFDO

Publication date 19 February 2016

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

Full work available at URL https://doi.org/10.1016/j.jsc.2015.11.018

cylindrical algebraic decomposition quantifier elimination semialgebraic sets solving inequalities

Quantifier elimination, model completeness, and related topics (03C10) Computational aspects and applications of commutative rings (13P99) Semialgebraic sets and related spaces (14P10) Computational aspects in algebraic geometry (14Q99) Symbolic computation and algebraic computation (68W30)

Review text

A cylindrical algebraic decomposition of a semialgebraic set is considered. This paper proposes a new algorithm computing the cylindrical algebraic decomposition by a different method from the one given in the classical Cylindrical Algebraic Decomposition (CAD) algorithm. This new approach consists in using projection sets computed for each cell separately. One of the advantages of the Local Projection Cylindrical Algebraic Decomposition (LP CAD) algorithm is that local projection sets can be significantly smaller than the global projection set used by the classical CAD algorithm. Therefore the LP CAD algorithm leads to a reduction on the number of cells the algorithm needs to construct. Experiments suggest that for systems that are not well-oriented LP CAD performs better than CAD. For well oriented-systems LP CAD usually construct less cells than CAD, but this does not necessarily translate to a faster timing, due to overhead from reconstructing projection for every cell. However, for some of the well-oriented systems, LP CAD is significantly faster than CAD. It is due to the ability of LP CAD to exploit the Boolean structure of the problem. Let us recall that every semialgebraic set can be represented as a finite union of disjoint cells bounded by graphs of algebraic functions. The classical Cylindrical Algebraic Decomposition algorithm can be used to compute a cell decomposition of any semialgebraic set presented by a quantified system of polynomial equations and inequalities. The CAD algorithm takes a system of polynomial equations and inequalities and constructs a cell decomposition of its solution set. The algorithm consists of two phases: the projection phase and the lifting phase.The projection phase finds a set of polynomials. The roots of this set of polynomials are sufficient to describe the cell boundaries. The lifting phase constructs a cell decomposition, one dimension at a time, subdividing cells at all roots of the projection polynomials. One may remark that some of these subdivisions may be unnecessary. The LP CAD algorithm presented in the paper combines the two phases.NEWLINENEWLINEThis paper provides various examples and an empirical comparison of this new algorithm and the classical CAD algorithm.

Recommendations

Cites work

Cited in

(28)

Describes a project that uses

Uses Software

QEPCAD

This page was built for publication: Cylindrical algebraic decomposition using local projections

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