Computational Complexity: On the Geometry of Polynomials and a Theory of Cost: II

DOI10.1137/0215011zbMath0625.65036OpenAlexW2029950920MaRDI QIDQ3028211

Michael Shub, Stephen Smale

Publication date: 1986

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/7f26baa2f3c2995ec06a78db98e483f9e81b51e4

zbMATH Keywords

computational complexityefficiencyEuler methodpolynomial root findingnumber of iterationsgeneralized Euler with modificationzero of a complex polynomial

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Zeros of polynomials, rational functions, and other analytic functions of one complex variable (e.g., zeros of functions with bounded Dirichlet integral) (30C15) Numerical computation of solutions to single equations (65H05)

Related Items (39)

On the cost of approximating all roots of a complex polynomial ⋮ How to be sure of finding a root of a complex polynomial using Newton's method ⋮ Optimal solution of nonlinear equations ⋮ Complexity of Bezout's theorem. V: Polynomial time ⋮ Point estimation of simultaneous methods for solving polynomial equations: A survey. II. ⋮ Smale’s mean value conjecture and the coefficients of univalent functions ⋮ Algebraic complexity of computing polynomial zeros ⋮ Sequential and parallel complexity of approximate evaluation of polynomial zeros ⋮ On the efficiency of algorithms of analysis ⋮ Improved two-step Newton's method for computing simple multiple zeros of polynomial systems ⋮ A probabilistic theory for error estimation in automatic integration ⋮ Statistical complexity of the power method for Markov chains ⋮ On zero finding methods of higher order from data at one point ⋮ Geometric function theory and Smale's mean value conjecture ⋮ Extremal problems in geometric function theory ⋮ Newton's method in practice. II: The iterated refinement Newton method and near-optimal complexity for finding all roots of some polynomials of very large degrees ⋮ Flow box decomposition for gradients of univariate polynomials, billiards on the Riemann sphere, tree-like configurations of vanishing cycles for \(A_{n}\) curve singularities and geometric cluster monodromy ⋮ Recent developments in information-based complexity ⋮ Geometry of polynomials and root-finding via path-lifting ⋮ Globally convergent, iterative path-following for algebraic equations ⋮ SMALE’S PROBLEM FOR CRITICAL POINTS ON CERTAIN TWO RAYS ⋮ Smale's mean value conjecture for finite Blaschke products ⋮ Newton's method and the Computational Complexity of the Fundamental Theorem of Algebra ⋮ Complexity and algorithms for nonlinear optimization problems ⋮ Semialgebraic complexity of functions ⋮ Kronecker's and Newton's approaches to solving: a first comparison ⋮ On the average number of steps of the simplex method of linear programming ⋮ Dual mean value problem for complex polynomials ⋮ Approximate Zeros of Quadratically Convergent Algorithms ⋮ Point estimation of simultaneous methods for solving polynomial equations: A survey ⋮ Topological complexity of a root finding algorithm ⋮ On Approximate Zeros and Rootfinding Algorithms for a Complex Polynomial ⋮ On critical values of polynomials with real critical points ⋮ On isolation of simple multiple zeros and clusters of zeros of polynomial systems ⋮ Partial fraction decomposition in \(\mathbb{C}(z)\) and simultaneous Newton iteration for factorization in \(\mathbb{C}^{[z}\)] ⋮ Critical points and values of complex polynomials ⋮ On the efficient global dynamics of Newton’s method for complex polynomials ⋮ A short survey on Kantorovich ⋮ Average case optimality

This page was built for publication: Computational Complexity: On the Geometry of Polynomials and a Theory of Cost: II