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/

Global: Zendy Plus annual

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

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We describe a subdivision algorithm for isolating the complex roots of apolynomial $F\in\mathbb{C}[x]$. Given an oracle that provides approximations ofeach of the coefficients of $F$ to any absolute error bound and given anarbitrary square $\mathcal{B}$ in the complex plane containing only simpleroots of $F$, our algorithm returns disjoint isolating disks for the roots of$F$ in $\mathcal{B}$. Our complexity analysis bounds the absolute error towhich the coefficients of $F$ have to be provided, the total number ofiterations, and the overall bit complexity. It further shows that thecomplexity of our algorithm is controlled by the geometry of the roots in anear neighborhood of the input square $\mathcal{B}$, namely, the number ofroots, their absolute values and pairwise distances. The number of subdivisionsteps is near-optimal. For the \emph{benchmark problem}, namely, to isolate allthe roots of a polynomial of degree $n$ with integer coefficients of bit sizeless than $\tau$, our algorithm needs $\tilde O(n^3+n^2\tau)$ bit operations,which is comparable to the record bound of Pan (2002). It is the first timethat such a bound has been achieved using subdivision methods, and independentof divide-and-conquer techniques such as Sch\"onhage's splitting circletechnique. Our algorithm uses the quadtree construction of Weyl (1924) with twokey ingredients: using Pellet's Theorem (1881) combined with Graeffe iteration,we derive a "soft-test" to count the number of roots in a disk. UsingSchr\"oder's modified Newton operator combined with bisection, in a forminspired by the quadratic interval method from Abbot (2006), we achievequadratic convergence towards root clusters. Relative to the divide-conqueralgorithms, our algorithm is quite simple with the potential of beingpractical. This paper is self-contained: we provide pseudo-code for allsubroutines used by our algorithm.

A Near-Optimal Subdivision Algorithm for Complex Root Isolation based on the Pellet Test and Newton Iteration