E cient incremental algorithms for the sparse resultant and the mixed volume
E cient incremental algorithms for the sparse resultant and the mixed volume
复制标题
稀疏结果和混合体积的高效增量算法
DOI：
--
复制
发表时间：
1995
期刊：
影响因子：
--
通讯作者：
zProjet Safir
中科院分区：
文献类型：
--
作者：
Ioannis Z. EMIRISzAND;John F. CANNYx;zProjet Safir
本文提出了一种新的计算n+1个多项式方程组的稀疏结式的有效算法。该算法产生一个矩阵，其元素是给定多项式的系数，并且通常小于通过先前方法获得的矩阵。矩阵行列式是稀疏结式的非平凡倍数，从中可以恢复稀疏结式本身。该算法是递增的意义上说，连续更大的矩阵，直到找到一个与上述性质。对于多阶系统，新算法产生最优矩阵，即，将稀疏结式表示为单个行列式。该算法的实现和实验结果。此外，我们还提出了一个计算n元多项式混合体积的有效算法。该计算提供了公共孤立根的数目的上界。一个公开可用的实现算法和经验的结果报告表明，它是最快的混合卷代码。
We propose a new and e cient algorithm for computing the sparse resultant of a system of n+1 polynomial equations in n unknowns. This algorithm produces a matrix whose entries are coe cients of the given polynomials and is typically smaller than the matrices obtained by previous approaches. The matrix determinant is a nontrivial multiple of the sparse resultant from which the sparse resultant itself can be recovered. The algorithm is incremental in the sense that successively larger matrices are constructed until one is found with the above properties. For multigraded systems, the new algorithm produces optimal matrices, i.e., expresses the sparse resultant as a single determinant. An implementation of the algorithm is described and experimental results are presented. In addition, we propose an e cient algorithm for computing the mixed volume of n polynomials in n variables. This computation provides an upper bound on the number of common isolated roots. A publicly available implementation of the algorithm is presented and empirical results are reported which suggest that it is the fastest mixed volume code to date.