A Fast Parallel Algorithm for Determining All Roots of a Polynomial with Real Roots
From MaRDI portal
Publication:3814803
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
numerical integrationSturm sequenceparallel algorithmsroot separationcomplexity classapproximations of zeroespolynomials roots
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