Re: polredabs() suggestion

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

On Tue, 29 Apr 2003, Igor Schein wrote:
> On Mon, Apr 28, 2003 at 09:59:10PM +0200, Karim BELABAS wrote:
> > 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.
>
> [snip]
>
> > 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
>
> 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.

Sorry if I was unclear. The 0.5% savings applies to this specific example
also: you wouldn't notice any improvement. The algorithm (current settings)
caches 200 small vectors (when in "looks like we're having problem" mode),
then orders them by order of increasing norm, and checks them in turn. Very
small vectors are plentiful in your example, and the large known generator
comes last most of the time.

So each time we have a "sorting" phase we check about 199 vectors (and fail).
Marking generators in the aforementioned manner would save a _single_ check
(since we abort as soon as the check is successful, saving a successful check
gains almost nothing).

If there do not exist very small generators (or subfields are not conveniently
detected), I have to check _all_ the small vectors. That largely dominates
everything else.

    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]