Karim BELABAS on Tue, 14 Oct 2003 20:29:29 +0200 (MEST) |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: polredabs failure |
On Tue, 14 Oct 2003, Karim BELABAS wrote: > On Mon, 13 Oct 2003, Igor Schein wrote: > > 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? > > You can't have everything. This example is not very surprising (many > subfields, and quadratic ones at that) : one should be thankful it works > at all !! [...] > In this particular example, the "core" is entirely filled with > non-generators. Which could be detected in the subfields search phase, but at > an even higher cost [ due to the special nature of the Galois resolvants > you're throwing at it, polynomial factorization is highly non-trivial. ]. This part was silly. It's actually trivial to check whether a number of elements generate a subfield (easy linear algebra, no reason to compute compositums and factor difficult polynomials). I've changed this part of the algorithm. So this example should be slightly faster than it used to be: the field generated by the first 14 elements of the basis is a strict subfield. Previously, only the first 8 ones were tested since the check was (deemed) too expensive otherwise. Any glitches ? Karim. -- Karim Belabas Tel: (+33) (0)1 69 15 57 48 Dép. de Mathématiques, Bât. 425 Fax: (+33) (0)1 69 15 60 19 Université Paris-Sud http://www.math.u-psud.fr/~belabas/ F-91405 Orsay (France) http://www.parigp-home.de/ [PARI/GP]