Polynomial root-finding algorithms and branched covers

From WebRef.org
Revision as of 15:47, 13 July 2021 by Webref (talk | contribs) (Created page with "Myong-Hi Kim, Scott Sutherland We construct a family of root-finding algorithms which exploit the branched covering structure of a polynomial of degree d with a path-lifting...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigationJump to search

Myong-Hi Kim, Scott Sutherland

We construct a family of root-finding algorithms which exploit the branched covering structure of a polynomial of degree d with a path-lifting algorithm for finding individual roots. In particular, the family includes an algorithm that computes an ϵ-factorization of the polynomial which has an arithmetic complexity of $\Order{d^2(\log d)^2 + d(\log d)^2|\log\epsilon|}$. At the present time (1993), this complexity is the best known in terms of the degree.

https://arxiv.org/abs/math/9201280


Sponsor: Shop the mattress

Featuring Angelfish