Re: Speed up RgX_mul, RgX_sqr, RgX_divrem over Z, Fp, FpXQ

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

On Wed, Jun 07, 2017 at 07:43:32PM +0200, Peter Bruin wrote:
> Hello,
> 
> The following resultant computation (with output of degree 9480)
> currently takes about 10 minutes:
> 
> g = x^11+t^13+3*x^7+(2*(t+1)^8+2*t)^7*x^6+(2*t^8+t^6+2*t)^45*x^3+(t+1)^5*t^4*(2*x+x)+t^12+2;
> f = Mod(g^2+x^4*(t+2)^4-t^12, 5);
> r = polresultant(f, f', 'x);
> 
> Claus Fieker pointed out that this only takes about 0.3 seconds in Bill
> Hart's implementation of the subresultant algorithm in Julia.
> 
> It turns out that the PARI implementation can also be significantly sped
> up by dispatching to more specialised functions in RgX_mul, RgX_sqr and
> RgX_divrem.  After applying the two attached patches, the time for the
> above computation drops to about 0.7 seconds.

Hello Peter,

RgX_mul not calling ZX_mul was more or less a design decision
done to avoid repeated type checks in low level code.

Instead, the idea was that highlevel functions like polresultant 
would call low-level functions like FpX_resultant.

However this is not the case for polresultant:

-- polresultant only call ZX_resultant and QX_resultant, but not the
other resultant functions:
Flx_resultant, FpX_resultant, Flx_FlxY_resultant, FlxX_resultant,
FpX_FpXY_resultant, ZX_ZXY_resultant

-- there is no FpXY_resultant, so this would not help you anyway.

If we are going to keep this design decision, we should change
resultant_all to call gmul instead of RgX_mul, etc.

Maybe it would be better to have functions RgX_mul_i etc.
that does what RgX_mul is doing now, and change RgX_mul
to do what you suggest.

Cheers,
Bill.