Re: polredabs() suggestion

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

On Wed, 30 Apr 2003, Bill Allombert wrote:
> On Tue, Apr 29, 2003 at 05:53:15PM -0400, Igor Schein wrote:
>>> P.S: I could "mark" the previous generator, so that the check is not done
>>> many times on the same element, and it is just accepted as is, provided it
>>> passes the test once. With current settings that means < 0.5% savings. I
>>> didn't bother.
>> I feel very strongly that this would show a significant improvement on
>> the polynomials I've had problems with, e.g.
>>
>> x^8-97418273277417164826810*x^4-97418273278115084139045*x^2+97418273278115084139045
>>
>> ( from one of my older postings ).
>>
>> So if there's no performance penalty for an average case ( which I
>> don't forsee ), it's a change I would more than welcome.
>
> I am with Igor here. I have made a lot a similar tweaking in galoisinit.
> While it seems wasteful in normal case, it can make a large difference
> on catastrophical case. And usually catastrophical case are the more
> interesting.
>
> For example you could keep a 'top 10' list of generators that appear the
> most often and compare with them before the other test. If it is found, you
> reorder them.

It wouldn't work. The problem is that polredabs insists on finding the _best_
generator (wrt to T2-norm), so it has to check and delete all the smaller
vectors that do not generate the field. Assume you see 10^3 "sorting..."
messages; that means 2.10^5 checks. Out of these at most 10^3 + 200 were
successful, and could (possibly) have been saved.

One minor improvement I see is to remove the (IMHO silly) flag polredabs(,4),
and the (undocumented) feature that the polynomial with smallest discriminant
for a given minimal T2-norm is output. Then at least we do not have to keep
_all_ the best generators so far. A single one would be enough, in effect
increasing the cache. [ Directly increasing the cache also would be a minor
improvement. ]

Again, the only significant improvements would be to
1) rewrite the backtracking so that smallest vectors are found first.

2) find an efficient algorithm to determine the largest subset of basis
that still only generate a subfield [ "skipfirst" pruning ].

3) add user-defined (flag-driven) limits to bottom out of the recursion when
too much time is spent.

Item 3) would certainly be the most useful one.

No time for this, unfortunately...

Cheers,

    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]