Smale's fundamental theorem of algebra reconsidered

DOI10.1007/S10208-013-9155-YzbMATH Open1316.65050arXiv1204.0036OpenAlexW2043325110MaRDI QIDQ404254FDOQ404254

Authors: Diego Armentano, Michael Shub 

Publication date: 4 September 2014

Published in: Foundations of Computational Mathematics (Search for Journal in Brave)

Abstract: In his 1981 Fundamental Theorem of Algebra paper Steve Smale initiated the complexity theory of finding a solution of polynomial equations of one complex variable by a variant of Newton's method. In this paper we reconsider his algorithm in the light of work done in the intervening years. Smale's upper bound estimate was infinite average cost. Our's is polynomial in the B'ezout number and the dimension of the input. Hence polynomial for any range of dimensions where the B'ezout number is polynomial in the input size. In particular not just for the case that Smale considered but for a range of dimensions as considered by B"urgisser-Cucker where the max of the degrees is greater than or equal to $n^{1+epsilon}$ for some fixed $epsilon$. It is possible that Smale's algorithm is polynomial cost in all dimensions and our main theorem raises some problems that might lead to a proof of such a theorem.

Full work available at URL: https://arxiv.org/abs/1204.0036

Recommendations

• The complexity and geometry of numerically solving polynomial systems
• On Smale's 17th problem: a probabilistic positive solution
• Efficient polynomial system solving by numerical methods
• Some remarks on Smale's “Algorithms for solving equations”
• Efficient polynomial system-solving by numerical methods

zbMATH Keywords

numerical experimentNewton methodhomotopy methodpolynomial equationSmale's fundamental theorem of algebra

Mathematics Subject Classification ID

Global methods, including homotopy approaches to the numerical solution of nonlinear equations (65H20) Numerical computation of roots of polynomial equations (65H04)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• COMPLEXITY AND REAL COMPUTATION: A MANIFESTO
• Title not available (Why is that?)
• Smale's 17th problem: average polynomial time to compute affine and projective solutions
• The fundamental theorem of algebra and complexity theory
• Title not available (Why is that?)
• On a problem posed by Steve Smale
• Complexity of Bezout’s Theorem IV: Probability of Success; Extensions
• Complexity of Bezout's theorem. VI: Geodesics in the condition (number) metric
• Complexity of Bezout's theorem. III: Condition number and packing
• An arithmetic Poisson formula for the multi-variate resultant
• Complexity of Bezout's Theorem I: Geometric Aspects
• Title not available (Why is that?)
• Fast linear homotopy to find approximate zeros of polynomial systems
• A note on the finite variance of the averaging function for polynomial system solving
• On the Efficiency of Newton's Method in Approximating All Zeros of a System of Complex Polynomials
• Adaptive step-size selection for homotopy methods to solve polynomial equations
• A continuation method to solve polynomial systems and its complexity

Cited In (11)

• Erratum to: ``Smale's fundamental theorem of algebra reconsidered
• Nonlinear equations. Paper from the 28th Brazilian mathematics colloquium -- 28\(^{\text o}\) Colóquio Brasileiro de Matemática, Rio de Janeiro, Brazil, July 2011
• Title not available (Why is that?)
• Smale's polynomial problem
• Title not available (Why is that?)
• The complexity and geometry of numerically solving polynomial systems
• Efficient polynomial system solving by numerical methods
• Complexity of path-following methods for the eigenvalue problem
• Efficient polynomial system-solving by numerical methods
• Solving systems of polynomial equations by bounded and real homotopy
• Title not available (Why is that?)

This page was built for publication: Smale's fundamental theorem of algebra reconsidered

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q404254)