Re: nffactor() slowdown

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

On Wed, 19 Jun 2002, Igor Schein wrote:
> On Wed, Jun 19, 2002 at 05:33:58PM +0200, Karim BELABAS wrote:
> > On Tue, 18 Jun 2002, Igor Schein wrote:
> > > I compared nffactor's speed between 2.2.3 and 2.2.4, and latter
> > > is on average 10-25% slower on the type of polynomials I tried - large
> > > Galois polynomials over cyclotomic or quarternion fields.
[...]
> > Can you post a few representative examples ?
>
> You can use this one, after the bug is fixed, or any of the 2 I've
> posted during the last week on the list:
>
> ? nffactor(nfinit(polcyclo(13,y)),x^72-291*x^70+168*x^69+40380*x^68-48588*x^67-3528919*x^66+6672120*x^65+215657160*x^64-575538144*x^63-9642387423*x^62+34735086786*x^61+318475831783*x^60-1543992152304*x^59-7526047084203*x^58+51709921323996*x^57+110268119466273*x^56-1306863903654948*x^55-197687339387338*x^54+24340617020480994*x^53-37674206381844006*x^52-309388136734870296*x^51+1097175021601270233*x^50+1965430743178095924*x^49-17057741307681944498*x^48+12695705864721864408*x^47+149941210123858078557*x^46-449449010694960248724*x^45-360137445013361079753*x^44+4743771886303072354536*x^43-7957480107528139931362*x^42-20006312987061736459890*x^41+103127662005251951018025*x^40-57922725775374790826892*x^39-575374977336477060878406*x^38+1141042155363070337681952*x^37+2107623272811930164219492*x^36-8555883275792119671168984*x^35-6622038332271478648217502*x^34+67788499073804904961005264*x^33-62194621346216574281355513*x^32-298503076979390816950994616*x^31+935868776923024509133161567*x^30-602191893688026944562387144*x^29-2378403718028116295265005703*x^28+7144715267789671188060423636*x^27-8264313767410946129053876314*x^26-2988303993119955116599622124*x^25+36320303706133493815706370331*x^24-93405543373036036850518472592*x^23+137892731303549623166716872621*x^22-73374564495372153466268524626*x^21-180690507689854149951443988039*x^20+506199649638427572646328975856*x^19-511453665473658325356669209047*x^18-183193264910244539106552118338*x^17+1423840911419731272911578335897*x^16-2367314022969857609246689985844*x^15+2236677523353346112926136338695*x^14-1548489683091587051973217338168*x^13+2105049137205776145162583648404*x^12-4754348311294629767834593856064*x^11+7567806891220394207855512254933*x^10-7605431066578089163623568649610*x^9+3882625664788999249342771140339*x^8+1356469287400668040516453202076*x^7-3841355512345259545848813224621*x^6+2330504083587501732658867007532*x^5-169172628407290891217225606775*x^4-398965703199322569698936377044*x^3+198978398979453484569202793808*x^2-60597282938946837445378411698*x+12280639561039083425818958713)
>   ***   bug in LLL_cmbf [no factor], please report

I checked and rechecked my bounds for a couple of hours, and eventually
noticed I was reducing a (subtly) wrong lattice for which my bound was
slightly off. I need to do a number of incremental base changes, and
bidirectional p-adic truncation [ something like (x % p^a) \/ p^b ], the
operations being _nearly_ commutative (the lattice is always correct, the
bound changes a little). I was doing them in the wrong order.

So I fixed the lattice, kept the bound, and the "[no factor]" problem above
disappears.

About the slowdown, this is definitely due to the new factor bound,
which is much worse for your class of examples than the old one (nearly the
square of the previous bound). Have to put back Beauzamy's bound, and take
the minimum of the 2 bounds. Will do it tomorrow.

In any case, thanks for a very nice counter example !

    Karim.
-- 
Karim Belabas                    Tel: (+33) (0)1 69 15 57 48
Dép. de Mathematiques, Bat. 425  Fax: (+33) (0)1 69 15 60 19
Université Paris-Sud             Email: Karim.Belabas@math.u-psud.fr
F-91405 Orsay (France)           http://www.math.u-psud.fr/~belabas/
--
PARI/GP Home Page: http://www.parigp-home.de/