The Computational Complexity of the Chow Form
The Computational Complexity of the Chow Form
复制标题
DOI：
10.1007/s10208-002-0078-2
复制
发表时间：
2002-10
影响因子：
3
通讯作者：
中科院分区：
文献类型：
--
作者：
本文给出了计算代数簇的等维分支的Chowform的一个有界概率算法。特别是，这给出了一个替代程序的有效等维分解的品种，因为每个等维组件的特点是其周形式。该算法的预期复杂度是多项式的大小和几何次数的输入方程系统定义的品种。因此，它提高了（或满足在某些特殊情况下）的复杂性，所有以前的算法计算周形式。除此之外，我们澄清的概率和均匀性方面，这构成了进一步的贡献的文件。该算法基于消元理论技术，与M. Giusti，J. Heintz，L. M.帕尔多和他们的合作者事实上，我们可以被认为是他们的算法的零维系统的情况下，正维品种的延伸。处理正维簇的关键是一个新的Poisson型乘积公式。这个公式允许我们从一个合适的零维纤维计算一个等维簇的Chow形式。作为应用，我们得到了一个算法来计算一个子类的稀疏结式，其复杂性是多项式的维数和体积的输入集的指数。作为另一个应用，我们推导出一个算法计算的（唯一）解决方案的一般超定多项式方程组。
We present a bounded probability algorithm for the computation of the Chowforms of the equidimensional components of an algebraic variety. In particular, this gives an alternative procedure for the effective equidimensional decomposition of the variety, since each equidimensional component is characterized by its Chow form. The expected complexity of the algorithm is polynomial in the size and the geometric degree of the input equation system defining the variety. Hence it improves (or meets in some special cases) the complexity of all previous algorithms for computing Chow forms. In addition to this, we clarify the probability and uniformity aspects, which constitutes a further contribution of the paper. The algorithm is based on elimination theory techniques, in line with the geometric resolution algorithm due to M. Giusti, J. Heintz, L. M. Pardo, and their collaborators. In fact, ours can be considered as an extension of their algorithm for zero-dimensional systems to the case of positive-dimensional varieties. The key element for dealing with positive-dimensional varieties is a new Poisson-type product formula. This formula allows us to compute the Chow form of an equidimensional variety from a suitable zero-dimensional fiber. As an application, we obtain an algorithm to compute a subclass of sparse resultants, whose complexity is polynomial in the dimension and the volume of the input set of exponents. As another application, we derive an algorithm for the computation of the (unique) solution of a generic overdetermined polynomial equation system.