The fundamental theorem of algebra and complexity theory

DOI10.1090/S0273-0979-1981-14858-8zbMATH Open0456.12012MaRDI QIDQ3904686FDOQ3904686

Authors: Stephen Smale 

Publication date: 1981

Published in: Bulletin of the American Mathematical Society (Search for Journal in Brave)

zbMATH Keywords

approximation of zeros of complex polynomial

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Representations of entire functions of one complex variable by series and integrals (30D10) Numerical computation of solutions to single equations (65H05) Polynomials in real and complex fields: location of zeros (algebraic theorems) (12D10)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• On the Volume of Tubes
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• A Constructive Proof of the Brouwer Fixed-Point Theorem and Computational Results
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The geometry of the generalized Gauss map
• A convergent process of price adjustment and global Newton methods
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On local Pareto Optima
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Shorter Notes: A Proof of the Nonretractibility of a Cell Onto its Boundary
• The Solution of Systems of Piecewise Linear Equations
• Title not available (Why is that?)
• Title not available (Why is that?)
• On Algorithms for Solvingf(x)=0
• Complex differential and integral geometry and curvature integrals associated to singularities of complex analytic varieties

Cited In (only showing first 100 items - show all)

• Shifted varieties and discrete neighborhoods around varieties
• Wilkinson's bus: weak condition numbers, with an application to singular polynomial eigenproblems
• Finiteness of the set of conservative polynomials of given degree
• On the infinite-dimensional QR algorithm
• Plane Autonomous Systems with Rational Vector Fields
• On application of some recent techniques of the design of algebraic algorithms to the sequential and parallel evaluation of the roots of a polynomial and to some other numerical problems
• Specifying attracting cycles for Newton maps of polynomials
• Some remarks on Dvorcuk's root-finding method
• Invertibility of random fredholm operators
• Ecology models and Newton vector fields
• Dual Smale's mean value conjecture
• Extremal problems in geometric function theory
• Reshaping the metaphor of proof
• Recent developments in information-based complexity
• Convergence behavior for Newton-Steffensen's method under \(\gamma\)-condition of second derivative
• A short survey on Kantorovich-like theorems for Newton's method
• On the convergence of the sequences of Gerschgorin-like disks
• Local and semilocal convergence of a family of multi-point Weierstrass-type root-finding methods
• Convergence analysis of Davidchack and Lai's algorithm for finding periodic orbits
• Average-case complexity without the black swans
• A universal constant for the convergence of Newton's method and an application to the classical homotopy method
• Computational complexity. On the geometry of polynomials and a theory of cost. I
• A family of root-finding methods with accelerated convergence
• Geometry of polynomials and root-finding via path-lifting
• The Newton transform: An operational method for constructing integrals of dynamical systems
• Density estimates on composite polynomials
• On the convergence of Wang-Zheng's method
• Mean value conjectures for rational maps
• On the complexity of a PL homotopy algorithm for zeros of polynomials
• On the complexity of a piecewise linear algorithm for approximating roots of complex polynomials
• Point estimation of a family of simultaneous zero-finding methods
• Probabilistic analysis of numerical methods for integral equations
• The continuous, desingularized Newton method for meromorphic functions
• On the existence of generally convergent algorithms
• A probabilistic theory for error estimation in automatic integration
• Global aspects of the continuous and discrete Newton method: A case study
• Uniform convergence of higher order quasi Hermite-Fejér interpolation
• Corrections to Probabilistic analysis of numerical methods for integral equations
• Computational complexity of a piecewise linear homotopy algorithm
• On a modification of the Ehrlich–Aberth method for simultaneous approximation of polynomial zeros
• Improved two-step Newton's method for computing simple multiple zeros of polynomial systems
• Algebraic complexity of computing polynomial zeros
• Study of linear information for classes of polynomial equations
• Global convergence of the method of successive approximations on \(S^ 1\)
• Some computational methods for systems of nonlinear equations and systems of polynomial equations
• On the cost of computing roots of polynomials
• On isolation of simple multiple zeros and clusters of zeros of polynomial systems
• On an efficient simultaneous method for finding polynomial zeros
• On Gauss's first proof of the fundamental theorem of algebra
• Responses to ``Theoretical Mathematics: Toward\\ a cultural synthesis of mathematics and\\ theoretical physics, by A. Jaffe and F. Quinn
• On the cost of approximating all roots of a complex polynomial
• A new fourth-order family of simultaneous methods for finding polynomial zeros
• Geometric function theory and Smale's mean value conjecture
• On Approximate Zeros and Rootfinding Algorithms for a Complex Polynomial
• A general approach to isolating roots of a bitstream polynomial
• Complexity theory of numerical linear algebra
• An adjoint-based approach for finding invariant solutions of Navier-Stokes equations
• The Probability That a Numerical Analysis Problem is Difficult
• Smale's fundamental theorem of algebra reconsidered
• Critical points and values of complex polynomials
• On critical values of polynomials with real critical points
• On the history of the fundamental theorem of algebra: theory of equations and integral calculus
• Some inequalities for polynomials and rational functions associated with lemniscates
• A continuation method to solve polynomial systems and its complexity
• Approximate Zeros of Quadratically Convergent Algorithms
• Cayley's problem and Julia sets
• Smale's problem for critical points on certain two rays
• Polynomials versus finite Blaschke products
• One-dimensional Coulomb multiparticle systems
• On the new fourth-order methods for the simultaneous approximation of polynomial zeros
• A Gröbner free alternative for polynomial system solving
• Newton's method and the computational complexity of the fundamental theorem of algebra
• Extending the applicability of the Gauss-Newton method under average Lipschitz-type conditions
• Extended Newton methods for conic inequalities: approximate solutions and the extended Smale \(\alpha\)-theory
• Smale's mean value conjecture and complex dynamics
• Newton's Method for Underdetermined Systems of Equations Under the γ-Condition
• On zero finding methods of higher order from data at one point
• On the average number of steps of the simplex method of linear programming
• Partial fraction decomposition in \(\mathbb{C}(z)\) and simultaneous Newton iteration for factorization in \(\mathbb{C}^{[z]}\)
• Optimal and nearly optimal algorithms for approximating polynomial zeros
• On a cubically convergent derivative-free root finding method
• Uniqueness of the singular points of vector fields on Riemannian manifolds under the \(\gamma\)-condition
• On the solution of systems of equations with constant rank derivatives
• Dual mean value problem for complex polynomials
• The guaranteed convergence of Laguerre-like method
• Topological complexity of a root finding algorithm
• Smoothed analysis of complex conic condition numbers
• The probability that a slightly perturbed numerical analysis problem is difficult
• Kronecker's and Newton's approaches to solving: a first comparison
• Point estimation of simultaneous methods for solving polynomial equations: A survey
• Sequential and parallel complexity of approximate evaluation of polynomial zeros
• Extremal polynomials in Smale's mean value conjecture
• On the worst-case arithmetic complexity of approximating zeros of polynomials
• Kantorovich-type convergence criterion for inexact Newton methods
• Recent development in computational complexity characterization of Nash equilibrium
• Computational complexity of kernel-based density-ratio estimation: a condition number analysis
• Local and global behavior for algorithms of solving equations
• A posteriori error bound methods for the inclusion of polynomial zeros
• On one extremal problem for complex polynomials with constraints on critical values
• Point estimation of simultaneous methods for solving polynomial equations: A survey. II.

This page was built for publication: The fundamental theorem of algebra and complexity theory

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