When polynomial equation systems can be ``solved fast?
When polynomial equation systems can be ``solved'' fast?
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].
- scientific article; zbMATH DE number 3959582
- Efficient solution of real polynomial systems of equations
- Efficient polynomial system-solving by numerical methods
- Efficient polynomial system solving by numerical methods
- Systems with parameters, or efficiently solving systems of polynomial equations: 33 years later. I
- Systems with parameters, or efficiently solving systems of polynomial equations 33 years later. II
- Solving polynomial systems equation by equation
- Accelerated Solution of Multivariate Polynomial Systems of Equations
- Fast algorithms for polynomial solutions of linear differential equations
- Systems with parameters, or efficiently solving systems of polynomial equations: 33 years later. III
- Interpolation of polynomials given by straight-line programs
- Evaluation techniques for zero-dimensional primary decomposition
- Lower bounds for diophantine approximations
- Polar varieties, real equation solving, and data structures: the hypersurface case
- Straight-line programs in geometric elimination theory
- Computing the characteristic polynomial of multivariate polynomial matrices given by straight-line programs
- Some speed-ups and speed limits for real algebraic geometry
- Bit complexity for multi-homogeneous polynomial system solving -- application to polynomial minimization
- Matrices in elimination theory
- Solving degenerate sparse polynomial systems faster
- Functional programming concepts and straight-line programs in computer algebra
- Systems of rational polynomial equations have polynomial size approximate zeros on the average
- Complexity results for triangular sets
- On the intrinsic complexity of the arithmetic Nullstellensatz
- Time-space tradeoffs in algebraic complexity theory
- Homotopy techniques for solving sparse column support determinantal polynomial systems
- Bit complexity for computing one point in each connected component of a smooth real algebraic set
- Computing critical points for invariant algebraic systems
- Solving parametric systems of polynomial equations over the reals through Hermite matrices
- Solving determinantal systems using homotopy techniques
- On types of degenerate critical points of real polynomial functions
- Degeneracy loci and polynomial equation solving
- A concise proof of the Kronecker polynomial system solver from scratch
- On the probability distribution of singular varieties of given corank
- Change of order for regular chains in positive dimension
- On the complexity of the resolvent representation of some prime differential ideals
- On the complexity exponent of polynomial system solving
- Positive dimensional parametric polynomial systems, connectivity queries and applications in robotics
- Point searching in real singularcomplete intersection varieties: algorithms of intrinsic complexity
- Fast computation of a rational point of a variety over a finite field
- Solving projective complete intersection faster
- scientific article; zbMATH DE number 4096783 (Why is no real title available?)
- A lower bound for solvability of polynomial equations
- Algorithms of intrinsic complexity for point searching in compact real singular hypersurfaces
- scientific article; zbMATH DE number 865572 (Why is no real title available?)
- Effective de Rham cohomology — The general case
- A Gröbner free alternative for polynomial system solving
- Kronecker's and Newton's approaches to solving: a first comparison
- Computing bases of complete intersection rings in Noether position
- Polynomial equation solving by lifting procedures for ramified fibers
- Deformation techniques to solve generalised Pham systems
- p-adic algorithm for bivariate Gröbner bases
- Further perspectives on elimination
- Counting solutions of a polynomial system locally and exactly
- A baby steps/giant steps probabilistic algorithm for computing roadmaps in smooth bounded real hypersurface
- Computing the equidimensional decomposition of an algebraic closed set by means of lifting fibers
- On types of isolated KKT points in polynomial optimization
- An \(\mathfrak{m}\)-adic algorithm for bivariate Gröbner bases
- Properness defects of projection and minimal discriminant variety
- Dedicated to the memory of Joos Heintz
- A Kronecker algorithm for locally closed sets over a perfect field
- Towards a library for straight-line programs
- Erzeugungsgrad, VC-dimension and neural networks with rational activation function
- Computing polynomial representation in subrings of multivariate polynomial rings
- Some applications of Chinese remainder theorem codes with error-correction
- Computing roadmaps in unbounded smooth real algebraic sets. II: Algorithm and complexity
- Evaluation properties of invariant polynomials
- An algorithm for implicit interpolation
This page was built for publication: When polynomial equation systems can be ``solved fast?
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4352797)
