Re: polredabs() suggestion

[Igor Schein <igor@txc.com>]

On Wed, Apr 30, 2003 at 01:12:25PM +0200, Karim BELABAS wrote:
> 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. ]

If it's gonna fix the current woes right away, then I'm all for it.
Besides, returning a vector contradicts the idea of polynomial
canonization anyway. 

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

I think the other two are no less important.  The 3rd one just adds
flexibility, it's not an algorithm impovement per ce.  

To be honest, I would like to see the user be able to specify a
different comparison criteria, like poldisc(pol), or #Str(pol), or
even vecsort(abs(Vec(pol)),,4)[1], all of them being as inexpensive as
current norml2(polroots(pol)).  Wishful thinking, I guess :) 
    
> 
> No time for this, unfortunately...

I hope it won't always be the case :)

Igor