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

Published 20 hours ago • verified publisher icon JuliaAlgebra

Monomial ordering

Open saschatimme opened this issue 6 years ago • 4 comments

Could elaborate which monomial ordering is currently used? Lexicographic? And is this enforced by the interface, i.e. MultivariatePolynomials, or is it depending on the implementation, i.e. DynamicPolynomials etc.? And would it maybe make sense to be able to specify the ordering?

saschatimme avatar Apr 06 '18 08:04 saschatimme

Currently the ordering used is graded lexicographic order by DynamicPolynomials and TypedPolynomials. I agree that it would be nice to query the ordering used and be able to choose the monomial ordering in e.g. @polyvar.

blegat avatar Apr 06 '18 08:04 blegat

There are actually two things. The first one is the ordering and the other is the ordering of the variables itself. Currently we have the following behaviour: DynamicPolynomials.@polyvar b a results in the variable ordering b > a but TypedPolynomials.@polyvar b a results in a > b. This is quite subtle and could lead to some surprises. cc: @rdeits

saschatimme avatar Apr 06 '18 09:04 saschatimme

Yes, DynamicPolynomials compares variables using creation order while TypedPolynomials compares them with names. There is the same subtlety with == :-P

blegat avatar Apr 06 '18 11:04 blegat

The problem is that in TypedPolynomials the only identity a Variable has is its literal name, so that's the only information I can possibly use for comparison. Perhaps this is just something we have to document better?

rdeits avatar Apr 06 '18 15:04 rdeits

With the 0.5 release, there is the possibility to have different monomial orderings (although it is not fully implemented yet, as for example DP.monomials always generates graded lex order and therefore fails to produce valid monomial vectors, as mentioned in https://github.com/JuliaAlgebra/DynamicPolynomials.jl/issues/138). However, unless I'm mistaken, a way to query this ordering is still missing: While there is ordering(::APL), this gives the AbstractOrdering of the polynomial, which does not seem to be related in any way with the AbstractMonomialOrdering of the monomials. There is no such monomial_ordering(::Monomial{V,M}) where {V,M} = M, as for example the implementation in DynamicPolynomials would look like.

projekter avatar Oct 24 '23 10:10 projekter

Oops, indeed this ordering and AbstractOrdering are not in sync with the rest, we should make it match

blegat avatar Oct 24 '23 11:10 blegat