Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
1991
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/math/9201280 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908600109105152 |
|---|---|
| author | Kim, Myong-Hi Sutherland, Scott |
| author_facet | Kim, Myong-Hi Sutherland, Scott |
| contents | 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ε|}$. At the present time (1993), this complexity is the best known in terms of the degree. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_math_9201280 |
| institution | arXiv |
| publishDate | 1991 |
| record_format | arxiv |
| spellingShingle | Polynomial root-finding algorithms and branched covers Kim, Myong-Hi Sutherland, Scott Dynamical Systems Numerical Analysis 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ε|}$. At the present time (1993), this complexity is the best known in terms of the degree. |
| title | Polynomial root-finding algorithms and branched covers |
| topic | Dynamical Systems Numerical Analysis |
| url | https://arxiv.org/abs/math/9201280 |