Almost tight recursion tree bounds for the Descartes method
From MaRDI portal
Publication:2958973
DOI10.1145/1145768.1145786zbMath1356.65120OpenAlexW2158622794MaRDI 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
Bernstein basispolynomial real root isolationDescartes rule of signsDavenport-Mahler boundDescartes method
Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Numerical computation of roots of polynomial equations (65H04)
Related Items
On the Davenport-Mahler bound ⋮ Continuous amortization and extensions: with applications to bisection-based root isolation ⋮ Near optimal subdivision algorithms for real root isolation ⋮ Revisiting the problem of zeros of univariate scalar Béziers ⋮ Complexity of real root isolation using continued fractions ⋮ A deterministic algorithm for isolating real roots of a real polynomial ⋮ Improved bounds for the CF algorithm ⋮ The complexity of subdivision for diameter-distance tests ⋮ Separation bounds for polynomial systems ⋮ On the topology of real algebraic plane curves ⋮ On the computing time of the continued fractions method ⋮ Finding the Growth Rate of a Regular of Context-Free Language in Polynomial Time ⋮ On the complexity of the Descartes method when using approximate arithmetic ⋮ A general approach to isolating roots of a bitstream polynomial ⋮ SqFreeEVAL: An (almost) optimal real-root isolation algorithm ⋮ Certificates of positivity in the Bernstein basis ⋮ Computing real roots of real polynomials ⋮ On the maximum computing time of the bisection method for real root isolation ⋮ On the complexity of real root isolation using continued fractions ⋮ Univariate real root isolation in an extension field and applications ⋮ On continued fraction expansion of real roots of polynomial systems, complexity and condition numbers ⋮ Topology and arrangement computation of semi-algebraic planar curves ⋮ Subdivision methods for solving polynomial equations ⋮ Sampling polynomial trajectories for LTL verification ⋮ On the asymptotic and practical complexity of solving bivariate systems over the reals ⋮ On the Complexity of Reliable Root Approximation
