Near optimal subdivision algorithms for real root isolation

DOI10.1016/j.jsc.2016.11.004zbMath1375.65064OpenAlexW2555112576MaRDI QIDQ2628307

Vikram Sharma, Prashant Batra

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

zbMATH Keywords

Newton diagramsubdivision algorithmsSturm sequencescontinuous amortizationreal root isolationinterval-arithmeticintegral analysisDescartes's rule of signs

Mathematics Subject Classification ID

Interval and finite arithmetic (65G30) Numerical computation of roots of polynomial equations (65H04)

Uses Software

• ISOLATE

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