7

Mathematica のCylindricalDecompositionは、Cylindrical Algebraic Decomposition として知られるアルゴリズムを実装しています。Wolfram MathWorld のCylindrical Algebraic Decompositionに関する記事では、このアルゴリズムは「複雑な不等式では計算上実行不可能になる」と述べています。

このステートメントをより正確にすることはできますか? 具体的には、時間と空間は、多変量多項式の変数の次数と数にどのように関係していますか? 時間と空間は他のパラメーターに依存しますか?

4

1 に答える 1

10

Tarski は、量化子を含むすべての式に対して、同等の量化子を含まない式が常に存在することを示しました。前者から後者を求めることを量化子の消去と呼びます。(...)

特に、円筒代数分解 (CAD) の場合、演算の数は通常、変数の数に応じて 2 倍の指数関数でスケーリングされますが、新しい方法では、量化子の変更の数が 2 倍の指数関数になります。

参照: MIT 6.972 Pablo A. Parrilo による代数的手法と半定値最適化

編集：Mma CADアルゴリズムに関する素晴らしい記事はこちら

于 2011-06-20T01:10:12.603 に答える