Almost tight recursion tree bounds for the Descartes method

DOI10.1145/1145768.1145786zbMath1356.65120MaRDI QIDQ2958973

Vikram Sharma, Arno Eigenwillig, Chee-Keng Yap

Publication date: 3 February 2017

Published in: Proceedings of the 2006 international symposium on Symbolic and algebraic computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1145768.1145786

zbMATH Keywords

Bernstein basis; polynomial real root isolation; Descartes rule of signs; Davenport-Mahler bound; Descartes method

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68W30: Symbolic computation and algebraic computation

65H04: Numerical computation of roots of polynomial equations

Related Items

Continuous amortization and extensions: with applications to bisection-based root isolation, Improved bounds for the CF algorithm, On the computing time of the continued fractions method, Computing real roots of real polynomials, On the maximum computing time of the bisection method for real root isolation, On continued fraction expansion of real roots of polynomial systems, complexity and condition numbers, A deterministic algorithm for isolating real roots of a real polynomial, On the topology of real algebraic plane curves, A general approach to isolating roots of a bitstream polynomial, SqFreeEVAL: An (almost) optimal real-root isolation algorithm, Topology and arrangement computation of semi-algebraic planar curves, Certificates of positivity in the Bernstein basis, Subdivision methods for solving polynomial equations, On the asymptotic and practical complexity of solving bivariate systems over the reals, Revisiting the problem of zeros of univariate scalar Béziers, Univariate real root isolation in an extension field and applications, Sampling polynomial trajectories for LTL verification, The complexity of subdivision for diameter-distance tests, Separation bounds for polynomial systems, On the Davenport-Mahler bound, Complexity of real root isolation using continued fractions, On the complexity of the Descartes method when using approximate arithmetic, On the complexity of real root isolation using continued fractions, Near optimal subdivision algorithms for real root isolation, Finding the Growth Rate of a Regular of Context-Free Language in Polynomial Time, On the Complexity of Reliable Root Approximation