Igor Schein on Thu, 3 Apr 2003 16:04:06 -0500

[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Re: polredabs() again

On Thu, Apr 03, 2003 at 10:42:54PM +0200, Bill Allombert wrote:
> On Wed, Mar 12, 2003 at 03:09:12PM -0500, Igor Schein wrote:
> > Hi,
> > 
> > I know there're too many things going on at the same time right now,
> > but I'll still gonna mention this example of polredabs() inefficiency:
> > 
> > polredabs(x^8-97418273277417164826810*x^4-97418273278115084139045*x^2+97418273278115084139045);
> > 
> > It takes extremely long time.  Basically, I'd like to see either a
> > quick fix ( if possible ) or an acknowledgement of the issue in TODO
> > file :).  I know we've discussed this with Karim in private emails,
> > but it never made it into TODO.  
> [I was expecting Karim to comment but...]
> Well, the underlying algorithm has a high complexity, so it is not clear
> it is a defficiency in PARI or even that it is fixable, if we insist
> to have the 'absolutly smallest polynomial'.

I would like to see an ability to do a flag-driven partial reduction.
I encounter many polynomials where polred(,1) returns *larger*
polynomials that the input one, while polredabs() wouldn't run to
completion in my life time.  

> Do you have experienced with other implementation (Kant OrderShort
> function ?)

Totally useless in my experience.  Someone please correct me if I am
wrong.  I've put Kant to use for other tasks, but I couldn't find a
legit equivalent of polredabs() there.