Degeneracy Loci and Polynomial Equation Solving

作者：Bank Bernd; Giusti Marc; Heintz Joos^*; Lecerf Gregoire; Matera Guillermo; Solerno Pablo

来源：Foundations of Computational Mathematics, 2015, 15(1): 159-184.

DOI：10.1007/s10208-014-9214-z

• Polynomial equation solving
• Pseudo-polynomial complexity
• Degeneracy locus
• Degree of varieties

Let V be a smooth, equidimensional, quasi-affine variety of dimension r overC, and let F be a (pxs) matrix of coordinate functions of C[V], where s >= p+ r. The pair (V, F) determines a vector bundle E of rank s-p over W := {x is an element of V vertical bar rk F(x) = p}. We associate with (V, F) a descending chain of degeneracy loci of E (the generic polar varieties of V represent a typical example of this situation). The maximal degree of these degeneracy loci constitutes the essential ingredient for the uniform, bounded-error probabilistic pseudo-polynomial-time algorithm that we will design and that solves a series of computational elimination problems that can be formulated in this framework. We describe applications to polynomial equation solving over the reals and to the computation of a generic fiber of a dominant endomorphism of an affine space.

• 出版日期2015-2