Systems of rational polynomial equations have polynomial size approximate zeros on the average

DOI10.1016/S0885-064X(02)00028-6zbMath1018.14020OpenAlexW2112718969MaRDI QIDQ1869964

Yanyan Li

Publication date: 4 May 2003

Published in: Journal of Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0885-064x(02)00028-6

zbMATH Keywords

Newton operatorsystem of polynomial equationssemi-algebraic setsapproximate zerosheight of projective points

Mathematics Subject Classification ID

Numerical computation of solutions to systems of equations (65H10) Computational aspects of higher-dimensional varieties (14Q15) Semialgebraic sets and related spaces (14P10)

Related Items

A concise proof of the Kronecker polynomial system solver from scratch, Probabilistic condition number estimates for real polynomial systems. I: A broader family of distributions, On the probability distribution of singular varieties of given corank

Uses Software

• Kronecker

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Definability and fast quantifier elimination in algebraically closed fields
• Lower bounds for diophantine approximations
• Polar varieties, real equation solving, and data structures: the hypersurface case
• Straight-line programs in geometric elimination theory
• The hardness of polynomial equation solving
• The distribution of condition numbers of rational data of bounded bit length
• Lower bounds for arithmetic networks
• Sharp estimates for the arithmetic Nullstellensatz
• On the intrinsic complexity of the arithmetic Nullstellensatz
• Eine Verallgemeinerung des Sturmschen Wurzelzählverfahrens
• A new decision method for elementary algebra
• Some extremal functions in Fourier analysis
• Complexity of Bezout's Theorem I: Geometric Aspects
• The Subresultant PRS Algorithm
• The intrinsic complexity of parametric elimination methods
• On the combinatorial and algebraic complexity of quantifier elimination
• Le rôle des structures de données dans les problèmes d'élimination
• On the distribution of points in projective space of bounded height
• Complexity of Bezout’s Theorem IV: Probability of Success; Extensions
• Subresultants and Reduced Polynomial Remainder Sequences
• Lower Bounds for Approximation by Nonlinear Manifolds
• On Euclid's Algorithm and the Computation of Polynomial Greatest Common Divisors
• On Euclid's Algorithm and the Theory of Subresultants
• On the Betti Numbers of Real Varieties
• On a Principle of Lipschitz
• Sylvester-Habicht sequences and fast Cauchy index computation
• On the time-space complexity of geometric elimination procedures
• A Gröbner free alternative for polynomial system solving
• Kronecker's and Newton's approaches to solving: a first comparison
• Polar varieties and efficient real elimination