Difference between revisions of "Category:ApCoCoA-1:Package gbmr"

From ApCoCoAWiki
m (Andraschko moved page Category:Package gbmr to Category:ApCoCoA-1:Package gbmr: Clearer page title)
 
(2 intermediate revisions by 2 users not shown)
Line 1: Line 1:
Package gbmr is designed to enable us to do basic computations, such as addition (via Add(F1,F2)), subtraction (via Subtract(F1,F2)), multiplication (via Multiply(F1,F2)), leading term (via LT(F)), leading coefficient (via LC(F)), normal remainder (via NR(F,G)), (partial) Groebner basis (via GB(G)), reduced (partial) Groebner basis (via ReducedGB(G)) and so on, over non-commutative algebras, i.e. over finitely generated free monoid rings (or free associative <tt>K</tt>-algebras or non-commutative polynomial rings), finitely presented monoid rings, group ring, etc. Consequently, the package can be applied to many algebraic applications, for instance the computations of leading term ideal (via LTIdeal(G)), kernel of <tt>K</tt>-algebra homomorphism (via KernelOfHomomorphism(X1,X2,Images)), Hilbert function (via HF(Gb)), etc.
+
The package gbmr contains numbers of functions for basic computations and Groebner basis computations in <em>non-commutative algebras</em>, such as finitely generated free monoid rings (or non-commutative polynomial rings, non-commutative free associative algebras), finitely presented monoid rings, group ring, etc., over the field of rational numbers Q or over finite fields Z/(p) where p is a prime. More precisedly, this package enables us to do computations as addition, subtraction and multiplication of two non-commutative polynomials, getting the leading word and leading coefficient of a non-zero polynomial, computing the normal remainder of a polynomial w.r.t. a list of polynomials, interreducing a lists of polynomials, enumerating (reduced) (partial) Groebner bases of finitely generated two-sided ideals, and computing truncated Groebner basis of a finitely and homogeneously generated two-sided ideals, etc. Consequently, this package can be applied to many algebraic applications, for instance, enumerating a Macaulay's basis and the values of the Hilbert function of a finitely generated K-algbera, computing leading word ideals, intersections of ideals, and kernels of K-algebra homomorphisms, and so on.
  
For most computations, there are three different functions having the same functionality but under different settings. Let us take addition as an example. There are three functions, namely MRAdd(X,Ordering,Relations,F1,F2), Add(F1,F2) and GAdd(F1,F2), doing addition over monoid ring, free associative algebra and group ring, respectively. For details about how to use each of them, please check relevant functions.
 
  
 +
Generally speaking, a finitely presented monoid ring is defined by <tt>P=K<X|R></tt>, where <tt>K</tt> is a field, <tt>X</tt> is a finite alphabet (or a finite set of indeterminates), and <tt>R</tt> is a finite set of relations. Clearly, we have <tt>P=K<X|R></tt> is isomorphic to <tt>K<X>/<R></tt>, where <tt>K<X></tt> is the free monoid ring generated by <tt>X</tt> over <tt>K</tt> and <tt><R></tt> is the two-sided ideal generated by <tt>R</tt>.
  
Generally speaking, a finitely presented monoid ring is defined by <tt>P=K<X|R>=K<X>/<R></tt>, where <tt>K</tt> is a field, <tt>X</tt> is a finite alphabet (a finite set of indeterminates), and <tt>R</tt> is a finite set of relations. Particularly, <tt>P</tt> becomes a free associative <tt>K</tt>-algebra if <tt>R</tt> is empty.
 
  
 +
<strong>Important issues about this package:</strong>
  
Things to know about this package.
+
(a) Predefined alias for this package is as follows.
  
(a) Predefined alias for this package is as follows.
+
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; Alias NCo := $apcocoa/gbmr;
  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; Alias NCo. := $apcocoa/gbmr;
+
Note that, before ApCoCoA 1.9.0,  the alias for this package is NC. However, since ApCoCoA 1.9.0, the alias NC has been used for the ApCoCoA package ncpoly.  
  
  
(b) By default, the field <tt>K</tt> is rational numbers. It can be set to a finite field <tt>Fp</tt> through the functions
+
(b) By default, the field <tt>K</tt> is the field of rational numbers. It can be set to a finite field through the functions
  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; NCo.SetFp(); and NCo.SetFp(Prime);
+
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; NCo.SetFp(); and NCo.SetFp(P);
  
