The Computational Complexity of the Chow Form
Copyright policy )The Computational Complexity of the Chow Form
We present a bounded probability algorithm for the computation of the Chow forms of the equidimensional components of an algebraic variety. Its complexity is polynomial in the length and in the geometric degree of the input equation system defining the variety. In particular, it provides an alternative algorithm for the equidimensional decomposition of a variety. As an application we obtain an algorithm for the computation of a subclass of sparse resultants, whose complexity is polynomial in the dimension and the volume of the input set of exponents. As a further application, we derive an algorithm for the computation of the (unique) solution of a generic over-determined equation system.
60 pages, Latex2e
- National University of La Plata Argentina
- National Scientific and Technical Research Council Argentina
- University of Buenos Aires Argentina
- University of Paris France
- Panthéon-Assas University France
symbolic Newton algorithm, SYMBOLIC NEWTON ALGORITHM, EQUIDIMENSIONAL DECOMPOSITION OF ALGEBRAIC VARIETIES, Analysis of algorithms and problem complexity, 14Q15, 68W30, Symbolic computation and algebraic computation, sparse resultant, Mathematics - Commutative Algebra, Commutative Algebra (math.AC), OVERDETERMINED POLYNOMIAL EQUATION SYSTEM, overdetermined polynomial equation system, Mathematics - Algebraic Geometry, Computational aspects of higher-dimensional varieties, FOS: Mathematics, https://purl.org/becyt/ford/1.1, CHOW FORM, SPARSE RESULTANT, https://purl.org/becyt/ford/1, Algebraic Geometry (math.AG), equidimensional decomposition of algebraic variety
symbolic Newton algorithm, SYMBOLIC NEWTON ALGORITHM, EQUIDIMENSIONAL DECOMPOSITION OF ALGEBRAIC VARIETIES, Analysis of algorithms and problem complexity, 14Q15, 68W30, Symbolic computation and algebraic computation, sparse resultant, Mathematics - Commutative Algebra, Commutative Algebra (math.AC), OVERDETERMINED POLYNOMIAL EQUATION SYSTEM, overdetermined polynomial equation system, Mathematics - Algebraic Geometry, Computational aspects of higher-dimensional varieties, FOS: Mathematics, https://purl.org/becyt/ford/1.1, CHOW FORM, SPARSE RESULTANT, https://purl.org/becyt/ford/1, Algebraic Geometry (math.AG), equidimensional decomposition of algebraic variety
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).35 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Top 10% influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Top 10% impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!