English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

We introduce a new algorithm denoted DSC2 to isolate the real roots of aunivariate square-free polynomial f with integer coefficients. The algorithmiteratively subdivides an initial interval which is known to contain all realroots of f. The main novelty of our approach is that we combine Descartes' Ruleof Signs and Newton iteration. More precisely, instead of using a fixedsubdivision strategy such as bisection in each iteration, a Newton step basedon the number of sign variations for an actual interval is considered, and,only if the Newton step fails, we fall back to bisection. Following thisapproach, our analysis shows that, for most iterations, we can achievequadratic convergence towards the real roots. In terms of complexity, ourmethod induces a recursion tree of almost optimal size O(nlog(n tau)), where ndenotes the degree of the polynomial and tau the bitsize of its coefficients.The latter bound constitutes an improvement by a factor of tau upon allexisting subdivision methods for the task of isolating the real roots. Inaddition, we provide a bit complexity analysis showing that DSC2 needs only\tilde{O}(n^3tau) bit operations to isolate all real roots of f. This matchesthe best bound known for this fundamental problem. However, in comparison tothe much more involved algorithms by Pan and Sch\"onhage (for the task ofisolating all complex roots) which achieve the same bit complexity, DSC2focuses on real root isolation, is very easy to access and easy to implement.

When Newton meets Descartes: A Simple and Fast Algorithm to Isolate the Real Roots of a Polynomial