Smale's fundamental theorem of algebra reconsidered

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

Authors Diego Armentano, Michael Shub 

Publication date 4 September 2014

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

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

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)

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.

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

Cites work

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

Cited in

(11)

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

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)