Topological complexity of a root finding algorithm

DOI10.1016/0885-064X(89)90029-0zbMath0689.65030OpenAlexW2077918470MaRDI QIDQ582007

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

Related Items (6)

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 distance to the zero set of a homogeneous polynomial ⋮ 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 ⋮ 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

Cites Work

• Unnamed Item
• On the topology of algorithms. I
• Computational Complexity: On the Geometry of Polynomials and a Theory of Cost: II
• On the efficiency of algorithms of analysis
• The fundamental theorem of algebra and complexity theory

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