A Fast Parallel Algorithm for Determining All Roots of a Polynomial with Real Roots

DOI10.1137/0217069zbMath0663.68047OpenAlexW2003933590MaRDI QIDQ3814803

Prasoon Tiwari, Michael Ben-Or, Dexter Kozen, Ephraim Feig

Publication date: 1988

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0217069

zbMATH Keywords

numerical integrationSturm sequenceparallel algorithmsroot separationcomplexity classapproximations of zeroespolynomials roots

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Polynomials in real and complex fields: location of zeros (algebraic theorems) (12D10) Numerical approximation and computational geometry (primarily algorithms) (65D99)

Related Items

Specified precision polynomial root isolation is in NC, European Summer Meeting of the Association for Symbolic Logic, Optimal and nearly optimal algorithms for approximating polynomial zeros, Approximating complex polynomial zeros: modified Weyl's quadtree construction and improved Newton's iteration., Root finding with threshold circuits, Efficient parallel factorization and solution of structured and unstructured linear systems, A lower bound for the shortest path problem, Simple algorithms for approximating all roots of a polynomial with real roots, Computation of equilibria in noncooperative games