什么是Mathematica的CylindricalDecomposition的计算复杂性 [英] What is the Computational Complexity of Mathematica's CylindricalDecomposition

问题描述

数学<一href="http://reference.wolfram.com/mathematica/ref/CylindricalDecomposition.html">CylindricalDecomposition实现被称为圆柱代数分解算法。沃尔弗拉姆MathWorld对圆柱代数分解文章说，这种算法成为计算不可行复杂的不平等。

可这种说法变得更为precise？具体而言，如何在时间和空间上涉及到的多元多项式变量的程度和数量？难道时间和空间依赖于其它参数？

解决方案

  

塔斯基表明，对于每一个公式，包括量化连接器总有一个相当于量化连接器配方。获得从前者，后者被称为量化连接器消除。 （...）

     

在特别地，对于圆柱形代数分解（CAD），​​操作的数目通常缩放以双倍指数的方式与变量的数目，而较新的方法是在量化音响器的交替的数目双倍指数。

<一个href="http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-972-algebraic-techniques-and-semidefinite-optimization-spring-2006/lecture-notes/lecture_18.pdf"相对=nofollow>参考：MIT 6.972代数技术和semide无限优化的，由Pablo A. Parrilo 的

修改：一个漂亮的MMA的CAD算法 此处

Mathematica' CylindricalDecomposition implements an algorithm known as Cylindrical Algebraic Decomposition. Wolfram MathWorld's article on Cylindrical Algebraic Decomposition says that this algorithm "becomes computationally infeasible for complicated inequalities."

Can this statement be made more precise? Specifically, how does the time and space relate to the degree and number of variables of the multivariate polynomials? Does the time and space depend on other parameters?

解决方案

Tarski showed that for every formula including quantifiers there is always an equivalent quantifier free formula. Obtaining the latter from the former is called quantifier elimination. (...)

In particular, for the cylindrical algebraic decomposition (CAD), the number of operations usually scales in a doubly exponential fashion with the number of variables, while the newer methods are doubly exponential in the number of quantifier alternations.

Reference: MIT 6.972 Algebraic techniques and semidefinite optimization by Pablo A. Parrilo

Edit: A nice article on Mma CAD algorithms here

这篇关于什么是Mathematica的CylindricalDecomposition的计算复杂性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！