Almost tight recursion tree bounds for the Descartes method
From MaRDI portal
Publication:2958973
DOI10.1145/1145768.1145786zbMath1356.65120MaRDI QIDQ2958973
Vikram Sharma, Chee-Keng Yap, Arno Eigenwillig
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
Bernstein basis; polynomial real root isolation; Descartes rule of signs; Davenport-Mahler bound; Descartes method
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 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, 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, Finding the Growth Rate of a Regular of Context-Free Language in Polynomial Time, On the Complexity of Reliable Root Approximation
