Cylindrical algebraic decomposition using local projections (Q5963393)

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. This paper provides various examples and an empirical comparison of this new algorithm and the classical CAD algorithm.