Univariate polynomial real root isolation: Continued Fractions revisited

Details Univariate polynomial real root isolation: Continued Fractions revisited Univariate polynomial real root isolation: Continued Fractions revisited

2006-04-17

arxiv.org/abs/cs/0604066v1

Computer Science

Symbolic Computation

12 pages

Scientific paper

We present algorithmic, complexity and implementation results concerning real root isolation of integer univariate polynomials using the continued fraction expansion of real algebraic numbers. One motivation is to explain the method's good performance in practice. We improve the previously known bound by a factor of $d \tau$, where $d$ is the polynomial degree and $\tau$ bounds the coefficient bitsize, thus matching the current record complexity for real root isolation by exact methods. Namely, the complexity bound is $\sOB(d^4 \tau^2)$ using the standard bound on the expected bitsize of the integers in the continued fraction expansion. We show how to compute the multiplicities within the same complexity and extend the algorithm to non square-free polynomials. Finally, we present an efficient open-source \texttt{C++} implementation in the algebraic library \synaps, and illustrate its efficiency as compared to other available software. We use polynomials with coefficient bitsize up to 8000 and degree up to 1000.

Affiliated with

Also associated with

No associations

Rating

Univariate polynomial real root isolation: Continued Fractions revisited does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Univariate polynomial real root isolation: Continued Fractions revisited, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Univariate polynomial real root isolation: Continued Fractions revisited will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-482818