On the cost of approximating all roots of a complex polynomial

DOI10.1007/BF01582052zbMath0577.65040OpenAlexW2047432539MaRDI QIDQ3698169

James Renegar

Publication date: 1985

Published in: Mathematical Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01582052

zbMATH Keywords

computational complexityNewton's methodzeros of polynomialshomotopy algorithmcomplex polynomial

Mathematics Subject Classification ID

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

Specified precision polynomial root isolation is in NC ⋮ Optimal solution of nonlinear equations ⋮ On the efficiency of algorithms of analysis ⋮ Rudiments of an average case complexity theory for piecewise-linear path following algorithms ⋮ Study of linear information for classes of polynomial equations ⋮ Some computational methods for systems of nonlinear equations and systems of polynomial equations ⋮ On the geometry of Graeffe iteration ⋮ Partial fraction decomposition in \(\mathbb{C}(z)\) and simultaneous Newton iteration for factorization in \(\mathbb{C}^{[z}\)] ⋮ On the complexity of a PL homotopy algorithm for zeros of polynomials

Cites Work

• Unnamed Item
• Unnamed Item
• Computational Complexity: On the Geometry of Polynomials and a Theory of Cost: II
• On the cost of computing roots of polynomials
• The fundamental theorem of algebra and complexity theory
• Homotopies for computation of fixed points
• Homotopies for computation of fixed points on unbounded regions

This page was built for publication: On the cost of approximating all roots of a complex polynomial