On Solving Fewnomials Over Intervals in Fewnomial Time
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2001
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909853317857280 |
|---|---|
| author | Rojas, J. Maurice Ye, Yinyu |
| author_facet | Rojas, J. Maurice Ye, Yinyu |
| contents | Let f be a degree D univariate polynomial with real coefficients and exactly m monomial terms. We show that in the special case m=3 we can approximate within eps all the roots of f in the interval [0,R] using just O(log(D)log(Dlog(R/eps))) arithmetic operations. In particular, we can count the number of roots in any bounded interval using just O(log^2 D) arithmetic operations. Our speed-ups are significant and near-optimal: The asymptotically sharpest previous complexity upper bounds for both problems were super-linear in D, while our algorithm has complexity close to the respective complexity lower bounds. We also discuss conditions under which our algorithms can be extended to general m, and a connection to a real analogue of Smale's 17th Problem. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_math_0106225 |
| institution | arXiv |
| publishDate | 2001 |
| record_format | arxiv |
| spellingShingle | On Solving Fewnomials Over Intervals in Fewnomial Time Rojas, J. Maurice Ye, Yinyu Numerical Analysis Algebraic Geometry Let f be a degree D univariate polynomial with real coefficients and exactly m monomial terms. We show that in the special case m=3 we can approximate within eps all the roots of f in the interval [0,R] using just O(log(D)log(Dlog(R/eps))) arithmetic operations. In particular, we can count the number of roots in any bounded interval using just O(log^2 D) arithmetic operations. Our speed-ups are significant and near-optimal: The asymptotically sharpest previous complexity upper bounds for both problems were super-linear in D, while our algorithm has complexity close to the respective complexity lower bounds. We also discuss conditions under which our algorithms can be extended to general m, and a connection to a real analogue of Smale's 17th Problem. |
| title | On Solving Fewnomials Over Intervals in Fewnomial Time |
| topic | Numerical Analysis Algebraic Geometry |
| url | https://arxiv.org/abs/math/0106225 |