where <tt>Prime</tt> is a prime number. The former sets finite field to <tt>F2=Z/(2)</tt>, and the latter to <tt>F_{Prime}=Z/(Prime)</tt>. One can reset <tt>K</tt> to rational number via the function
+
where <tt>P</tt> is a prime number. The former sets the finite field to the binary field <tt>{0,1}</tt>, and the latter to the finite field <tt>{0,1,2,...P-1}</tt>. One can reset <tt>K</tt> to rational numbers via the function
  
 
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; NCo.UnsetFp();
 
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; NCo.UnsetFp();
  
  
(c) The alphabet <tt>X</tt> is represented as a STRING of letters. Every letter in <tt>X</tt> must have a unique occurrence. The order of letters in <tt>X</tt> is important since it induces an admissible ordering specified by Ordering. <tt>X</tt> is set through the function
+
(c) The alphabet <tt>X</tt> is represented as a STRING of letters. Every letter in <tt>X</tt> must have a unique appearance. The order of letters in <tt>X</tt> is important since it will induce word orderings on the free monoid <tt><X></tt> (see NCo.SetOrdering). The alphabet <tt>X</tt> is set via the function
  
 
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; NCo.SetX(X);
 
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; NCo.SetX(X);
Line 29: Line 29:
 
where <tt>X</tt> is a STRING of letters.
 
where <tt>X</tt> is a STRING of letters.
  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(c.1) Each word (term) in the free monoid <tt><X></tt> is represented as a STRING with all letters coming from <tt>X</tt>.
+
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; (c.1) Each word (term) in the free monoid <tt><X></tt> is represented as a STRING with all letters coming from <tt>X</tt>. For example, the word
  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;For example, X:="abc"; W:="ba"; means a word <tt>W=ba</tt>.
+
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <tt>w=ba</tt>  
  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Note that the identity element in <tt><X></tt> is the empty word which is represented as the empty STRING "".
+
is represented as  
  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(c.2) Each polynomial in <tt>K<X></tt> (or <tt>K<X|R></tt>) is represented as a LIST of monomials, and each monomial is represented as a LIST consisting of an element (coefficient) in <tt>K</tt> and a word (term) in <tt><X></tt>.
+
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; W:="ba";
  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;For example, X := "abc"; P := [[1,"ab"],[1,"bb"],[1,""]]; means a polynomial <tt>P=ab+b^2+1</tt>.  
+
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Note that the identity element in <tt><X></tt> is the empty word which is represented as the empty STRING "".
  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Note that the zero polynomial <tt>0</tt> is represented as the empty LIST [].
+
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; (c.2) Each non-commutative polynomial is represented as a LIST of monomials, and each monomial is represented as a LIST consisting of an element (coefficient) in <tt>K</tt> and a word (term) in <tt><X></tt>. For example the polynomial
  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(c.3) In the case that <tt>K=F2</tt>, every polynomial can be represented as a LIST of words (terms) in <tt><X></tt>. For example, the polynomial <tt>P=ab+b^2+1</tt> in <tt>F2<a,b></tt> is represented as P := ["ab","bb",""]. We refer to the examples of functions in free monoid rings over <tt>F2</tt> (functions with the prefix "G") for more details.
+
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <tt>f=ab+2b^2+3</tt>
  
 +
is represented as
  
(d) An admissible ordering <tt>Ordering</tt> is a STRING indicating which ordering we are working with. Currently, the package only supports length-lexicographic ordering ("LLEX"), elimination ordering ("ELIM") and length-reverse-lexicographic ordering ("LRLEX"), which are induced from the order of letters in <tt>X</tt>. We refer to the function NCo.SetOrdering for the definitions of these orderings. Note that the default ordering is "LLEX".
+
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;  F := [[1,"ab"],[2,"bb"],[3,""]];
  
For example, X:="abc"; Ordering:="ELIM"; means the elimination ordering induced by <tt>a>b>c</tt>.  
+
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Note that the zero polynomial <tt>0</tt> is represented as the empty LIST [].  
  
<tt>Ordering</tt> is set through the function
+
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; (c.3) In the case that <tt>K={0,1}</tt>, every polynomial can be represented as a LIST of words (terms) in <tt><X></tt>. For example, the polynomial
  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; NCo.SetOrdering(Ordering);
+
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <tt>p=ab+b^2+1</tt>
  
