Re: polredabs failure

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

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]