Nemocas/AbstractAlgebra.jl

An example of bad behaviour of multivariate gcd

sumiya11 opened this issue · 4 comments

sumiya11 commented 
using AbstractAlgebra

R, (x, y, z, t) = polynomial_ring(QQ, ["x","y","z","t"])

f = (x^5 - y)*(x - z)*(x + y + z + t)^2
g = (x^3 - y)*(x - z)*(x + y + z + t + 1)^2

@time gcd(f, g)
 388.518452 seconds (1.45 G allocations: 28.546 GiB, 20.09% gc time, 1.75% compilation time)

I imagine there is some expression swell happening (expectedly?).

In any case, feel free to close this issue. It is not an actionable item, just an observation.

thofma commented

It is

julia> @time gcd(f, g)
 47.001273 seconds (1.12 G allocations: 22.266 GiB, 29.84% gc time)

for me and

julia> @time gcd(f, g)
  0.000243 seconds (666 allocations: 47.484 KiB)

with Nemo. Since Nemo is fast, there is no urgency to work on this.

sumiya11 commented

I agree: Nemo is great

fieker commented
sumiya11 commented

Though I think the swell is universal, not only in the coefficients:

using AbstractAlgebra

function example(n)
    @assert n >= 3
    R, (x,y,z,other...) = polynomial_ring(GF(2^30+3), ["x$i" for i in 1:n])
    f = (x^5 - y)*(x - z)*(sum(gens(R))    )^2
    g = (x^3 - y)*(x - z)*(sum(gens(R)) + 1)^2
    f, g
end

for i in 3:5
    f, g = example(i)
    @time gcd(f, g)
end

With AbstractAlgebra:

  0.050994 seconds (6.70 k allocations: 3.879 MiB)
  2.754756 seconds (7.28 k allocations: 30.883 MiB, 3.61% gc time)
117.572059 seconds (251.60 k allocations: 326.330 MiB, 0.18% gc time, 0.59% compilation time)

with Nemo:

  0.000173 seconds (2 allocations: 96 bytes)
  0.000542 seconds (2 allocations: 96 bytes)
  0.001343 seconds (2 allocations: 96 bytes)