Karim Belabas on Fri, 19 Oct 2012 13:24:40 +0200 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: Real roots of a polynomial |
* 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] `