Re: slow factor

[Zhao Li <zhaoli@ihep.ac.cn>]

Dear Bill,

	Thank you. 
	In practice we can restrict the input polynomial in the integer ring.
	This function works very well. But we found it failed for this polynomial.

P = -400000*ieta + 3600000*ep*ieta + 4*ep*ieta^2 - 11300000*ep^2*ieta - 20*ep^2*ieta^2 + 15000000*ep^3*ieta + 33*ep^3*ieta^2 - 7200000*ep^4*ieta - 18*ep^4*ieta^2;

	We do not fully understand the reason yet.

Cheers,
Zhao

Theoretical Physics Division
Institute of High Energy Physics
Chinese Academy of Sciences

> On Apr 30, 2022, at 3:28 AM, Bill Allombert <Bill.Allombert@math.u-bordeaux.fr> wrote:
> 
> On Sat, Apr 30, 2022 at 02:12:33AM +0800, Zhao Li wrote:
>> Hi all,
>> 
>> 	We are using GP for factoring the multivariate polynomial, which
>> 	however could be extremely slow compared to Factor function in
>> 	mathematica. 
> 
> Yes, this is very slow. In fact, this is not even really documented!
> 
>> 	So we were wondering if there is any option to make factor more efficient in GP.
> 
> Probably not... Over what ring do you want to factor ?
> Your example is in Z[i][X,Y] (with i^2=-1).
> 
> PARI do not have fast GCD code for such ring, so issquarefree(P) is very slow.
> 
> You can try the following script which skip the issquarefree step:
> 
> fact(P) =
> {
>  my(x=variable(P),y=variable(Vec(P)));
>  my(d=poldegree(P,y));
>  my(C=content(P),FC=factor(C));
>  for(i=1,oo,
>    my(R=substpol(factor(subst(P/C,ieta,(x+i)^d)),(x+i)^d,ieta));
>    R= matconcat([FC,R]~);
>    my(F=factorback(R)*C);
>    if(pollead(P)*F==pollead(F)*P,
>      return(R)));
> }
> 
> ? fact(P)
> ? ##
>  ***   last result computed in 8,564 ms.
> 
> (which is slow but still usable).
> 
> Cheers,
> Bill