AbstractAlgebra.jl icon indicating copy to clipboard operation
AbstractAlgebra.jl copied to clipboard

possible improvements to mpoly divrem

Open tthsqe12 opened this issue 3 years ago • 1 comments

Currently: the divrem goes down the list of divisors, finds the first one whose lm divides the lm of the divisor, and performs a reduction. There is a more general notion where all divisors whose lm divides the lm of the divisor are considered at the same time. These can be simulaneously used to essentially perform a reduction modulo the gcd of the corresponding lc's. Ex:

julia> using AbstractAlgebra

julia> R,(x,) = PolynomialRing(ZZ, ["x"]);

julia> divrem(x, [3*x, 5*x])      # suboptimial: gcd(3,5) = 1, so we should be able to reduce to 0
(AbstractAlgebra.Generic.MPoly{BigInt}[0, 0], x)

julia> divrem(5*x, [3*x, 5*x])    # suboptimal: 5 mod 3 = 2, then 2 mod 3 = 2 
(AbstractAlgebra.Generic.MPoly{BigInt}[1, 0], 2*x)

julia> divrem(3*x, [5*x, 3*x])    # optimal only by chance. 3 mod 5 = 3, 3 mod 3 = 0
(AbstractAlgebra.Generic.MPoly{BigInt}[0, 1], 0)

tthsqe12 avatar Nov 16 '22 15:11 tthsqe12

This is a question of definition. I am happy for someone to adjust it.

thofma avatar Nov 17 '22 07:11 thofma