On the cost of computing roots of polynomials

DOI10.1007/BF02612355MaRDI QIDQ3330394zbMATH OpenOpenAlexFDO

Authors Zeke Wang, Senlin Xu, Harold W. Kuhn

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

complementary pivotingcomputational complexitypiecewise linear homotopyroots of polynomialszeros of a 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)

Recommendations

• On the worst-case arithmetic complexity of approximating zeros of polynomials
• Computational complexity. On the geometry of polynomials and a theory of cost. I
• Algebraic complexity of computing polynomial zeros
• scientific article; zbMATH DE number 3928209
• scientific article; zbMATH DE number 3976214

Cites work

• A PL homotopy for finding all the roots of a polynomial
• scientific article; zbMATH DE number 3567160 (Why is no real title available?)
• The fundamental theorem of algebra and complexity theory

Cited in

(17)

• Optimal solution of nonlinear equations
• On the worst-case arithmetic complexity of approximating zeros of polynomials
• 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
• Horner versus Holdred: An episode in the history of root computation
• On the complexity of a PL homotopy algorithm for zeros of polynomials
• Fine costs for Euclid's algorithm on polynomials and Farey maps
• Relative performance evaluation for dynamic contracts in a large competitive market
• Computers and the Multiplicity of Polynomial Roots
• scientific article; zbMATH DE number 3880014 (Why is no real title available?)
• On the cost of approximating all roots of a complex polynomial
• scientific article; zbMATH DE number 3928209 (Why is no real title available?)
• On the efficiency of algorithms of analysis
• Computational complexity. On the geometry of polynomials and a theory of cost. I
• How to be sure of finding a root of a complex polynomial using Newton's method
• Finding cactus roots in polynomial time

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3330394)