Near optimal subdivision algorithms for real root isolation
From MaRDI portal
Publication:2628307
DOI10.1016/j.jsc.2016.11.004zbMath1375.65064OpenAlexW2555112576MaRDI QIDQ2628307
Publication date: 1 June 2017
Published in: Journal of Symbolic Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jsc.2016.11.004
Newton diagramsubdivision algorithmsSturm sequencescontinuous amortizationreal root isolationinterval-arithmeticintegral analysisDescartes's rule of signs
Interval and finite arithmetic (65G30) Numerical computation of roots of polynomial equations (65H04)
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Continuous amortization and extensions: with applications to bisection-based root isolation
- Computing real roots of real polynomials
- Univariate polynomials: Nearly optimal algorithms for numerical factorization and root-finding
- On the worst-case arithmetic complexity of approximating zeros of polynomials
- Efficient isolation of polynomial's real roots.
- Optimal and nearly optimal algorithms for approximating polynomial zeros
- Approximating complex polynomial zeros: modified Weyl's quadtree construction and improved Newton's iteration.
- From approximate factorization to root isolation with application to cylindrical algebraic decomposition
- On location and approximation of clusters of zeros of analytic functions
- An efficient algorithm for the complex roots problem
- Near Optimal Subdivision Algorithms for Real Root Isolation
- Almost tight recursion tree bounds for the Descartes method
- Computing clustered close-roots of univariate polynomials
- The location of the zeros of the higher order derivatives of a polynomial
- When Newton meets Descartes
- Near optimal tree size bounds on a simple real root isolation algorithm
- Quadratic interval refinement for real roots
- Analytic Root Clustering: A Complete Algorithm Using Soft Zero Tests
This page was built for publication: Near optimal subdivision algorithms for real root isolation