A New Algorithm to Find a Point in Every Cell Defined by a Family of Polynomials
A New Algorithm to Find a Point in Every Cell Defined by a Family of Polynomials
复制标题
一种在多项式族定义的每个单元中查找点的新算法
DOI：
10.1007/978-3-7091-9459-1_17
复制
发表时间：
1998
期刊：
影响因子：
--
通讯作者：
Marie
中科院分区：
文献类型：
--
作者：
S. Basu;R. Pollack;Marie
我们考虑包含在真实的闭域R中的有序区域A中的系数为k < s的s个多项式P1，...，Ps，每个多项式的次数至多为d.本文提出了一个新的算法，该算法计算环P1，.，Ps上每个非空符号条件的每个连通分支中的一个点.输出是点的集合以及每个点的符号条件。该算法在A中使用s（s/k）kdO（k）次算术运算。该算法在输出大小可以达到s（O（sd/k））k的意义上几乎是最优的。
We consider s polynomials P1,…,P s in k < s variables with coefficients in an ordered domain A contained in a real closed field R, each of degree at most d. We present a new algorithm which computes a point in each connected component of each non-empty sign condition over P1,…,P s . The output is the set of points together with the sign condition at each point. The algorithm uses s(s/k) k d O (k) arithmetic operations in A. The algorithm is nearly optimal in the sense that the size of the output can be as large as s(O(sd/k)) k .