主题
Search

柱形代数分解

DOWNLOAD Mathematica Notebook下载 Wolfram 笔记本

在 R^1 中，将单元格定义为开区间或点。在 R^(k+1) 中的单元格则具有以下两种形式之一，

{(x,y):x in C, and f(x)<y<g(x)}
(1)

或

{(x,y):x in C, and y=f(x)},
(2)

其中 x={x_1,...,x_k}, C 是 R^k 中的单元格，f 和 g 是 (1) 在 C 上的连续函数，使得对于某些多项式 F 和 G, F(x,f(x))=0 和 G(x,g(x))=0, 或 (2) +/-infty, 且对于所有 x in C, f(x)<g(x)。

集合 S subset R^n 的柱形代数分解是将 S 表示为有限个不相交单元格的并集。设 F 为 n 个变量的多项式的有限集合。集合 S subset R^n 的柱形代数分解被称为是 F-不变的，如果来自 F 的每个多项式在分解的每个单元格上都具有恒定的符号。

柱形代数分解 (CAD) 算法，给定 F，即 n 个变量的多项式的有限集合，计算 F-不变的 R^n 的柱形代数分解。给定 n 个实数未知数的多项式方程和不等式的逻辑组合，可以使用 CAD 算法找到其解集的柱形代数分解。例如，以下分解

x^2+y^2+z^2<1
(3)

由下式给出

{-1<x<1; -sqrt(1-x^2)<y<sqrt(1-x^2); -sqrt(1-x^2-y^2)<z<sqrt(1-x^2-y^2).
(4)

命令CylindricalDecomposition[ineqs, {x1, x2, ...}] 在 Wolfram 语言中执行柱形代数分解。虽然该过程是算法性的，但对于复杂的不等式，它在计算上变得不可行。

参见

柱形部分, 通用柱形代数分解, 量词消去, 塔斯基定理

此条目由 Adam Strzebonski 贡献

使用 Wolfram|Alpha 探索

参考文献

Brown, C. W. "Simple CAD Construction and Its Applications." J. Symbolic Comput. 31, 521-547, 2001.Caviness, B. F. and Johnson, J. R. (Eds.). Quantifier Elimination and Cylindrical Algebraic Decomposition. New York: Springer-Verlag, 1998.Collins, G. E. "Quantifier Elimination for the Elementary Theory of Real Closed Fields by Cylindrical Algebraic Decomposition." Lect. Notes Comput. Sci. 33, 134-183, 1975.Collins, G. E. "Quantifier Elimination by Cylindrical Algebraic Decomposition--Twenty Years of Progress." In Quantifier Elimination and Cylindrical Algebraic Decomposition (Ed. B. F. Caviness and J. R. Johnson). New York: Springer-Verlag, pp. 8-23, 1998.Collins, G. E. and Hong, H. "Partial Cylindrical Algebraic Decomposition for Quantifier Elimination." J. Symb. Comput. 12, 299-328, 1991.Dolzmann, A. and Sturm, T. "Simplification of Quantifier-Free Formulae Over Ordered Fields." J. Symb. Comput. 24, 209-231, 1997.Faugere, J. C.; Gianni, P.; Lazard, D.; and Mora, T. "Efficient Computation of Zero-Dimensional Groebner Bases by Change of Ordering." J. Symb. Comput. 16, 329-344, 1993.Hong, H. "An Improvement of the Projection Operator in Cylindrical Algebraic Decomposition." In ISSAC '90: Proceedings of the International Symposium on Symbolic and Algebraic Computation, August 20-24, 1990, Tokyo, Japan (Ed. S. Watanabe and M. Nagata). New York: ACM Press, pp. 261-264, 1990.Loos, R. and Weispfenning, V. "Applying Lattice Quantifier Elimination." Comput. J. 36, 450-461, 1993.McCallum, S. "Solving Polynomial Strict Inequalities Using Cylindrical Algebraic Decomposition." Comput. J. 36, 432-438, 1993.McCallum, S. "An Improved Projection for Cylindrical Algebraic Decomposition of Three Dimensional Space." J. Symb. Comput. 5, 141-161, 1988.McCallum, S. "An Improved Projection for Cylindrical Algebraic Decomposition." In Quantifier Elimination and Cylindrical Algebraic Decomposition (Ed. B. F. Caviness and J. R. Johnson). New York: Springer-Verlag, pp. 242-268, 1998.McCallum, S. and Collins, G. E. "Local Box Adjacency Algorithms for Cylindrical Algebraic Decompositions." J. Symb. Comput. 33, 321-342, 2002.Strzebonski, A. "An Algorithm for Systems of Strong Polynomial Inequalities." Mathematica J. 4, 74-77, 1994.Strzebonski, A. "A Real Polynomial Decision Algorithm Using Arbitrary-Precision Floating Point Arithmetic." Reliable Comput. 5, 337-346, 1999.Strzebonski, A. "Solving Algebraic Inequalities." Mathematica J. 7, 525-541, 2000.Trott, M. "Polynomials in Inequalities." §1.2.3 in The Mathematica GuideBook for Symbolics. New York: Springer-Verlag, pp. 50-78, 2006. http://www.mathematicaguidebooks.org/.

在 Wolfram|Alpha 上被引用

柱形代数分解

请引用为

Strzebonski, Adam. "柱形代数分解。" 来自 MathWorld--Wolfram Web 资源，由 Eric W. Weisstein 创建。 https://mathworld.net.cn/CylindricalAlgebraicDecomposition.html

主题分类