Topological complexity of a root finding algorithm

DOI10.1016/0885-064X(89)90029-0zbMATH Open0689.65030OpenAlexW2077918470MaRDI QIDQ582007FDOQ582007

Authors: Myong-Hi Kim 

Publication date: 1989

Published in: Journal of Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0885-064x(89)90029-0

Recommendations

• Topological complexity and real roots of polynomials
• scientific article
• On the topology of algorithms. I
• scientific article; zbMATH DE number 953047
• Polynomial Root-Finding Algorithms and Branched Covers

zbMATH Keywords

computational complexitytopological complexityzeros of polynomialsroot finding algorithm

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) Real polynomials: location of zeros (26C10) Numerical computation of solutions to single equations (65H05)

Cites Work

• Title not available (Why is that?)
• The fundamental theorem of algebra and complexity theory
• On the topology of algorithms. I
• On the efficiency of algorithms of analysis
• Computational Complexity: On the Geometry of Polynomials and a Theory of Cost: II

Cited In (15)

• Title not available (Why is that?)
• Topological complexity and real roots of polynomials
• A lower bound for the topological complexity of poly(D,n)
• On the complexity of isolating real roots and computing with certainty the topological degree
• Root-neededness and approximations of neededness
• On the distance to the zero set of a homogeneous polynomial
• Recursively enumerable subsets of \(\mathbb{R}^{q}\) in two computing models Blum-Shub-Smale machine and Turing machine
• Geometry of polynomials and root-finding via path-lifting
• Kronecker's and Newton's approaches to solving: a first comparison
• On the probability distribution of condition numbers of complete intersection varieties and the average radius of convergence of Newton's method in the underdetermined case
• Smale's 17th problem: average polynomial time to compute affine and projective solutions
• On the complexity of a piecewise linear algorithm for approximating roots of complex polynomials
• On the topology of algorithms. I
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• Logical Approaches to Computational Barriers

This page was built for publication: Topological complexity of a root finding algorithm

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