Bill Allombert on Fri, 19 Oct 2012 10:30:27 +0200


[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Re: Real roots of a polynomial


On Fri, Oct 19, 2012 at 10:10:47AM +0200, Loïc Grenié wrote:
>     Hello pari developers,
> 
>     does anybody know any way to obtain the real roots of a
>   polynomial without computing the non-real ones (potentially
>   saving time) ? A quick and dirty gp script using Sturm sequence
>   and Legendre bounds was 35% faster than polroots on a
>   (single) sample polynomial. Is there any secret pari function
>   GEN __get_real_roots_of_polynomial_really_fast(GEN P) that
>   I have not noticed ? If it helps, I only need the roots between two
>   bounds.

There basically two family of algorithms for that task, Descartes rules and Uspensky,
which are basically equivalent in complexity if you do not the distribution of your
polynomials.

A persistent rumor in Nancy suggests the existence of an implementation of Uspensky
algorithm for libpari, but I never seen it.

Cheers,
Bill.