Topological complexity of a root finding algorithm

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

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)

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 (8)

• Topological complexity and real roots of polynomials
• 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
• 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 a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines

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)