Abstract
We show how to compute Hongs bound for the absolute positiveness of a polynomial in d variables with maximum degree in O(nlogdn) time, where n is the number of non-zero coefficients. For the univariate case, we give a linear time algorithm. As a consequence, the time bounds for the continued fraction algorithm for real root isolation improve by a factor of δ.
Original language | English (US) |
---|---|
Pages (from-to) | 677-683 |
Number of pages | 7 |
Journal | Journal of Symbolic Computation |
Volume | 45 |
Issue number | 6 |
DOIs | |
State | Published - Jun 2010 |
Keywords
- Absolute positiveness
- Geometric computing
- Hongs bound
- Multivariate polynomials
ASJC Scopus subject areas
- Algebra and Number Theory
- Computational Mathematics