Re: slow factor

[Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>]

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