Systems of rational polynomial equations have polynomial size approximate zeros on the average
type: Item
instance of: scholarly article
title: Systems of rational polynomial equations have polynomial size approximate zeros on the average
zbMATH Open document ID: 1018.14020
DOI: 10.1016/S0885-064X(02)00028-6
author: Yanyan Li
published in: Journal of Complexity
publication date: 2003-05-04T00:00:00Z
review text: In Smale's approximate zero theory an approximate zero of a system of polynomial equations \(F\) with associated zero \(\zeta\) is a point \(z\) such that the sequences of iterates of the Newton operator of \(F\) is well defined and converges quadratically to \(\zeta\). In this paper, two of the main parameters of this theory as the total number of solutions and the size of approximate zeros, namely, the number of tape cells in a Turing machine required to write down the list of digits describings the approximate zero, are studied for input systems of multivariate polynomial equations with rational coefficients of bounded bit length. This last restriction means that computing is discrete and not continuous. Under a continuous modelling, \textit{M. Shub} and \textit{S. Smale} have shown [in: Computational algebraic geometry, Proc. Conf., MEGA'92, Prog. Math. 109, 267-285 (1993; Zbl 0851.65031)]\ that the average number or real solutions of systems of polynomial equations with real coefficientes equals the square root of the Bézout number of the system. One of the questions answered in the affirmative in this paper is whether this average can be translated to the discrete case of systems with rational coefficients of bounded input length. Another outcome of this paper is that these systems have polynomial size approximate zeros on the average. The technique used by the authors is an improvement of a sharp method due to \textit{H. Davenport} [J. Lond. Math. Soc. 26, 179-183 (1951; Zbl 0042.27504)]\ which combine induction and Fubini's theorem.
Mathematics Subject Classification ID: 14P10
Mathematics Subject Classification ID: 12Y05
Mathematics Subject Classification ID: 14Q15
Mathematics Subject Classification ID: 65H10
zbMATH DE Number: 1903491
zbMATH Keywords: semi-algebraic sets
zbMATH Keywords: system of polynomial equations
zbMATH Keywords: Newton operator
zbMATH Keywords: approximate zeros
zbMATH Keywords: height of projective points
reviewed by: Antonio Diaz-Cano
describes a project that uses: Kronecker
MaRDI profile type: Publication
cites work: Polar varieties, real equation solving, and data structures: the hypersurface case
cites work: Polar varieties and efficient real elimination
cites work: On the combinatorial and algebraic complexity of quantifier elimination
cites work: Q3996250
cites work: Q3770650
cites work: On Euclid's Algorithm and the Computation of Polynomial Greatest Common Divisors
cites work: The Subresultant PRS Algorithm
cites work: On Euclid's Algorithm and the Theory of Subresultants
cites work: The hardness of polynomial equation solving
cites work: Kronecker's and Newton's approaches to solving: a first comparison
cites work: The distribution of condition numbers of rational data of bounded bit length
cites work: On the distribution of points in projective space of bounded height
cites work: Subresultants and Reduced Polynomial Remainder Sequences
cites work: On a Principle of Lipschitz
cites work: Q4850731
cites work: Lower bounds for diophantine approximations
cites work: Q4352797
cites work: Le rôle des structures de données dans les problèmes d'élimination
cites work: Straight-line programs in geometric elimination theory
cites work: A Gröbner free alternative for polynomial system solving
cites work: Eine Verallgemeinerung des Sturmschen Wurzelzählverfahrens
cites work: On the intrinsic complexity of the arithmetic Nullstellensatz
cites work: Q5772619
cites work: Definability and fast quantifier elimination in algebraically closed fields
cites work: The intrinsic complexity of parametric elimination methods
cites work: On the time-space complexity of geometric elimination procedures
cites work: Q4231918
cites work: Q4714022
cites work: Sharp estimates for the arithmetic Nullstellensatz
cites work: Sylvester-Habicht sequences and fast Cauchy index computation
cites work: Q3698903
cites work: On the Betti Numbers of Real Varieties
cites work: Lower bounds for arithmetic networks
cites work: Q4756757
cites work: Q5804648
cites work: Q4352783
cites work: Q4341368
cites work: A new decision method for elementary algebra
cites work: Q4279734
cites work: Q3135179
cites work: Complexity of Bezout's Theorem I: Geometric Aspects
cites work: Complexity of Bezout’s Theorem IV: Probability of Success; Extensions
cites work: Q5807665
cites work: Q5511997
cites work: Some extremal functions in Fourier analysis
cites work: Lower Bounds for Approximation by Nonlinear Manifolds
full work available at URL: s0885-064x(02)00028-6
OpenAlex ID: W2112718969
Recommended article: On the Worst-Case Arithmetic Complexity of Approximating Zeros of Systems of Polynomials
Recommended article: Smale’s 17th problem: Average polynomial time to compute affine and projective solutions
Recommended article: Complexity of Bezout's theorem. V: Polynomial time
Recommended article: A Schur's modified sequence and the number of zeros of a real polynomial in the unit disk: Testing its numerical quality
Recommended article: Condition length and complexity for the solution of polynomial systems
Recommended article: Kronecker's and Newton's approaches to solving: a first comparison
Recommended article: Le rôle des structures de données dans les problèmes d'élimination
Recommended article: Sequential and parallel complexity of approximate evaluation of polynomial zeros
Recommended article: Sturm sequences and the number of zeros of a real polynomial in the unit disk: Numerical computation
Recommended article: Q3681839