Almost tight recursion tree bounds for the Descartes method

DOI10.1145/1145768.1145786MaRDI QIDQ2958973zbMATH OpenOpenAlexFDO

Authors Arno Eigenwillig, Vikram Sharma, Chee K. 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 basisDavenport-Mahler boundDescartes methodDescartes rule of signspolynomial real root isolation

Mathematics Subject Classification ID

Numerical computation of roots of polynomial equations (65H04) Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30)

Recommendations

• New bounds for the Descartes method
• On the complexity of the Descartes method when using approximate arithmetic
• Computer Algebra in Scientific Computing
• Efficient isolation of polynomial's real roots.
• When Newton meets Descartes

Cited in

(28)

• 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
• New bounds for the Descartes method
• On the complexity of real root isolation using continued fractions
• Near optimal subdivision algorithms for real root isolation
• Continuous amortization and extensions: with applications to bisection-based root isolation
• Finding the Growth Rate of a Regular of Context-Free Language in Polynomial Time
• On the Complexity of Reliable Root Approximation
• 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
• On multiple roots in Descartes' rule and their distance to roots of higher derivatives
• Certificates of positivity in the Bernstein basis

This page was built for publication: Almost tight recursion tree bounds for the Descartes method

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