When polynomial equation systems can be ``solved'' fast? (Q4352797)

In this paper the symbolic solution of systems of zero-dimensional polynomial equations is done using arithmetic networks and straight line programs which contain in addition to the those of an ordinary network a new type of nodes; the authors call them FOR gates and think of them as modelizing parallel FORTRAN programs. The input for the following `affine' theorem has two parts: a) a family of \(n\) polynomials \(f_1,\ldots, f_n \in k[X_1,\ldots, X_n]\) of degree \(\leq d\) defining a regular sequence encoded by an essentially division free straight line program \(\beta\) of nonscalar size (length) \(L\) and non-scalar depth \(\ell\), and b) a nonzero linear form \(H\) on \(k[X_1,\ldots, X_n]\) represented by its coefficient \(n\)-tuple. \(k\) is a suitably effective field. Consider varieties \(V(f_1,\ldots,f_i) \subset A^n(\overline{k})\), \((1\leq i \leq n)\). Its irreducible components are all of dimension \(n-i\) and its degree \(\deg V(f_1, \ldots, f_i)\) is the cardinality of the finite set of points obtained by cutting it with \(n-i\) generic hyperplanes. Let \(\delta:=\max\{\text{deg} V(f_1,\ldots,f_i):1\leq i \leq n\}\) be the geometric affine degree of the the equation system. Theorem: Under these conditions there exists an arithmetic network with FOR gates which from input \(\beta\) and \(H\) computes the coefficients of a non-zero polynomial \(p\in k[T]\) such that \(p(H)\) vanishes on the variety \(V=V(f_1,\ldots, f_n)\). The network's size is \((nd\delta L)^{O(1)}\); its depth is \(O(n (\log_2(\delta d)+ \ell))\). The point here is that in `many important [\dots] geometrically well suited cases', \(\delta\) is much smaller than \(d^n\), in which latter case only the usual best to be hoped for worst case complexity bounds would be obtained; see \textit{J. Heintz} and \textit{J. Morgenstern} [J. Complexity 9, 471-498 (1993; Zbl 0835.68054)]. This allows to reduce the size of the matrices in the algorithms. A similar theorem is provided for the case that the polynomials form a toric complete intersection, and the question under which conditions the above complexity bounds hold for ordinary arithmetic networks is also dealt with. The paper has a well written introduction and explains in Section 2 its own computational model in detail; even so, the reader will need extensive background knowledge (see keywords, i.e. UT) from the some fifty papers given in its references. Pivotal seems to be the paper of \textit{T. Krick} and \textit{L. Pardo} [Proc. MEGA '94, Birkhäuser (1994; Zbl 0878.11043)]. Wright's review of the paper of \textit{M. Giusti, J. Heintz} and \textit{J. Sabia} [Comput. Complexity 3, 56-95 (1993; Zbl 0824.68051)] provides further perspective and references for the one under consideration. For the entire collection see [Zbl 0847.00060].