Using the Regular Chains Library to Build Cylindrical Algebraic Decompositions by Projecting and Lifting

Abstract. Cylindrical algebraic decomposition (CAD) is an important tool, both for quantifier elimination over the reals and a range of other applications. Traditionally, a CAD is built through a process of projec-tion and lifting to move the problem within Euclidean spaces of changing dimension. Recently, an alternative approach which first decomposes com-plex space using triangular decomposition before refining to real space has been introduced and implemented within theRegularChains Library of Maple. We here describe a freely available package ProjectionCAD which utilises the routines within the RegularChains Library to build CADs by projection and lifting. We detail how the projection and lifting algo-rithms were modified to allow this, discuss the motivation and survey the functionality of the package.