Quantifier elimination by cylindrical algebraic decomposition based on regular chains. (July 2016)

• Record Type: Journal Article
• Authors: Chen, Changbo; Moreno Maza, Marc
• Is Part Of: Journal of symbolic computation. Volume 75(2016)
• Page Start: 74
• Page End: 93
• Publication Date: 2016-07
• Subjects: Quantifier elimination -- Cylindrical algebraic decomposition -- Regular chains -- Triangular decomposition; Mathematics -- Data processing -- Periodicals; Numerical analysis -- Data processing -- Periodicals; Automatic programming (Computer science) -- Periodicals; Mathématiques -- Informatique -- Périodiques; Analyse numérique -- Informatique -- Périodiques; Programmation automatique -- Périodiques; Automatic programming (Computer science); Mathematics -- Data processing; Numerical analysis -- Data processing; Periodicals; Electronic journals; 510.285
• DOI: 10.1016/j.jsc.2015.11.008
• Languages: English
• ISSNs: 0747-7171

Abstract

Abstract: A quantifier elimination algorithm by cylindrical algebraic decomposition based on regular chains is presented. The main idea is to refine a complex cylindrical tree until the signs of polynomials appearing in the tree are sufficient to distinguish the true and false cells. We report an implementation of our algorithm in theRegularChains library inMaple and illustrate its effectiveness by examples.