Simple algorithms for approximating all roots of a polynomial with real roots

DOI10.1016/0885-064X(90)90032-9MaRDI QIDQ757494zbMATH OpenOpenAlexFDO

Authors Michael Ben-Or, Prasoon Tiwari

Publication date 1990

Published in Journal of Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0885-064x(90)90032-9

zbMATH Keywords

orthogonal polynomialspolynomialparallel implementationSturm sequencereal rootssequential algorithmextended Euclidean scheme

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Real polynomials: location of zeros (26C10) Polynomials in real and complex fields: location of zeros (algebraic theorems) (12D10)

Recommendations

• A Fast Parallel Algorithm for Determining All Roots of a Polynomial with Real Roots
• Specified precision polynomial root isolation is in NC
• scientific article; zbMATH DE number 3846864
• Efficient real root approximation
• On the Complexity of Polynomial Zeros

Cites work

• scientific article; zbMATH DE number 3445421 (Why is no real title available?)
• scientific article; zbMATH DE number 3383473 (Why is no real title available?)
• A Fast Parallel Algorithm for Determining All Roots of a Polynomial with Real Roots
• An inequality for the discriminant of a polynomial
• On computing the determinant in small parallel time using a small number of processors
• On the computational power of pushdown automata
• On the worst-case arithmetic complexity of approximating zeros of polynomials
• Subresultants and Reduced Polynomial Remainder Sequences

Cited in

(14)

• Parallel computation of polynomial GCD and some related parallel computations over abstract fields
• Specified precision polynomial root isolation is in NC
• Efficient parallel factorization and solution of structured and unstructured linear systems
• Optimal and nearly optimal algorithms for approximating polynomial zeros
• Generalized updating problems and computation of the eigenvalues of rational Toeplitz matrices
• Real polynomial root-finding by means of matrix and polynomial iterations
• Practical improvement of the divide-and-conquer eigenvalue algorithms
• Numerical computation of polynomial zeros by means of Aberth's method
• A Fast Parallel Algorithm for Determining All Roots of a Polynomial with Real Roots
• Nearly optimal refinement of real roots of a univariate polynomial
• A new fast root-finder for black box polynomials
• Approximating complex polynomial zeros: modified Weyl's quadtree construction and improved Newton's iteration.
• When Newton meets Descartes
• Finding polynomial roots: A fast algorithm convergent on the complex plane

This page was built for publication: Simple algorithms for approximating all roots of a polynomial with real roots

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