Iteration over monomials in modules is slow

[HechtiDerLachs]

I came across this issue in #3002 and also left a comment in the source. But it is probably better to also have this documented here. Try the following:

R, (x, y, z) = QQ[:x, :y, :z]

m = ideal(R, gens(R))
pow_m = m^200;

F = FreeMod(R, 5)

M, _ = pow_m*F;

w = sum(gens(M));
v = ambient_representative(w);
@time collect(monomials(v));

g = sum(gens(m));
@time collect(monomials(g));

What you would expect is that the second timing is roughly five times the first, because F is free of rank 5. However, I get

julia> @time collect(monomials(v));
  0.447076 seconds (7.59 M allocations: 301.277 MiB, 2.17% gc time)

vs.

julia> @time collect(monomials(g));
  0.000033 seconds (18 allocations: 840 bytes)

The use of a profiler reveals that apparently there is some "ordering up to permutation" working on putting the monomials in modules in correct order with respect to some monomial ordering of the module.

[jankoboehm]

As far as I remember there was somewhere the idea that the monomials command allows you to get the monomials in the right ordering, as a substitute of the polynomials not printing in the default ordering of the ring (which would be better). So I guess this behaviour is expected and there could be another command to just get the non-sorted monomials.

[fieker]

On Thu, Nov 30, 2023 at 08:28:20AM -0800, Janko Boehm wrote:

As far as I remember there was somewhere the idea that the monomials command allows you to get the monomials in the right ordering, as a substitute of the polynomials not printing in the default ordering of the ring (which would be better). So I guess this behaviour is expected and there could be another command to just get the non-sorted monomials.

I'd opt for a keyword: raw = true

-- Reply to this email directly or view it on GitHub: https://github.com/oscar-system/Oscar.jl/issues/3055#issuecomment-1834110785 You are receiving this because you are subscribed to this thread.

Message ID: @.***>

[fieker]

Side comment: g is tiny, v is large, hence a time difference.... bad example The question is still valid: two use cases

• Frank: wants the monomials sorted "his" way, default_ordering
• modular algorithsm: deterministic and FAST, don't care about details Frank needs sorting ....

Suggestion:

• use raw
• invent a new name for the fast version (and similar for exponents and others) and fix the modular stuff

[mjrodgers]

What you would expect is that the second timing is roughly five times the first, because F is free of rank 5.

Here, m has 3 generators, and M has 101505. The size difference (in terms of number of generators) is about 5x between M and pow_m.

[JohnAAbbott]

Revised test:

R, (x, y, z) = QQ[:x, :y, :z]

m = ideal(R, gens(R))
pow_m = m^200;

F = FreeMod(R, 5)

M, _ = pow_m*F;

w = sum(gens(M));
v = ambient_representative(w);
@time collect(monomials(v));

g = sum(gens(pow_m));  ### REVISED ###
@time collect(monomials(g));

Timings obtained using @btime which might be more reproducible than with @time:

julia> @btime collect(monomials(v));
  743.380 ms (10193203 allocations: 393.99 MiB)
julia> @btime collect(monomials(g));
  73.933 ms (1031635 allocations: 37.52 MiB)

Observe there is a ratio of about 10:1 in the amount of memory allocated; so this may be closely related to ratio of the execution times. As a variant, I tried increasing the rank of F to 10, and the time and memory requirement for v essentially doubled.