Re: polredabs() suggestion

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

On Mon, 28 Apr 2003, Igor Schein wrote:
> On Mon, Apr 28, 2003 at 04:26:01PM +0200, Karim BELABAS wrote:
>> On Mon, 28 Apr 2003, Igor Schein wrote:
>>> I was thinking, maybe it's a good idea to restart smallvectors() with
>>> a lower bound once a better generator is found, to shorten the sorting
>>> stage.
>>
>> The current algorithm does this. Anytime a better generator is found, the
>> bound is updated, pruning the search tree.
>
> Then I don't understand the following behavior ( snapshot of a polredabs()
> running I happen to be running right now, at \g5 ):
[...]
> The same generator is output over and over again.
>
> In other recent examples, I saw cases where several different generators
> are output during this stage.   It doesn't make sense if pruning is done,
> because the non-optimal ones shouldn't be seen more than once.

The ones which are output _are_ optimal [so far]. Pruning is done so that all
the _strictly_ worse ones currently accumulated are deleted. Then we
accumulate new elements [ which we don't check because the check is expensive
and it failed a few times already ].

When the cache overflows, we have to get rid of some of those accumulated
elements, so we sort them in order of increasing norm, and check them in
order.

When we find a generator, the "tail" is deleted. Unfortunately, we may find
the same generator over and over again [ because we accumulate elements all
of which generate subfields ].

An exhaustive search algorithm simply doesn't work when there are many
subfields and huge dimension. Using a C^n algorithm when n = 72 is not really
supposed to work. It _does_ work sometimes, but you shouldn't expect it too
often...

    Karim.

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.
-- 
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]