When polynomial equation systems can be “solved” fast? (English) Zbl 0902.12005

Cohen, Gérard (ed.) et al., Applied algebra, algebraic algorithms and error-correcting codes. 11th international symposium, AAECC-11, Paris, France, July 17-22, 1995. Proceedings. Berlin: Springer-Verlag. Lect. Notes Comput. Sci. 948, 205-231 (1995).
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 […] 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 J. Heintz and 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 T. Krick and L. Pardo [Proc. MEGA ’94, Birkhäuser (1994; Zbl 0878.11043)]. Wright’s review of the paper of M. Giusti, J. Heintz and 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].


12Y05 Computational aspects of field theory and polynomials (MSC2010)
68W30 Symbolic computation and algebraic computation
65F30 Other matrix algorithms (MSC2010)
12E12 Equations in general fields
13P99 Computational aspects and applications of commutative rings