On the cost of computing roots of polynomials

DOI10.1007/BF02612355zbMath0542.65025OpenAlexW2040238541MaRDI QIDQ3330394

Ze-Ke Wang, Harold W. Kuhn, Sen-Lin Xu

Publication date: 1984

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

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

zbMATH Keywords

computational complexityzeros of a polynomialroots of polynomialscomplementary pivotingpiecewise linear homotopy

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)

On the cost of approximating all roots of a complex polynomial ⋮ How to be sure of finding a root of a complex polynomial using Newton's method ⋮ 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 ⋮ Relative performance evaluation for dynamic contracts in a large competitive market ⋮ Some computational methods for systems of nonlinear equations and systems of polynomial equations ⋮ On the complexity of a PL homotopy algorithm for zeros of polynomials

Cites Work

• Unnamed Item
• The fundamental theorem of algebra and complexity theory
• A PL homotopy for finding all the roots of a polynomial

This page was built for publication: On the cost of computing roots of polynomials