Simple algorithms for approximating all roots of a polynomial with real roots
From MaRDI portal
Publication:757494
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
orthogonal polynomialsSturm sequencesequential algorithmpolynomialparallel implementationreal rootsextended Euclidean scheme
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
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
