Cylindrical algebraic decomposition using local projections.

*(English)*Zbl 1350.14042A 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.

This paper provides various examples and an empirical comparison of this new algorithm and the classical CAD algorithm.

Reviewer: Noémie Combe (Marseille)

##### MSC:

14P10 | Semialgebraic sets and related spaces |

68W30 | Symbolic computation and algebraic computation |

03C10 | Quantifier elimination, model completeness, and related topics |

14Q99 | Computational aspects in algebraic geometry |

13P99 | Computational aspects and applications of commutative rings |

##### Keywords:

semialgebraic sets; cylindrical algebraic decomposition; solving inequalities; quantifier elimination##### Software:

QEPCAD
Full Text:
DOI

##### References:

[1] | Basu, S.; Pollack, R.; Roy, M., Algorithms in real algebraic geometry, vol. 10, (2006), Springer-Verlag, New York, Inc |

[2] | Brown, C. W., Improved projection for cylindrical algebraic decomposition, J. Symb. Comput., 32, 447-465, (2001) · Zbl 0981.68186 |

[3] | Brown, C. W., Qepcad b - a program for computing with semi-algebraic sets using cads, ACM SIGSAM Bull., 37, 97-108, (2003) · Zbl 1083.68148 |

[4] | Brown, C. W., Constructing a single open cell in a cylindrical algebraic decomposition, (Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC 2013, (2013), ACM), 133-140 · Zbl 1360.68924 |

[5] | (Caviness, B.; Johnson, J., Quantifier Elimination and Cylindrical Algebraic Decomposition, (1998), Springer Verlag New York) · Zbl 0906.03033 |

[6] | Chen, C.; Maza, M. M.; Xia, B.; Yang, L., Computing cylindrical algebraic decomposition via triangular decomposition, (Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC 2009, (2009), ACM), 95-102 · Zbl 1237.14068 |

[7] | Collins, G. E., Quantifier elimination for the elementary theory of real closed fields by cylindrical algebraic decomposition, Lect. Notes Comput. Sci., 33, 134-183, (1975) |

[8] | Dolzmann, A.; Sturm, T.; Weispfenning, V., Real quantifier elimination in practice, (Algorithmic Algebra and Number Theory, (1998), Springer), 221-247 · Zbl 0934.68130 |

[9] | Grigoriev, D.; Vorobjov, N., Solving systems of polynomial inequalities in subexponential time, J. Symb. Comput., 5, 1/2, 37-64, (1988) · Zbl 0662.12001 |

[10] | Hong, H., An improvement of the projection operator in cylindrical algebraic decomposition, (Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC 1990, (1990), ACM), 261-264 |

[11] | Hong, H.; Din, M. S.E., Variant quantifier elimination, J. Symb. Comput., 47, 883-901, (2012) · Zbl 1238.14001 |

[12] | Jirstrand, M., Nonlinear control system design by quantifier elimination, J. Symb. Comput., 24, 137-152, (1997) · Zbl 0882.93022 |

[13] | Jovanovic, D.; de Moura, L. M., Solving non-linear arithmetic, (IJCAR, (2012)), 339-354 · Zbl 1358.68257 |

[14] | Łojasiewicz, S., Ensembles semi-analytiques, (1964), I.H.E.S |

[15] | Loos, R.; Weispfenning, V., Applying linear quantifier elimination, Comput. J., 36, 5, 450-462, (1993) · Zbl 0787.03021 |

[16] | McCallum, S., An improved projection for cylindrical algebraic decomposition of three dimensional space, J. Symb. Comput., 5, 141-161, (1988) · Zbl 0648.68054 |

[17] | McCallum, S., An improved projection for cylindrical algebraic decomposition, (Caviness, B.; Johnson, J., Quantifier Elimination and Cylindrical Algebraic Decomposition, (1998), Springer Verlag), 242-268 · Zbl 0900.68279 |

[18] | McCallum, S., On projection in cad-based quantifier elimination with equational constraint, (Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC 1999, (1999), ACM), 145-149 |

[19] | McCallum, S., On propagation of equational constraints in cad-based quantifier elimination, (Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC 2001, (2001), ACM), 223-230 · Zbl 1356.68287 |

[20] | Renegar, J., On the computational complexity and geometry of the first order theory of the reals, J. Symb. Comput., 13, 255-352, (1992) · Zbl 0798.68073 |

[21] | Strzeboński, A., Computing in the field of complex algebraic numbers, J. Symb. Comput., 24, 647-656, (1997) · Zbl 0910.65029 |

[22] | Strzeboński, A., Solving systems of strict polynomial inequalities, J. Symb. Comput., 29, 471-480, (2000) · Zbl 0962.68183 |

[23] | Strzeboński, A., Cylindrical algebraic decomposition using validated numerics, J. Symb. Comput., 41, 1021-1038, (2006) · Zbl 1124.68123 |

[24] | Strzeboński, A., Computation with semialgebraic sets represented by cylindrical algebraic formulas, (Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC 2010, (2010), ACM), 61-68 · Zbl 1321.68543 |

[25] | Strzeboński, A., Solving polynomial systems over semialgebraic sets represented by cylindrical algebraic formulas, (Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC 2012, (2012), ACM), 335-342 · Zbl 1308.68191 |

[26] | Strzeboński, A., Cylindrical algebraic decomposition using local projections, (Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC 2014, (2014), ACM), 389-396 · Zbl 1325.68302 |

[27] | Tarski, A., A decision method for elementary algebra and geometry, (1951), University of California Press · Zbl 0044.25102 |

[28] | Weispfenning, V., Quantifier elimination for real algebra - the quadratic case and beyond, Appl. Algebra Eng. Commun. Comput., 8, 85-101, (1993) · Zbl 0867.03003 |

[29] | Wilson, D., Real geometry and connectedness via triangular description: CAD example bank, (2012) |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.