Charles Greathouse on Fri, 19 Oct 2012 15:26:00 +0200 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: Real roots of a polynomial |
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] > `