|Bill Allombert on Wed, 07 Jun 2017 21:12:58 +0200|
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
|Re: Speed up RgX_mul, RgX_sqr, RgX_divrem over Z, Fp, FpXQ|
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.