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

From ApCoCoAWiki
(New page: Package ncpoly is designed to enable us to do basic computations in non-commutative polynomial rings (or free associative algebras), over the field of rational numbers <tt>Q</tt> or over f...)
 
Line 1: Line 1:
−
Package ncpoly is designed to enable us to do basic computations in non-commutative polynomial rings (or free associative algebras), over the field of rational numbers <tt>Q</tt> or over finite field <tt>Z/(p)</tt> where <tt>p</tt> is a prime. For instance, in the package, there are functions for addition of two (non-commutative) polynomials (via Add(F1,F2)), subtraction (via Sub(F1,F2)), multiplication (via Mul(F1,F2)), getting the leading word (via Lw(F)) and leading coefficient (via Lc(F)) of a non-zero polynomial, computing the normal remainder (via NR(F,G)) of a polynomial w.r.t a LIST of polynomials, interreducing (via Interreduction(G)) a LIST of polynomials, etc. Moreover, we can, check if a LIST of polynomials is a Groebner basis (via IsGB(G)), enumerate (reduced) (partial) Groebner bases (via GB(G[,Optimize,OFlag,DB,LB]) and RedGB(G[,Optimize,OFlag,DB,LB])), and compute truncated Groebner bases (via TruncatedGB(G[,Optimize,OFlag,DB])) of finitely generated (two-sided) ideals. Consequently, we can apply the package to many algebraic applications, for instance, to compute Macaulay basis (via MB(Gb)) and the values of Hilbert function (via HF(Gb)), compute generating systems for leading term ideals, kernel of <tt>K</tt>-algebra homomorphism, intersection of ideals, etc.
+
Package ncpoly is designed to enable us to do <em>basic calculations</em> with polynomials in <em>non-commutative polynomial rings</em> (or <em>free associative algebras</em>), over the field of rational numbers <tt>Q</tt> or over finite fields <tt>Z/(p)</tt> where <tt>p</tt> is a prime. For instance, in the package, there are functions for addition of two (non-commutative) polynomials (via Add(F1,F2)), subtraction (via Sub(F1,F2)), multiplication (via Mul(F1,F2)), getting the leading word (via Lw(F)) and leading coefficient (via Lc(F)) of a non-zero polynomial, computing the normal remainder (via NR(F,G)) of a polynomial w.r.t a LIST of polynomials, interreducing (via Interreduction(G)) a LIST of polynomials, etc. Moreover, the package also contains functions for <em>Groebner basis computations</em>. For example, there are functions to check if a LIST of polynomials is a Groebner basis (via IsGB(G)), enumerate (reduced) (partial) Groebner bases (via GB(G[,Optimize,OFlag,DB,LB]) and RedGB(G[,Optimize,OFlag,DB,LB])), and compute truncated Groebner bases (via TruncatedGB(G[,Optimize,OFlag,DB])) of finitely generated (two-sided) ideals. Consequently, we can apply the package to many algebraic applications, i.e. to compute Macaulay basis (via MB(Gb)) and the values of Hilbert function (via HF(Gb)), compute generating systems for leading term ideals, kernel of <tt>K</tt>-algebra homomorphism, intersection of ideals, etc.
  
  
−
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>
  
 +
(a) Predefined alias for this package is as follows.
  
−
Things to know about this package.
+
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; Alias NC := $apcocoa/ncpoly;
  
−
(a) Predefined alias for this package is as follows.
 
  
−
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; Alias NC := $apcocoa/gbmr;
+
(b) The very first step to use functions in this package is to set non-commutative polynomial ring environment via the command
  
 +
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; Use
  
