On the Complexity of Sparse Elimination
On the Complexity of Sparse Elimination
复制标题
DOI：
10.1006/jcom.1996.0010
复制
发表时间：
1996-06
期刊：
影响因子：
--
通讯作者：
I. Emiris
中科院分区：
文献类型：
--
作者：
I. Emiris
稀疏消去法通过考虑其牛顿多面体而不是其总次数来利用多元多项式的结构。我们专注于生成零维理想的多项式系统。从牛顿多面体的Minkowski和的混合细分定义了坐标环的单项基。我们提供了一个新的简单的证明依赖于一个稀疏的结果矩阵的建设，这导致计算的乘法映射和所有公共零点。单项式基的大小等于混合体积，其计算等价于计算混合体积，因此后者是内在复杂性的度量。另一方面，我们的算法具有与Minkowski和的体积成比例的最坏情况的复杂度。为了得到的稀疏参数的界限，我们建立了新的界限的闵可夫斯基和体积作为混合体积的函数。为此，我们证明了一个下界的混合体积的欧氏体积，这是独立的利益。
Sparse elimination exploits the structure of a multivariate polynomial by considering its Newton polytope instead of its total degree. We concentrate on polynomial systems that generate zero-dimensional ideals. A monomial basis for the coordinate ring is defined from a mixed subdivision of the Minkowski sum of the Newton polytopes. We offer a new simple proof relying on the construction of a sparse resultant matrix, which leads to the computation of a multiplication map and all common zeros. The size of the monomial basis equals the mixed volume and its computation is equivalent to computing the mixed volume, so the latter is a measure of intrinsic complexity. On the other hand, our algorithms have worst-case complexity proportional to the volume of the Minkowski sum. In order to derive bounds in terms of the sparsity parameters, we establish new bounds on the Minkowski sum volume as a function of mixed volume. To this end, we prove a lower bound on mixed volume in terms of Euclidean volume which is of independent interest.