Re: Real roots of a polynomial

[Charles Greathouse <charles.greathouse@case.edu>]

At least add this to TODO?

Charles Greathouse
Analyst/Programmer
Case Western Reserve University

On Fri, Oct 19, 2012 at 7:24 AM, Karim Belabas
<Karim.Belabas@math.u-bordeaux1.fr> wrote:
> * Bill Allombert [2012-10-19 10:30]:
>> 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
>
> Descartes's rule and Sturm sequences. One uses translations P -> P(X+1) and
> shifts P -> P(2^i X), the other uses derivatives and Euclidean divisions.
>
>> 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.
>
> I have seen it. I even have the email Guillaume Hanrot sent me
> (on Apr 28th, 1999) to announce a quick-and-dirty implementation
> that was already 4 times faster than polsturm on poltchebi(100),
> an infinitely faster on larger examples.
>
> But I lost the code itself. :-(
>
> The standard references (for polynomials with integer coefficients) are
> Section 3 of
>
>   http://hal.inria.fr/inria-00072518/   (Rouiller-Zimmermann)
>
> and
>
>   http://www.springerlink.com/content/c70468755x403481/   (Tsigarisas-Emiris)
>   http://www-polsys.lip6.fr/~elias/files//te-esa-2006.pdf
>
> The latter apparently performs better in practice. Anybody interested in
> implementing (one or both of) them ?
>
> Cheers,
>
>     K.B.
> --
> Karim Belabas, IMB (UMR 5251)  Tel: (+33) (0)5 40 00 26 17
> Universite Bordeaux 1          Fax: (+33) (0)5 40 00 69 50
> 351, cours de la Liberation    http://www.math.u-bordeaux1.fr/~belabas/
> F-33405 Talence (France)       http://pari.math.u-bordeaux1.fr/  [PARI/GP]
> `