首页 | 本学科首页   官方微博 | 高级检索  
     检索      


The Computational Complexity of the Chow Form
Authors:Gabriela Jeronimo  Teresa Krick  Juan Sabia and Martín Sombra
Institution:(1) FCEyN, Departamento de Matemática, Universidad de Buenos Aires, Ciudad Universitaria 1428, Buenos Aires, Argentina;(2) Université de Paris, 7 UFR de Mathématiques Équipe de Géométrie et Dynamique, 2 place Jussieu 75251, Paris Cedex 05, France and Departamento de Matemática, Universidad Nacional de La Plata, Calle 50 y 115 1900, La Plata, Argentina
Abstract: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.
Keywords:Chow form  Equidimensional decomposition of algebraic varieties  Symbolic Newton algorithm  Sparse resultant  Overdetermined polynomial equation system
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号