where <tt>Ordering</tt> is one of the orderings supported by the package. One can reset <tt>Ordering</tt> to "LLEX" via the function
+
is represented as
  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; NCo.UnsetOrdering();
+
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; P := ["ab","bb",""];
  
 +
Notice that this representation is ONLY applied to computations in free monoid rings over the binary field <tt>{0,1}</tt>. See functions with the prefix "B" for more details.
  
(e) A set <tt>Relations</tt> of relations is a finite set represented as a LIST. Each relation in <tt>Relations</tt> is represented as a LIST composed of two words in <tt><X></tt>.
 
  
For example, X := "abc"; Relations := [["ba","ab"], ["ca","ac"], ["cb","bc"]]; means <tt>Relations</tt> containing relations <tt>ba=ab</tt>, <tt>ca=ac</tt> and <tt>cb=bc</tt>.  
+
(d) A <em>word ordering</em> on a monoid is a well-ordering that is compatible with multiplication. One can set word orderings via the function
  
<tt>Relations</tt> is set through the function
+
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; NCo.SetOrdering(Ordering);
 
 
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; NCo.SetRelations(Relations);
 
  
where <tt>Relations</tt> is a set of properly represented relations. One can set <tt>Relations</tt> to empty via the function
+
where <tt>Ordering</tt> is a STRING indicating which ordering we are going to work with. Currently, the package only supports the length-lexicographic ordering ("LLEX"), an elimination ordering ("ELIM") and the length-reverse-lexicographic ordering ("LRLEX"). We refer to NCo.SetOrdering for the definitions of these orderings. The default ordering is "LLEX". Note that word orderings are induced by the order of letters in <tt>X</tt>. For example, X:="abc"; Ordering:="LLEX"; means the length-lexicographic word ordering induced by <tt>a>b>c</tt>.
  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; NCo.UnsetRelations();
+
(e) For a finitely presented monoid ring <tt>P=K<X|R></tt>, the set <tt>R</tt> of relations is represented as a LIST. and each relation in <tt>R</tt> is represented as a LIST composed of two words in <tt><X></tt>. For example, the relations
  
Note that using the functions UnsetRelations() is a tricky way to change a monoid ring to a free monoid ring.
+
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <tt>R={ba=ab, ca=ac, cb=bc}</tt>
  
 +
is represented as
  
(f) A set <tt>Rules</tt> of rewriting rules is a finite set represented as a LIST. Each rewriting rule in <tt>Rules</tt> is represented as a LIST composed of a word in <tt><X></tt> and a polynomial in <tt>K<X></tt> (or <tt>K<X|R></tt>).
+
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; R:= [["ba","ab"], ["ca","ac"], ["cb","bc"]];
  
For example, X := "ab"; Rules := [["ba",  [[1,"ab"], [1,""]]]]; means <tt>Rules</tt> containing rewriting rule <tt>ba=ab+1</tt>.
+
The relations can be set via the function
  
<tt>Rules</tt> is set through the function
+
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; NCo.SetRelations(R);
  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; NCo.SetRules(Rules);
+
where <tt>R</tt> is a LIST of properly represented relations. One can set the relations to empty via the function
  
where <tt>Rules</tt> is a set of properly represented rules. One can set <tt>Rules</tt> to empty via the function
+
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; NCo.UnsetRelations();
  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; NCo.UnsetRules();
 
  
 +
(f) Th following function gives basic information on the working ring.
  
(g) There is a function for showing general information on ring environment.
+
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; NCo.RingEnv();
  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; NCo.RingEnv();
 
  
 +
(g) For most computations, there are three different functions having the same functionality but under different settings. Let us take addition as an example. There are three functions, namely MRAdd(X,Ordering,Relations,F1,F2), Add(F1,F2) and BAdd(F1,F2), doing addition over monoid rings, free monoid rings and free monoid rings over the binary field, respectively. For details about how to use each of them, please check relevant functions.
  
[[Category:ApCoCoA_Manual]]
+
[[Category:ApCoCoA-1 Manual]]

Latest revision as of 15:17, 2 October 2020

