An effective implementation of symbolic-numeric cylindrical algebraic decomposition for quantifier elimination

作者：Iwane Hidenao^*; Yanami Hitoshi; Anai Hirokazu; Yokoyama Kazuhiro

来源：Theoretical Computer Science, 2013, 479: 43-69.

DOI：10.1016/j.tcs.2012.10.020

• Quantifier elimination
• Cylindrical algebraic decomposition
• Symbolic-numeric computation

With many applications in engineering and scientific fields, quantifier elimination (QE) has received increasing attention. Cylindrical algebraic decomposition (CAD) is used as a basis for a general QE algorithm. In this paper we present an effective symbolic-numeric cylindrical algebraic decomposition (SNCAD) algorithm for QE incorporating several new devices, which we call %26quot;quick tests%26quot;. The simple quick tests are run beforehand to detect an unnecessary procedure that might be skipped without violating the correctness of results and they thus considerably reduce the computing time. The effectiveness of the SNCAD algorithm is examined in a number of experiments including practical engineering problems, which also reveal the quality of the implementation. Experimental results show that our implementation has significantly improved efficiency compared with our previous work.

• 出版日期2013-4-1