We report an ongoing work on clustering algorithms for complex roots of a
univariate polynomial $p$ of degree $d$ with real or complex coefficients. As
in their previous best subdivision algorithms our root-finders are robust even
for multiple roots of a polynomial given by a black box for the approximation
of its coefficients, and their complexity decreases at least proportionally to
the number of roots in a region of interest (ROI) on the complex plane, such as
a disc or a square, but we greatly strengthen the main ingredient of the
previous algorithms. Namely our new counting test essentially amounts to the
evaluation of a polynomial $p$ and its derivative $p'$, which is a major
benefit, e.g., for sparse polynomials $p$. Moreover with evaluation at about
$\log(d)$ points (versus the previous record of order $d$) we output correct
number of roots in a disc whose contour has no roots of $p$ nearby. Moreover we
greatly soften the latter requirement versus the known subdivision algorithms.
Our second and less significant...

more |
pdf
| html
ccluster is a certified numerical software for clustering the roots of a univariate polynomial which coefficients are complex algebraic numbers

None.

Sample Sizes : None.

Authors: 2

Total Words: 6904

Unqiue Words: 1864

Assert is a website where the best academic papers on arXiv (computer science, math, physics), bioRxiv (biology), BITSS (reproducibility), EarthArXiv (earth science), engrXiv (engineering), LawArXiv (law), PsyArXiv (psychology), SocArXiv (social science), and SportRxiv (sport research) bubble to the top each day.

Papers are scored (in real-time) based on how verifiable they are (as determined by their Github repos) and how interesting they are (based on Twitter).

To see top papers, follow us on twitter @assertpub_ (arXiv), @assert_pub (bioRxiv), and @assertpub_dev (everything else).

To see beautiful figures extracted from papers, follow us on Instagram.

*Tracking 223,556 papers.*

Sort results based on if they are interesting or reproducible.

Interesting

Reproducible