On Wed, Feb 12, 2025 at 10:06:24AM +0100, Grégory Vanuxem wrote:
>
> I need to implement the function in a Julia object but I'm not sure
> how FriCAS implemented it,
> or, at least conceptually, how it should be implemented.
>
> >From the description FiniteAbelianMonoidRing where it is declared:
> ++ Description: This category is
> ++ similar to AbelianMonoidRing, except that the sum is assumed to be finite.
> ++ It is a useful model for polynomials,
> ++ but is somewhat more general.
>
> The only documentation of this function is:
> minimumDegree : % -> E
> ++ minimumDegree(p) gives the least exponent of a non-zero term
> of polynomial p.
>
> But, here is an interpreter session:
> (10) -> ppp :MPOLY(['x,'y],INT):=x^7*y^3+3*x^17+y^11
>
> 17 3 7 11
> (10) 3 x + y x + y
> Type: MultivariatePolynomial([x,y],Integer)
> (11) -> minimumDegree %
>
> 11
> (11) y
> Type: IndexedExponents(OrderedVariableList([x,y]))
> (12) -> pp:=x^7*y^3+3*x^17+y^11
>
> 11 7 3 17
> (12) y + x y + 3 x
> Type: Polynomial(Integer)
> (13) -> minimumDegree %
>
> 17
> (13) x
> Type: IndexedExponents(Symbol)
>
> So, the documentation should be more precise, no?, variable ordering
> (?) to choose a variable (?) or ?
AbelianMonoidRing is build from OrderedAbelianMonoid. Which
means that there is order on exponents and this order is used
by minimumDegree. OrderedAbelianMonoid means that order
agrees with monoid operations and operatios are commutative,
but otherwise can be rather general. When the exponent monoid
is finitely generated people working on Groeber bases gave
full description of possible orders. Basically, generators
embed into a linear space over R and there are linear
functionls \phi_1, ..., \phi_k such that e_1 < e_2 is
equvalent to lexicographic order between (\phi_1(e_1), ..., \phik1(e_1))
and (\phi_1(e_2), ..., \phi_k(e_2)).
> Any thoughts? How should I code it? I have a vector of (term,
> exponent) or a listOfTerms.
>
> (19) -> pp:=x^7*y^3+3*x^17+y^11
>
> (19) 3*x^17 + x^7*y^3 + y^11
> Type: NemoMultivariatePolynomial(NemoRational,[x,y,z],:lex)
>
> (20) -> jlApply("collect", jlApply("terms",pp))
>
> (20)
>
> 3-element Vector{QQMPolyRingElem}:
> 3*x^17
> x^7*y^3
> y^11
> Type: JuliaObject
> (21) -> listOfTerms pp
>
> 17 7 3 11
> (21) [[k = x , c = 3], [k = x y , c = 1], [k = y , c = 1]]
> Type: List(Record(k: IndexedExponents(OrderedVariableList([x,y,z])),c:
> NemoRational))
>
> And if I change the ordering of MPOLY,
>
> (22) -> ppp :MPOLY(['yy,'xx],INT):=xx^7*yy^3+3*xx^17+yy^11
>
> 11 7 3 17
> (22) yy + xx yy + 3 xx
> Type: MultivariatePolynomial([yy,xx],Integer)
> (23) -> minimumDegree %
>
> 17
> (23) xx
AbelianMonoidRing is a category, it says what functions should
be implemented and their properties. Actual implementation
is left to domains. In FriCAS there are at least 3 different
representations. One is as list of pairs (coefficient, exponent).
Such list is sorted starting from biggest exponent. So one
need to go over whole list to get minimal exponent. Second
representation is recursive, it starts from biggest (main)
variable and stores polynomial as univariate polynomial in
the main variable with coefficients in polynomials in
remioning variables. This representation is only good
for lexical order. Third representation is dense univariate
in arrays. Here one needs to go trough array looking for
nonzero elements (array index 0 means exponent 0). Maple
has recursive representation based on arrays. IIUC giac
has representation based on hash tables. In literature there
are things called IIRC "geobuckets". Of course, they
require different method of computing minimumDegree.
--
Waldek Hebisch
--
You received this message because you are subscribed to the Google Groups
"FriCAS - computer algebra system" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to fricas-devel+unsubscr...@googlegroups.com.
To view this discussion visit
https://groups.google.com/d/msgid/fricas-devel/Z6yT5Tj0HoHPX1KX%40fricas.org.
