Re: QX_caract

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

On Mon, 17 Mar 2003, Bill Allombert wrote:

> On Sat, Mar 15, 2003 at 03:29:46PM +0100, Karim BELABAS wrote:
> > On Wed, 5 Mar 2003, Bill Allombert wrote:
> > > Why not use the modular algorithm of ZX_caract directly in QX_caract
> > > instead of removing the content and calling ZX_caract ?
[...]
> > OK, this is implemented in CVS. The modulus bound is rigorous (~ Hadamard
> > bound + floating point computation if bound is huge).
>
> Thanks ! I have tried it and polred seems to be much faster on my degree
> 72 polynomials.
>
> At least it use a bound of 2^16000 instead of 2^3000000 (72 times...).
> Of course this is still much too large or else polred is a complete
> failure (we expect polred to give small polynomial after all), but at
> least this is bearable. (it take 9 minutes instead of 7 hours.)

Note that the polred final phase is quite inefficient in any case. The way
polredabs does it is to use floating point approximations for the roots
(which need to be computed in any case for the LLL reduction), then round.

Actually, the first phase of polredabs [ polredabs + fincke_pohst excluding
smallvectors ] _is_ a polred, and should be much faster when LLL takes
negligible time.

How does it fare in your example ? Try at \g4 for instance, and stop it when
you see the "smallvectors looking for..." message.

It should already print subfield information (overkill in degree 72 where
we have no chance of completing the enumeration anyway) and reduced generators
(the _same_ that polred would print).

Note that due to the LLL code reorganization, polred is mostly an empty
wrapper now (we have common LLL driver routines for nfinit/polred/polredabs):
the "tough" part is handled by

    nfbasic_init(x, flag, fa, &T);
    if (T.lead) err(impl,"polred for non-monic polynomial");
    set_LLL_basis(&T, &ro);

which are also the first steps of polredabs(), and includes the maximal
order computation and LLL reduction. Then there is the inefficient QX_caract
loop to compute the characteristic polynomials.

polredabs() + skip almost everything in fincke_pohst() + early exit should
replace it some day.

    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]