The computational complexity of the Chow form
The Chow form of an equidimensional quasiprojective variety is one of the basic objects of algebraic geometry and plays a central role in elimination theory. Let \({\mathcal V}\in\mathbb{P}^n\) be an equidimensional quasiprojective variety of dimension \(r\), and degree \(D\) defined over \(\mathbb{Q}\). Its Chow form \({\mathcal F}_{\mathcal V}\) is a polynomial with rational coefficients (unique up to scalar factor) which characterizes the set of overdetermined linear systems over the projective closure \(\overline{\mathcal V}\). More precisely, let \(U_i\), \(i=0,\dots,r\) denote \(r+1\) sets of \(n+1\) variables each, and let \(L_i:=U_{i0}+ \cdots+ U_{in}x_n\) be the linear form associated to the set \(U_i\), \(i=0,\dots,r\). Then, \({\mathcal F}_{\mathcal V} \in\mathbb{Q} [U_0,\dots,U_r]\) is the squarefree polynomial such that \[ {\mathcal F}_V[u_0,\dots,u_r]=0 \Leftrightarrow\overline{\mathcal V}\cap\bigl\{L_0 (u_0,x)=0,\dots,L_r(u_r,x) =0\bigr\}\neq\emptyset, \] for \(u_i\in \mathbb{C}^{n+1}\), \(i=0,\dots,r\). From \({\mathcal F}_{\mathcal V}\), we can directly read the dimension of \({\mathcal V}\). Furthermore, if \({\mathcal V}\) is closed in \(\mathbb{P}^n\), its Chow form \({\mathcal F}_{\mathcal V}\) characterizes it, and it is possible to derive a complete set of equations for \({\mathcal V}\) from \({\mathcal F}_{\mathcal V}\). In this paper, the authors present a bounded probability algorithm for the computation of Chow forms of the equidimensional components of an algebraic variety defined by means of a given set of polynomials. Thus, in particular, this gives an alternative procedure for the effective equidimensional decomposition of the variety. Furthermore, the error probability is analyzed in detail. \textit{M. Giusti} et. al. [J. Pure Appl. Algebra 117--118, 277--317 (1997, Zbl 0871.68101); in: Straight-line programs in geometric elimination theory, J. Pure Appl. Algebra 124, 101--146 (1998; Zbl 0944.12004)] succeeded in classifying the tractability of polynomial equations solving in the zero-dimensional case in terms of the length, and the geometric degree of the input system. The algorithm presented can be seen as a general extension of these results to arbitrary varieties. The key element for dealing with positive-dimensional varieties is a new Poisson-type product formula. This formula allows to compute the Chow form from a suitable zero-dimensional fiber. The main result of this work is that the complexity of the algorithm is polynomial in the size and the geometric degree of the input equation system defining the variety. Hence, it improves the algorithms (which use dense encoding of polynomials) by \textit{L. Caniglia} [Appl. Algebra Eng. Commun. Comput. 1, 25--41 (1990; Zbl 0732.13012); \textit{M. Giusti} and \textit{J. Heintz} [in: Effective methods in algebraic geometry, Proc. Symp., Castiglioncello/Italy 1990, Prog. Math. 94, 169--194 (1991; Zbl 0755.14018)]; \textit{T. Krick} [Complejidad para Problemas de Geometría Elemental, Ph.D dissertation. Univ. Buenos Aires, Argentina (1990)]; and the algorithm (which uses the slp representation for the output) by \textit{S. Puddu} and \textit{J. Sabia} [J. Pure Appl. Algebra 129, 173--200 (1998; Zbl 0929.68132)]. The only previous algorithm whose complexity is in some cases comparable to this new algorithm is the one by \textit{G. Jeronimo, S. Puddu}, and \textit{J. Sabia} [J. Algorithms 41, 52--68 (2000; Zbl 1002.68061)], which computes an slp representation of the Chow form of the component of maximal dimension of an algebraic variety within complexity \((sd^n)^{{\mathcal O}(1)}\). In this paper, the authors do not compute the Chow forms for all the equidimensional components, but they replace the Bézout numbers \(d^n\) by \(d\delta\), where \(\delta\) denotes the geometric degree. As an application of these results, the authors obtain an algorithm to compute the subclass of sparse resultants, whose complexity is polynomial in the dimension and the volume of the input set of exponents. As another application, the authors derive an algorithm for the computation of the unique solution of a generic overdetermined polynomial equation system.
- Computing Chow forms and some applications
- The complexity of higher Chow groups
- The complexity to compute the Euler characteristic of complex varieties
- Explicit computation of the Chern character forms
- scientific article; zbMATH DE number 2070405
- A combinatoric shortcut to evaluate CHY-forms
- Computing the Chow variety of quadratic space curves
- scientific article; zbMATH DE number 38433
- scientific article; zbMATH DE number 4083786
- Computation of paramodular forms
- Deformation techniques for sparse systems
- Evaluation techniques for zero-dimensional primary decomposition
- Sparse resultants and straight-line programs
- Elimination theory in differential and difference algebra
- Chow form for projective differential variety
- Implicit representations of high-codimension varieties
- A package for computations with sparse resultants
- Computing real radicals and S-radicals of polynomial systems
- Elimination for generic sparse polynomial systems
- Difference Chow form
- The geometry of the flex locus of a hypersurface
- Degeneracy loci and polynomial equation solving
- Sparse differential resultant for Laurent differential polynomials
- A concise proof of the Kronecker polynomial system solver from scratch
- Computing multihomogeneous resultants using straight-line programs
- Change of order for regular chains in positive dimension
- Solving over-determined systems by the subresultant method (with an appendix by Marc Chardin)
- Rational univariate reduction via toric resultants
- On arithmetical bounds of Chow-forms
- Computing generators of the ideal of a smooth affine algebraic variety
- Computing Chow forms and some applications
- Puiseux expansions and nonisolated points in algebraic varieties
- Intersection theory in differential algebraic geometry: generic intersections and the differential Chow form
- Computing isolated roots of sparse polynomial systems in affine space
- Partial differential Chow forms and a type of partial differential Chow varieties
- A Poisson formula for the sparse resultant
- On a generalization of Stickelberger's theorem
- Segre-driven radicality testing
- Computing the equidimensional decomposition of an algebraic closed set by means of lifting fibers
- On the complexity of Chow and Hurwitz forms
- Variety evasive subspace families
- Sparse systems and algorithmic equidimensional decomposition
- Rational formulas for traces in zero-dimensional algebras
- Effective approximation of the solutions of algebraic equations
- Computation of differential Chow forms for ordinary prime differential ideals
This page was built for publication: The computational complexity of the Chow form
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1879037)
