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)

• 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.
• Univariate polynomials: Nearly optimal algorithms for numerical factorization and root-finding
• Optimal solution of nonlinear equations
• The geometry of ill-conditioning
• How to be sure of finding a root of a complex polynomial using Newton's method
• The theory of Newton's method
• Multiple attractors in Newton's method
• Complexity of Bezout's theorem. V: Polynomial time
• Numerical computation of polynomial zeros by means of Aberth's method
• Phase transitions in the one-dimensional Coulomb medium
• New barriers in complexity theory: on the solvability complexity index and the towers of algorithms
• On the efficiency of algorithms of analysis
• Kantorovich's type theorems for systems of equations with constant rank derivatives
• Linear programming, complexity theory and elementary functional analysis
• Chebyshev-like root-finding methods with accelerated convergence
• Ten misconceptions from the history of analysis and their debunking
• Verified error bounds for singular solutions of nonlinear systems
• Smale's mean value conjecture for odd polynomials
• On the volume of tubular neighborhoods of real algebraic varieties
• On the finite-increment theorem for complex polynomials
• Deformation techniques to solve generalised Pham systems
• Conservative polynomials and yet another action of \(\text{Gal}(\overline{\mathbb Q}/\mathbb Q)\) on plane trees
• Early Coefficients of the Inverse of a Regular Convex Function
• Convergence of Gauss-Newton's method and uniqueness of the solution
• Average case optimality
• On the solvability complexity index, the \(n\)-pseudospectrum and approximations of spectra of operators
• An efficient higher order family of root finders
• Statistical complexity of the power method for Markov chains
• Markov-type inequality and a lower bound for the moduli of critical values of polynomials
• Robust certified numerical homotopy tracking
• Smale’s mean value conjecture and the coefficients of univalent functions
• Certified predictor-corrector tracking for Newton homotopies
• Smale's \(\alpha \)-theory for inexact Newton methods under the \(\gamma \)-condition
• Real computations with fake numbers
• Smale's mean value conjecture for finite Blaschke products
• 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

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)