Sparse resultants and straight-line programs (Q1690776): Difference between revisions

The concept of \textit{sparse resultant} defined in [\textit{I. M. Gelfand} et al., Discriminants, resultants, and multidimensional determinants. Reprint of the 1994 edition. Boston, MA: Birkhäuser (2008; Zbl 1138.14001)] has been generalized properly in [\textit{A. I. Esterov}, Discrete Comput. Geom. 44, No. 1, 96--148 (2010; Zbl 1273.14105)], [\textit{C. D'Andrea} and \textit{M. Sombra}, Proc. Lond. Math. Soc. (3) 110, No. 4, 932--964 (2015; Zbl 1349.14160)] with the condition that a satisfactory \textit{Poisson type formula} for these resultants actually hold for any arbitrary sequence of supports. The paper under review takes advantage of this formula, jointly with the use of Geometric resolutions of varieties, Newton-Hensel liftings, and Padé approximations to produce a \textit{straight-line program} (an algorithm without bifurcations) to evaluate the sparse resultant of a given set of polynomials. The main result is the following: \par Theorem: Let ${\mathcal A}=({\mathcal A}_0,\dots,{\mathcal A}_n)$ be a sequence of non-empty finite subsets of ${\mathbb Z}^n.$ The sparse resultant $\mathrm{Res}_{\mathcal A}$ of these polynomials can be evaluated by a straight-line program of length polynomial in the following data: $\sum_{i=0}^n\#{\mathcal A}_i,\, \sum_{i=0}^n\mathrm{MV}_n({\mathcal A}_0,\dots,{\mathcal A}_{i-1},{\mathcal A}_{i+1},\dots, {\mathcal A}_n),$ and $\max\{\|a\|,\,a\in{\mathcal A}_i,\,0\leq i\leq n\}.$ \par Here, $\mathrm{MV}_n(\cdot,\dots,\cdot)$ denotes the $n$-th dimensional \textit{mixed volume} of the polytopes defined as the convex hull of each of the inputs. \par In addition, a probabilistic algorithm to compute, from a family of $n+1$ finite subsets of ${\mathbb Z}^n$, a straight-line program for the sparse resultant associated to $n+1$ Laurent polynomials with these support sets within a number of operations of the same order as for the computation of the resultant is designed.