−
(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
+
For instance, the following command 
  
−
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; NC.SetFp(); and NC.SetFp(Prime);
+
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; Use QQ[x[1..2],y[1..2]];
  
−
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
+
sets the ring to be the non-commutative polynomial ring generated by <tt>{x[1],x[2],y[1],y[2]}</tt> over the rational numbers. Note that, for the time being, the package only supports non-commutative polynomial rings over the rational field <tt>QQ</tt> and finite fields <tt>ZZ/(p)</tt> where <tt>p</tt> is a prime.
  
−
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; NC.UnsetFp();
 
  
 +
(c) The word ordering is set via 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 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
+
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; NC.SetOrdering(Ordering)
  
−
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; NC.SetX(X);
+
where the parameter <tt>Ordering</tt> is a STRING indicating which ordering we are working with. Note that word orderings are induced by the order of indeterminates. And, for the time being, the package supports the following word orderings, and among which "LLEX" is the default ordering.
  
−
where <tt>X</tt> is a STRING of letters.
+
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; (b1) "LLEX": the <em>length-lexicographic ordering</em>
  
−
&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; (b2) "ELIM": an <em>elimination ordering</em>
  
−
&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; (b3) "LRLEX": the <em>length-reverse-lexicographic ordering</em>
 +
                 
 +
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; (b4) "DEGREVLEX": the <em>degree-reverse-lexicographic ordering</em>
  
−
&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 "".
+
For instance, the following commands
  
−
&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; Use ZZ/(2)[a,b,c,d];
  
−
&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;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; NC.SetOrdering("LLEX");
  
−
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Note that the zero polynomial <tt>0</tt> is represented as the empty LIST [].  
+
define the non-commutative polynomial ring generated by <tt>{a,b,c,d}</tt> over the binary field <tt>{0,1}</tt>, and set the word ordering to be the length-lexicographic ordering induced by <tt>a>b>c>d</tt>.
  
−
&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.
 
  
 +
(d) One can use the function
  
−
(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 NC.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; NC.RingEnv();
  
−
For example, X:="abc"; Ordering:="ELIM"; means the elimination ordering induced by <tt>a>b>c</tt>.  
+
to get basic information on the working polynomial ring.
  
−
<tt>Ordering</tt> is set through the function
 
  
−
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; NC.SetOrdering(Ordering);
+
<strong>Representation of non-commutative polynomials in this package</strong>
  
−
where <tt>Ordering</tt> is one of the orderings supported by the package. One can reset <tt>Ordering</tt> to "LLEX" via the function
 
  
−
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; NC.UnsetOrdering();
 
−
 
−
 
−
(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>.
 
−
 
−
<tt>Relations</tt> is set through the function
 
−
 
−
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; NC.SetRelations(Relations);
 
−
 
−
where <tt>Relations</tt> is a set of properly represented relations. One can set <tt>Relations</tt> to empty via the function
 
−
 
−
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; NC.UnsetRelations();
 
−
 
−
Note that using the functions UnsetRelations() is a tricky way to change a monoid ring to a free monoid ring.
 
−
 
−
 
−
(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>).
 
−
 
−
For example, X := "ab"; Rules := [["ba",  [[1,"ab"], [1,""]]]]; means <tt>Rules</tt> containing rewriting rule <tt>ba=ab+1</tt>.
 
−
 
−
<tt>Rules</tt> is set through the function
 
−
 
−
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; NC.SetRules(Rules);
 
−
 
−
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; NC.UnsetRules();
 
−
 
−
 
−
(g) There is a function for showing general information on ring environment.
 
−
 
−
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; NC.RingEnv();
 
  
  
 
[[Category:ApCoCoA_Manual]]
 
[[Category:ApCoCoA_Manual]]

Revision as of 12:25, 25 April 2013

Package ncpoly is designed to enable us to do basic calculations with polynomials in non-commutative polynomial rings (or free associative algebras), over the field of rational numbers Q or over finite fields Z/(p) where p is a prime. For instance, in the package, there are functions for addition of two (non-commutative) polynomials (via Add(F1,F2)), subtraction (via Sub(F1,F2)), multiplication (via Mul(F1,F2)), getting the leading word (via Lw(F)) and leading coefficient (via Lc(F)) of a non-zero polynomial, computing the normal remainder (via NR(F,G)) of a polynomial w.r.t a LIST of polynomials, interreducing (via Interreduction(G)) a LIST of polynomials, etc. Moreover, the package also contains functions for Groebner basis computations. For example, there are functions to check if a LIST of polynomials is a Groebner basis (via IsGB(G)), enumerate (reduced) (partial) Groebner bases (via GB(G[,Optimize,OFlag,DB,LB]) and RedGB(G[,Optimize,OFlag,DB,LB])), and compute truncated Groebner bases (via TruncatedGB(G[,Optimize,OFlag,DB])) of finitely generated (two-sided) ideals. Consequently, we can apply the package to many algebraic applications, i.e. to compute Macaulay basis (via MB(Gb)) and the values of Hilbert function (via HF(Gb)), compute generating systems for leading term ideals, kernel of K-algebra homomorphism, intersection of ideals, etc.


Important issues about this package:

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

             Alias NC := $apcocoa/ncpoly;


(b) The very first step to use functions in this package is to set non-commutative polynomial ring environment via the command

             Use

For instance, the following command

             Use QQ[x[1..2],y[1..2]];

sets the ring to be the non-commutative polynomial ring generated by {x[1],x[2],y[1],y[2]} over the rational numbers. Note that, for the time being, the package only supports non-commutative polynomial rings over the rational field QQ and finite fields ZZ/(p) where p is a prime.


(c) The word ordering is set via the function

             NC.SetOrdering(Ordering)

where the parameter Ordering is a STRING indicating which ordering we are working with. Note that word orderings are induced by the order of indeterminates. And, for the time being, the package supports the following word orderings, and among which "LLEX" is the default ordering.

       (b1) "LLEX": the length-lexicographic ordering

       (b2) "ELIM": an elimination ordering

       (b3) "LRLEX": the length-reverse-lexicographic ordering

       (b4) "DEGREVLEX": the degree-reverse-lexicographic ordering

For instance, the following commands

             Use ZZ/(2)[a,b,c,d];

             NC.SetOrdering("LLEX");

define the non-commutative polynomial ring generated by {a,b,c,d} over the binary field {0,1}, and set the word ordering to be the length-lexicographic ordering induced by a>b>c>d.


(d) One can use the function

             NC.RingEnv();

to get basic information on the working polynomial ring.


Representation of non-commutative polynomials in this package

Retrieved from "http://apcocoa.uni-passau.de/wiki/index.php?title=Category:ApCoCoA-1:Package_ncpoly&oldid=13071"