Near optimal subdivision algorithms for real root isolation

DOI10.1016/J.JSC.2016.11.004MaRDI QIDQ2628307zbMATH OpenOpenAlexFDO

Authors Prashant Batra, Vikram Sharma

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

continuous amortizationDescartes's rule of signsintegral analysisinterval-arithmeticNewton diagramreal root isolationSturm sequencessubdivision algorithms

Mathematics Subject Classification ID

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

Recommendations

• Near optimal subdivision algorithms for real root isolation
• Empirical study of an evaluation-based subdivision algorithm for complex root isolation
• A near-optimal subdivision algorithm for complex root isolation based on the Pellet test and Newton iteration
• A simple but exact and efficient algorithm for complex root isolation
• On the maximum computing time of the bisection method for real root isolation
• Effective subdivision algorithm for isolating zeros of real systems of equations, with complexity analysis
• Improved subdivision scheme for the root computation of univariate polynomial equations
• An improved algorithm for real root isolation of univariate polynomials
• Near optimal tree size bounds on a simple real root isolation algorithm
• Acceleration of subdivision root-finding for sparse polynomials

Cites work

• Almost tight recursion tree bounds for the Descartes method
• An efficient algorithm for the complex roots problem
• Analytic root clustering: a complete algorithm using soft zero tests
• Approximating complex polynomial zeros: modified Weyl's quadtree construction and improved Newton's iteration.
• Computational geometry. Algorithms and applications.
• Computing clustered close-roots of univariate polynomials
• Computing real roots of real polynomials
• Continuous amortization and extensions: with applications to bisection-based root isolation
• Efficient isolation of polynomial's real roots.
• From approximate factorization to root isolation with application to cylindrical algebraic decomposition
• scientific article; zbMATH DE number 1157659 (Why is no real title available?)
• scientific article; zbMATH DE number 1820648 (Why is no real title available?)
• scientific article; zbMATH DE number 1859224 (Why is no real title available?)
• Near optimal subdivision algorithms for real root isolation
• Near optimal tree size bounds on a simple real root isolation algorithm
• On location and approximation of clusters of zeros of analytic functions
• On the worst-case arithmetic complexity of approximating zeros of polynomials
• Optimal and nearly optimal algorithms for approximating polynomial zeros
• Quadratic interval refinement for real roots
• The location of the zeros of the higher order derivatives of a polynomial
• Univariate polynomials: Nearly optimal algorithms for numerical factorization and root-finding
• When Newton meets Descartes

Cited in

(9)

• A near-optimal subdivision algorithm for complex root isolation based on the Pellet test and Newton iteration
• Continuous amortization and extensions: with applications to bisection-based root isolation
• Empirical study of an evaluation-based subdivision algorithm for complex root isolation
• Near optimal subdivision algorithms for real root isolation
• On the maximum computing time of the bisection method for real root isolation
• Effective subdivision algorithm for isolating zeros of real systems of equations, with complexity analysis
• Near optimal tree size bounds on a simple real root isolation algorithm
• Complexity of a root clustering algorithm for holomorphic functions
• SqFreeEVAL: An (almost) optimal real-root isolation algorithm

Describes a project that uses

Uses Software

• ISOLATE

This page was built for publication: Near optimal subdivision algorithms for real root isolation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2628307)