Re: Real roots of a polynomial

[Karim Belabas <Karim.Belabas@math.u-bordeaux1.fr>]

* 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]
`