You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
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.
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.
Perhaps we need additional kinds of maps that are optimized for certain setups?
Perhaps the ring flattening code should simply not use MPolyAnyMap in the first place, but do its job differently?
And perhaps we are not using MPolyAnyMap optimally in some cases?
... 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.
The text was updated successfully, but these errors were encountered:
Since MPolyRingAny is just a fancy wrapper for evaluate, the problem should lie there. Indeed it seems to be the case that evaluate(f::MPolyRingElem, values::Vector) does not do clever things in case the target is a polynomial ring itself. Interestingly, partial evaluation evaluate(f::MPolyRingElem, variables::Vector{Int}, values::Vector) is optimized. It might be just a matter of fixing this.
I agree that for the best performance, RingFlattening should role its own evaluate.
Can you provide us with a simple example? I wonder how much one gains by fixing 1.
Here polynomials are loaded by parsing them via Meta.parse and then "evaluating" the resulting syntax tree. I think evaluate also shows up here, so this code would likely also benefit from an improved evaluate. But I think the real fix will be to not call evaluate at all. Perhaps it can switch to the serialization by @antonydellavecchia?
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 forMPolyAnyMap
, 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 buildsx^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.
We could perhaps add a special case to
MPolyAnyMap
for when the codomain is an MPolyRing? Ideally it would then use (the equivalent of) anMPolyBuildCtx
.Perhaps we need additional kinds of maps that are optimized for certain setups?
Perhaps the ring flattening code should simply not use
MPolyAnyMap
in the first place, but do its job differently?And perhaps we are not using
MPolyAnyMap
optimally in some cases?... something else?
Here is a very simple way how
R = k[x...]
,S = R[y...]
could be mapped more efficiently toU = k[x...,y...]
: consider a termc * Y
inS
, wherec in R
andY
is a monomialy^e
withe=(e1,...,en)
. To map it, we can iterate over the terms inc
which have the formd * x^f
for somed in k
and exponent vectorf
. For each of these terms, we just need to push(c, vcat(f,e))
into theMPolyBuildCtx
.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.The text was updated successfully, but these errors were encountered: