Cylindrical Algebraic Decomposition in the RegularChains Library

Abstract. Cylindrical algebraic decomposition (CAD) is a fundamen-tal tool in computational real algebraic geometry and has been imple-mented in several software. While existing implementations are all based on Collins ’ projection-lifting scheme and its subsequent ameliorations, the implementation of CAD in the RegularChains library is based on triangular decomposition of polynomial systems and real root isolation of regular chains. The function in the RegularChains library for computing CAD is called CylindricalAlgebraicDecompose. In this paper, we illustrate by examples the functionality, the underlying theory and algorithm, as well the implementation techniques of CylindricalAlgebraicDecompose. An application of it is also provided