Topological complexity of a root finding algorithm

DOI10.1016/0885-064X(89)90029-0MaRDI QIDQ582007zbMATH OpenOpenAlexFDO

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

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)

Recommendations

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

Cites work

• scientific article; zbMATH DE number 3167270 (Why is no real title available?)
• Computational Complexity: On the Geometry of Polynomials and a Theory of Cost: II
• On the efficiency of algorithms of analysis
• On the topology of algorithms. I
• The fundamental theorem of algebra and complexity theory

Cited in

(15)

• On the topology of algorithms. I
• On the distance to the zero set of a homogeneous polynomial
• Smale's 17th problem: average polynomial time to compute affine and projective solutions
• scientific article; zbMATH DE number 4078810 (Why is no real title available?)
• Kronecker's and Newton's approaches to solving: a first comparison
• On the complexity of isolating real roots and computing with certainty the topological degree
• Topological complexity and real roots of polynomials
• On the complexity of a piecewise linear algorithm for approximating roots of complex polynomials
• Logical Approaches to Computational Barriers
• A lower bound for the topological complexity of poly(D,n)
• Recursively enumerable subsets of \(\mathbb{R}^{q}\) in two computing models Blum-Shub-Smale machine and Turing machine
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• Geometry of polynomials and root-finding via path-lifting
• 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
• Root-neededness and approximations of neededness

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)