Igor Schein on Mon, 13 Oct 2003 19:14:16 -0400 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: polredabs failure |
On Mon, Oct 13, 2003 at 05:42:38PM +0200, Karim BELABAS wrote: > On Sun, 12 Oct 2003, Igor Schein wrote: > > On Fri, Oct 10, 2003 at 08:08:00PM +0200, Karim BELABAS wrote: > >> On Fri, 10 Oct 2003, Igor Schein wrote: > > Latest changes broke it again: > > > > ? p=x^16-4*x^15+8*x^14-8*x^13+6*x^12-16*x^11+40*x^10-32*x^9-50*x^8+160*x^7-176*x^6+40*x^5+140*x^4-192*x^3+112*x^2-32*x+4; > > ? v=polredabs(p,4); > > ? vector(#v,k,#polredabs(v[k],4)) > > [22, 21, 24, 24, 24, 20, 24, 12, 20, 12, 20, 24] > > > > The correct answer is vector(24,x,24). > > Couldn't reproduce this, since I had changed it again in the meantime... I > rewrote the whole thing according to an age-old project of mine: enumerating > points by (roughly) increasing norms. I did not try to be efficient, this > time, only to get it right. I don't know if it's too early to talk about efficiency yet, but for the following polynomial { x^32 + 160*x^30 + 10592*x^28 + 380240*x^26 + 8223880*x^24 + 113613696*x^22 + 1038843456*x^20 + 6414739680*x^18 + 26951021784*x^16 + 76644143232*x^14 + 1 44482787456*x^12 + 172572281280*x^10 + 118940935456*x^8 + 37693530112*x^6 + 1869026048*x^4 + 31222400*x^2 + 169744 } polredabs has slowed down considerable - used to take only 8s, now it takes 40s if I start with at least 8MB stack, and much longer if I start with 32bit-default 4MB stack - operating on a low stack with a lot of GC? > > It should fix long standing problems in small dimension like > > x^8-97418273277417164826810*x^4-97418273278115084139045*x^2 > +97418273278115084139045 > > or > x^4+946461962680424656489*x^2+946461962680424656489 > > which ran forever. On the other hand, it won't help for polynomials of huge > degrees with lots of subfields, if we're unlucky with the initial basis > ordering. Especially when the fields contain lots of roots of 1. Like > > polcompositum(x^12-2*x^9+2*x^6+2*x^3+1, polsubcyclo(9,3))[1] > > (in dimension 36). Just to see why, have a look at \g5, you'll see the > (many) vectors of small L^2 norm that are being enumerated, but unfortunately > do not generate the field. I do not see any obvious structure that would > enable me to prune this. Essentially, as soon as one (small) generator is > found, the show is over; but till then... > > For these guys, you simply _have_ to use polred. One could time the polredabs > run and abort it after some point, but since we simply do not find any > generator, it is all a waste of time. > > Igor, any glitches with the new algorithm ? The testsuite runs OK, and I haven't found any new *fatal* cases this far. It's great to see the above bugs fixed. Thanks Igor