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

Possible performance issue in MPolyAnyMap / ring flattening

Open fingolfin opened this issue 5 months ago • 2 comments

During the "Julia performance tuning crash course" I did this week's OSCAR workshop, we looked at some of the "big" test suites in our tests, those which use 60GB of RAM and more, and found various sources of RAM usage.

One that was prominent across the board was the evaluate function for MPolyAnyMap, e.g. used for ring flattening.

The problem: it seems that images are constructed using + and ^. So if you map e.g. x^2*y + 5*y^3 to an isomorphic polynomial ring, then it gradually builds x^2, x^2*y, y^3, 5*y^3, x^2*y + 5*y^3 i.e. a ton of intermediate objects.

Of course in general, this is the best we can do.

But here the codomain is a polynomial ring.

There are multiple ways I can think of to address this, not necessarily mutually exclusive. e.g.

  1. We could perhaps add a special case to MPolyAnyMap for when the codomain is an MPolyRing? Ideally it would then use (the equivalent of) an MPolyBuildCtx.

  2. Perhaps we need additional kinds of maps that are optimized for certain setups?

  3. Perhaps the ring flattening code should simply not use MPolyAnyMap in the first place, but do its job differently?

  4. And perhaps we are not using MPolyAnyMap optimally in some cases?

  5. ... something else?

Here is a very simple way how R = k[x...], S = R[y...] could be mapped more efficiently to U = k[x...,y...]: consider a term c * Y in S, where c in R and Y is a monomial y^e with e=(e1,...,en). To map it, we can iterate over the terms in c which have the form d * x^f for some d in k and exponent vector f. For each of these terms, we just need to push (c, vcat(f,e)) into the MPolyBuildCtx.

Of course this only works if we map variables to variable, and if the variables are arranged in just this way. But it is my understanding that this is what we have in ring flattening situations anyway.

The process can also be adjusted to more than two "levels" (i.e. k[x...][y...][z...]) if necessary.

To go beyond MPolyRing yet more thoughts are required, but I am confident we can do something.

fingolfin avatar Sep 19 '24 09:09 fingolfin