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

Given a polynomial $p$ of degree $d$ and a bound $\kappa$ on a conditionnumber of $p$, we present the first root-finding algorithms that return all itsreal and complex roots with a number of bit operations quasi-linear in $d\log^2(\kappa)$. More precisely, several condition numbers can be defineddepending on the norm chosen on the coefficients of the polynomial. Let $p(x) =\sum\_{k=0}^d a\_k x^k = \sum\_{k=0}^d \sqrt{\binom d k} b\_k x^k$. We call thecondition number associated with a perturbation of the $a\_k$ the hyperboliccondition number $\kappa\_h$, and the one associated with a perturbation of the$b\_k$ the elliptic condition number $\kappa\_e$. For each of these conditionnumbers, we present algorithms that find the real and the complex roots of $p$in $O\left(d\log^2(d\kappa)\ \text{polylog}(\log(d\kappa))\right)$ bitoperations.Our algorithms are well suited for random polynomials since$\kappa\_h$ (resp. $\kappa\_e$) is bounded by a polynomial in $d$ with highprobability if the $a\_k$ (resp. the $b\_k$) are independent, centered Gaussianvariables of variance $1$.

Fast real and complex root-finding methods for well-conditioned polynomials