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

DOI10.1016/0885-064X(90)90032-9zbMath0723.12011OpenAlexW2039897960MaRDI QIDQ757494

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 polynomialsSturm sequencesequential algorithmpolynomialparallel implementationreal rootsextended Euclidean scheme

Mathematics Subject Classification ID

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

Related Items (10)

Specified precision polynomial root isolation is in NC ⋮ Parallel computation of polynomial GCD and some related parallel computations over abstract fields ⋮ Generalized updating problems and computation of the eigenvalues of rational Toeplitz matrices ⋮ Optimal and nearly optimal algorithms for approximating polynomial zeros ⋮ Nearly optimal refinement of real roots of a univariate polynomial ⋮ Approximating complex polynomial zeros: modified Weyl's quadtree construction and improved Newton's iteration. ⋮ Numerical computation of polynomial zeros by means of Aberth's method ⋮ Practical improvement of the divide-and-conquer eigenvalue algorithms ⋮ Efficient parallel factorization and solution of structured and unstructured linear systems ⋮ Real polynomial root-finding by means of matrix and polynomial iterations

Cites Work

• Unnamed Item
• Unnamed Item
• On computing the determinant in small parallel time using a small number of processors
• On the worst-case arithmetic complexity of approximating zeros of polynomials
• An inequality for the discriminant of a polynomial
• On the computational power of pushdown automata
• A Fast Parallel Algorithm for Determining All Roots of a Polynomial with Real Roots
• Subresultants and Reduced Polynomial Remainder Sequences

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