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

From ApCoCoAWiki
m (Andraschko moved page Category:Package ncpoly to Category:ApCoCoA-1:Package ncpoly: Clearer page title)
 
(11 intermediate revisions by 2 users not shown)
Line 1: Line 1:
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.
+
Package ncpoly is designed to enable us to do basic calculations 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.
  
  
Line 7: Line 7:
  
 
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; Alias NC := $apcocoa/ncpoly;
 
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; Alias NC := $apcocoa/ncpoly;
 +
 +
Note that, before ApCoCoA 1.9.0, the alias NC was used for the ApCoCoA package gbmr. Since ApCoCoA 1.9.0, the alias NC has been used for the package ncpoly, and the alias NCo has been used for the package gbmr.
  
  
Line 20: Line 22:
  
  
(c) The word ordering is set via the function
+
(c) 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
  
 
&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.SetOrdering(Ordering)
  
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 the parameter <tt>Ordering</tt> is a STRING indicating which ordering we are going to work 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.
  
 
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; (b1) "LLEX": the <em>length-lexicographic ordering</em>
 
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; (b1) "LLEX": the <em>length-lexicographic ordering</em>
Line 40: Line 42:
 
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; NC.SetOrdering("LLEX");
 
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; NC.SetOrdering("LLEX");
  
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>.
+
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>. See the function NC.SetOrdering for more details.
  
  
Line 50: Line 52:
  
  
<strong>Representation of non-commutative polynomials in this package</strong>
+
<strong>Representation of non-commutative polynomials in this package:</strong>
 +
 
 +
It is tricky to represent a non-commutative polynomial. In the package, every polynomial is represented as a LIST of monomials, and each monomial is a LIST such that each element in the LIST involves only one indeterminate or none (a constant). A polynomial represented in this way is said to be in the <em>CoCoAL format</em>. For instance, the polynomial
 +
 
 +
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <tt>f=2x[2]y[1]x[2]^2-9y[2]x[1]^2x[2]^3+5</tt>
 +
 
 +
is represented as
 +
 
 +
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; [[2x[1],y[1],x[2]^2], [-9y[2],x[1]^2,x[2]^3], [5]].
 +
 
 +
 
 +
Note that functions in this package are using the <strong>ApCoCoAServer</strong>. In the ApCoCoAServer (developed in C++), every polynomial is also represented as a LIST of LISTs, and each inner LIST contains a coefficient and a LIST of indices of indeterminates. A polynomial represented in this way is said to be in the <em>C format</em>. For instance, assume that the working ring is
 +
 
 +
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; Use QQ[x[1..2],y[1..2]];
 +
 
 +
then, indeterminates <tt>x[1],x[2],y[1],y[2]</tt> are indexed by <tt>1,2,3,4</tt>, respectively. Thus, polynomial <tt>f</tt> is represented in the C format as
  
 +
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; [[2, [1, 3, 2, 2]], [-9, [4, 1, 1, 2, 2, 2]], [5, []]].
  
 +
Two representations can be converted to each other via the functions
  
 +
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; NC.CoCoALToC(F); and NC.CToCoCoAL(F);
  
[[Category:ApCoCoA_Manual]]
+
[[Category:ApCoCoA-1 Manual]]

Latest revision as of 15:17, 2 October 2020

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;

Note that, before ApCoCoA 1.9.0, the alias NC was used for the ApCoCoA package gbmr. Since ApCoCoA 1.9.0, the alias NC has been used for the package ncpoly, and the alias NCo has been used for the package gbmr.


(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) A word ordering on a monoid is a well-ordering that is compatible with multiplication. One can set word orderings via the function

             NC.SetOrdering(Ordering)

where the parameter Ordering is a STRING indicating which ordering we are going to work 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. See the function NC.SetOrdering for more details.


(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:

It is tricky to represent a non-commutative polynomial. In the package, every polynomial is represented as a LIST of monomials, and each monomial is a LIST such that each element in the LIST involves only one indeterminate or none (a constant). A polynomial represented in this way is said to be in the CoCoAL format. For instance, the polynomial

             f=2x[2]y[1]x[2]^2-9y[2]x[1]^2x[2]^3+5

is represented as

             [[2x[1],y[1],x[2]^2], [-9y[2],x[1]^2,x[2]^3], [5]].


Note that functions in this package are using the ApCoCoAServer. In the ApCoCoAServer (developed in C++), every polynomial is also represented as a LIST of LISTs, and each inner LIST contains a coefficient and a LIST of indices of indeterminates. A polynomial represented in this way is said to be in the C format. For instance, assume that the working ring is

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

then, indeterminates x[1],x[2],y[1],y[2] are indexed by 1,2,3,4, respectively. Thus, polynomial f is represented in the C format as

             [[2, [1, 3, 2, 2]], [-9, [4, 1, 1, 2, 2, 2]], [5, []]].

Two representations can be converted to each other via the functions

             NC.CoCoALToC(F); and NC.CToCoCoAL(F);