The package gbmr contains numbers of functions for basic computations and Groebner basis computations in non-commutative algebras, such as finitely generated free monoid rings (or non-commutative polynomial rings, non-commutative free associative algebras), finitely presented monoid rings, group ring, etc., over the field of rational numbers Q or over finite fields Z/(p) where p is a prime. More precisedly, this package enables us to do computations as addition, subtraction and multiplication of two non-commutative polynomials, getting the leading word and leading coefficient of a non-zero polynomial, computing the normal remainder of a polynomial w.r.t. a list of polynomials, interreducing a lists of polynomials, enumerating (reduced) (partial) Groebner bases of finitely generated two-sided ideals, and computing truncated Groebner basis of a finitely and homogeneously generated two-sided ideals, etc. Consequently, this package can be applied to many algebraic applications, for instance, enumerating a Macaulay's basis and the values of the Hilbert function of a finitely generated K-algbera, computing leading word ideals, intersections of ideals, and kernels of K-algebra homomorphisms, and so on.


Generally speaking, a finitely presented monoid ring is defined by P=K<X|R>, where K is a field, X is a finite alphabet (or a finite set of indeterminates), and R is a finite set of relations. Clearly, we have P=K<X|R> is isomorphic to K<X>/<R>, where K<X> is the free monoid ring generated by X over K and <R> is the two-sided ideal generated by R.


Important issues about this package:

(a) Predefined alias for this package is as follows.

             Alias NCo := $apcocoa/gbmr;

Note that, before ApCoCoA 1.9.0, the alias for this package is NC. However, since ApCoCoA 1.9.0, the alias NC has been used for the ApCoCoA package ncpoly.


(b) By default, the field K is the field of rational numbers. It can be set to a finite field through the functions

             NCo.SetFp(); and NCo.SetFp(P);

where P is a prime number. The former sets the finite field to the binary field {0,1}, and the latter to the finite field {0,1,2,...P-1}. One can reset K to rational numbers via the function

             NCo.UnsetFp();


(c) The alphabet X is represented as a STRING of letters. Every letter in X must have a unique appearance. The order of letters in X is important since it will induce word orderings on the free monoid <X> (see NCo.SetOrdering). The alphabet X is set via the function

             NCo.SetX(X);

where X is a STRING of letters.

       (c.1) Each word (term) in the free monoid <X> is represented as a STRING with all letters coming from X. For example, the word

             w=ba

is represented as

             W:="ba";

      Note that the identity element in <X> is the empty word which is represented as the empty STRING "".

       (c.2) Each non-commutative polynomial is represented as a LIST of monomials, and each monomial is represented as a LIST consisting of an element (coefficient) in K and a word (term) in <X>. For example the polynomial

             f=ab+2b^2+3

is represented as

             F := [[1,"ab"],[2,"bb"],[3,""]];

      Note that the zero polynomial 0 is represented as the empty LIST [].

       (c.3) In the case that K={0,1}, every polynomial can be represented as a LIST of words (terms) in <X>. For example, the polynomial

             p=ab+b^2+1

is represented as

             P := ["ab","bb",""];

Notice that this representation is ONLY applied to computations in free monoid rings over the binary field {0,1}. See functions with the prefix "B" for more details.


(d) A word ordering on a monoid is a well-ordering that is compatible with multiplication. One can set word orderings via the function

             NCo.SetOrdering(Ordering);

where Ordering is a STRING indicating which ordering we are going to work with. Currently, the package only supports the length-lexicographic ordering ("LLEX"), an elimination ordering ("ELIM") and the length-reverse-lexicographic ordering ("LRLEX"). We refer to NCo.SetOrdering for the definitions of these orderings. The default ordering is "LLEX". Note that word orderings are induced by the order of letters in X. For example, X:="abc"; Ordering:="LLEX"; means the length-lexicographic word ordering induced by a>b>c.

(e) For a finitely presented monoid ring P=K<X|R>, the set R of relations is represented as a LIST. and each relation in R is represented as a LIST composed of two words in <X>. For example, the relations

             R={ba=ab, ca=ac, cb=bc}

is represented as

             R:= [["ba","ab"], ["ca","ac"], ["cb","bc"]];

The relations can be set via the function

             NCo.SetRelations(R);

where R is a LIST of properly represented relations. One can set the relations to empty via the function

             NCo.UnsetRelations();


(f) Th following function gives basic information on the working ring.

             NCo.RingEnv();


(g) For most computations, there are three different functions having the same functionality but under different settings. Let us take addition as an example. There are three functions, namely MRAdd(X,Ordering,Relations,F1,F2), Add(F1,F2) and BAdd(F1,F2), doing addition over monoid rings, free monoid rings and free monoid rings over the binary field, respectively. For details about how to use each of them, please check relevant functions.