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 present a new data structure to approximate accurately and efficiently apolynomial $f$ of degree $d$ given as a list of coefficients. Its propertiesallow us to improve the state-of-the-art bounds on the bit complexity for theproblems of root isolation and approximate multipoint evaluation. This datastructure also leads to a new geometric criterion to detect ill-conditionedpolynomials, implying notably that the standard condition number of the zerosof a polynomial is at least exponential in the number of roots of modulus lessthan $1/2$ or greater than $2$.Given a polynomial $f$ of degree $d$ with$\|f\|_1 \leq 2^\tau$ for $\tau \geq 1$, isolating all its complex roots orevaluating it at $d$ points can be done with a quasi-linear number ofarithmetic operations. However, considering the bit complexity, thestate-of-the-art algorithms require at least $d^{3/2}$ bit operations even forwell-conditioned polynomials and when the accuracy required is low. Given apositive integer $m$, we can compute our new data structure and evaluate $f$ at$d$ points in the unit disk with an absolute error less than $2^{-m}$ in$\widetilde O(d(\tau+m))$ bit operations, where $\widetilde O(\cdot)$ meansthat we omit logarithmic factors. We also show that if $\kappa$ is the absolutecondition number of the zeros of $f$, then we can isolate all the roots of $f$in $\widetilde O(d(\tau + \log \kappa))$ bit operations. Moreover, ouralgorithms are simple to implement. For approximating the complex roots of apolynomial, we implemented a small prototype in \verb|Python/NumPy| that is anorder of magnitude faster than the state-of-the-art solver \verb/MPSolve/ forhigh degree polynomials with random coefficients.

New data structure for univariate polynomial approximation and applications to root isolation, numerical multipoint evaluation, and other problems