Difference between revisions of "ApCoCoA-1:NC.SetOrdering"

From ApCoCoAWiki
(New page: <command> <title>NC.SetOrdering</title> <short_description> Set (admissible) ordering. </short_description> <syntax> NC.SetOrdering(Ordering) </syntax> <description> <itemize> <item>@param...)
 
m (replaced <quotes> tag by real quotes)
 
(42 intermediate revisions by 7 users not shown)
Line 1: Line 1:
 +
{{Version|1}}
 
<command>
 
<command>
 
<title>NC.SetOrdering</title>
 
<title>NC.SetOrdering</title>
 
<short_description>
 
<short_description>
−
Set (admissible) ordering.
+
Set a word ordering on the monoid of all words in a non-commutative polynomial ring.
 
</short_description>
 
</short_description>
 
<syntax>
 
<syntax>
−
NC.SetOrdering(Ordering)
+
NC.SetOrdering(Ordering:STRING)
 
</syntax>
 
</syntax>
 
<description>
 
<description>
 +
Note that a <em>word ordering</em> is a well-ordering which is compatible with multiplication. The default ordering is LLEX (the length-lexicographic ordering).
 +
 +
In the following, we let <tt>W^n</tt> be the monoid of all words generated by <tt>{x[1],x[2],...,x[n]}</tt>. We define the <tt>non-commutative left-to-right lexicographic ordering</tt> LEX on <tt>W^n</tt> as follows. For two words <tt>W, W'</tt> in <tt>W^n</tt>, we say <tt>W&gt;_{Lex}W'</tt> if we have <tt>W=W'W_{1}</tt> for some non-empty word <tt>W_{1}</tt> in <tt>W^n</tt>, or if we have <tt>W=W_{1}x[i]W_{2}, W'=W_{1}x[j]W_{3}</tt> for some words <tt>W_{1},W_{2},W_{3}</tt> in <tt>W^n</tt> and <tt>i&lt;j</tt>. Thus, we have <tt>x[1]&gt;_{LEX}x[2]&gt;_{LEX}...&gt;_{LEX}x[n]</tt>. Note that LEX is not a word ordering on <tt>W^n</tt>. Given two words <tt>W, W'</tt> in <tt>W^n</tt>, we define word orderings LLEX, ELIM, LRLEX, and DEGREVLEX on <tt>W^n</tt> as follows.
 +
<itemize>
 +
<item>LLEX: we say <tt>W&gt;_{LLEX}W'</tt> if <tt>len(W)&gt;len(W')</tt>, or <tt>len(W)=len(W')</tt> and <tt>W</tt> is lexicographically larger than <tt>W'</tt>.</item>
 +
 +
<item>ELIM: it first compares the associated commutative terms lexicographically and then breaks ties using the non-commutative lexicographic ordering with respect to <tt>x[1]&gt;_{LEX}...&gt;_{LEX}x[n]</tt>. That is, we say <tt>W&gt;_{ELIM}W'</tt> if <tt>W</tt> is lexicographically larger than <tt>W'</tt> by considering them as two terms in the commutative case, or <tt>W=W'</tt> as two commutative terms and <tt>W&gt;_{Lex}W'</tt> (<tt>W</tt> is lexicographically larger than <tt>W'</tt> by considering them as two words in the non-commutative case). Thus, the elimination ordering ELIM first eliminates the indeterminate <tt>x[1]</tt>, and then <tt>x[2]</tt>, and then <tt>x[3]</tt>, and so on and so forth.</item>
 +
 +
<item>LRLEX: we say <tt>W&gt;_{LRLEX}W'</tt> if <tt>len(W)&gt;len(W')</tt>, or <tt>len(W)=len(W')</tt> and <tt>W</tt> is larger than <tt>W'</tt> by the non-commutative right-to-left lexicographic ordering.</item>
 +
</itemize>
 +
A word ordering on is said to be <em>length compatible</em> if <tt>len(W)>len(W')</tt> implies <tt>W</tt> is larger than <tt>W'</tt> for all <tt>W, W'</tt> in <tt>W^n</tt>. For instance, LLEX and LRLEX are length compatible while ELIM is not.
 +
<par/>
 +
Note that each word ordering is induced by the order of indeterminates (see <ref>ApCoCoA-1:Use|Use</ref>). For instance, assume that we are working in the ring QQ[x[1..2],y[1..2],z]. Then word ordering are induced by x[1]&gt;x[2]&gt;y[1]&gt;y[1]&gt;z.
 
<itemize>
 
<itemize>
−
<item>@param <em>X</em>: an STRING which is an alphabet (indeterminates) of a free associative K-algebra. Every letter in <tt>X</tt> should occurrence only once. And the order of letters in <tt>X</tt> is important since it will induce an admissible ordering. </item>
+
<item>@param <em>Ordering</em>: a STRING, which indicates a word ordering. For the time being, the package supports "LLEX" (the length-lexicographic ordering), "ELIM" (an elimination ordering),"LRLEX" (the length-reverse-lexicographic ordering), and "DEGREVLEX" (the degree-reverse-lexicographic ordering).</item>
 
</itemize>
 
</itemize>
 
<example>
 
<example>
−
NC.SetX(<quotes>abc</quotes>);
 
 
NC.RingEnv();
 
NC.RingEnv();
−
Coefficient ring : Q (float type in C++)
+
 
−
Alphabet : abc
+
Coefficient field : CoCoA::QQ
 +
Indeterminates : ["x[1]", "y[1]", "z[1]"]
 +
Word ordering : LLEX
 +
 
 +
-------------------------------
 +
NC.SetOrdering("ELIM");
 +
NC.RingEnv();
 +
 
 +
Coefficient field : CoCoA::QQ
 +
Indeterminates : ["x[1]", "y[1]", "z[1]"]
 +
Word ordering : ELIM
  
 
-------------------------------
 
-------------------------------
Line 21: Line 44:
 
</description>
 
</description>
 
<seealso>
 
<seealso>
−
<see>NC.Add</see>
+
<see>ApCoCoA-1:Use|Use</see>
−
<see>NC.GB</see>
 
−
<see>NC.IsGB</see>
 
−
<see>NC.LC</see>
 
−
<see>NC.LT</see>
 
−
<see>NC.LTIdeal</see>
 
−
<see>NC.Multiply</see>
 
−
<see>NC.NR</see>
 
−
<see>NC.SetFp</see>
 
−
<see>NC.SetX</see>
 
−
<see>NC.Subtract</see>
 
−
<see>Gbmr.MRSubtract</see>
 
−
<see>Gbmr.MRMultiply</see>
 
−
<see>Gbmr.MRBP</see>
 
−
<see>Gbmr.MRIntersection</see>
 
−
<see>Gbmr.MRKernelOfHomomorphism</see>
 
−
<see>Gbmr.MRMinimalPolynomials</see>
 
−
<see>Introduction to CoCoAServer</see>
 
 
</seealso>
 
</seealso>
 
<types>
 
<types>
−
<type>apcocoaserver</type>
+
<type>polynomial</type>
−
<type>groebner</type>
+
<type>non_commutative</type>
 
</types>
 
</types>
 +
<key>ncpoly.SetOrdering</key>
 
<key>NC.SetOrdering</key>
 
<key>NC.SetOrdering</key>
 
<key>SetOrdering</key>
 
<key>SetOrdering</key>
−
<wiki-category>Package_gbmr</wiki-category>
+
<wiki-category>ApCoCoA-1:Package_ncpoly</wiki-category>
 
</command>
 
</command>

Latest revision as of 13:36, 29 October 2020

This article is about a function from ApCoCoA-1.

NC.SetOrdering

Set a word ordering on the monoid of all words in a non-commutative polynomial ring.

Syntax

NC.SetOrdering(Ordering:STRING)

Description

Note that a word ordering is a well-ordering which is compatible with multiplication. The default ordering is LLEX (the length-lexicographic ordering).

In the following, we let W^n be the monoid of all words generated by {x[1],x[2],...,x[n]}. We define the non-commutative left-to-right lexicographic ordering LEX on W^n as follows. For two words W, W' in W^n, we say W>_{Lex}W' if we have W=W'W_{1} for some non-empty word W_{1} in W^n, or if we have W=W_{1}x[i]W_{2}, W'=W_{1}x[j]W_{3} for some words W_{1},W_{2},W_{3} in W^n and i<j. Thus, we have x[1]>_{LEX}x[2]>_{LEX}...>_{LEX}x[n]. Note that LEX is not a word ordering on W^n. Given two words W, W' in W^n, we define word orderings LLEX, ELIM, LRLEX, and DEGREVLEX on W^n as follows.

  • LLEX: we say W>_{LLEX}W' if len(W)>len(W'), or len(W)=len(W') and W is lexicographically larger than W'.

  • ELIM: it first compares the associated commutative terms lexicographically and then breaks ties using the non-commutative lexicographic ordering with respect to x[1]>_{LEX}...>_{LEX}x[n]. That is, we say W>_{ELIM}W' if W is lexicographically larger than W' by considering them as two terms in the commutative case, or W=W' as two commutative terms and W>_{Lex}W' (W is lexicographically larger than W' by considering them as two words in the non-commutative case). Thus, the elimination ordering ELIM first eliminates the indeterminate x[1], and then x[2], and then x[3], and so on and so forth.

  • LRLEX: we say W>_{LRLEX}W' if len(W)>len(W'), or len(W)=len(W') and W is larger than W' by the non-commutative right-to-left lexicographic ordering.

A word ordering on is said to be length compatible if len(W)>len(W') implies W is larger than W' for all W, W' in W^n. For instance, LLEX and LRLEX are length compatible while ELIM is not.

Note that each word ordering is induced by the order of indeterminates (see Use). For instance, assume that we are working in the ring QQ[x[1..2],y[1..2],z]. Then word ordering are induced by x[1]>x[2]>y[1]>y[1]>z.

  • @param Ordering: a STRING, which indicates a word ordering. For the time being, the package supports "LLEX" (the length-lexicographic ordering), "ELIM" (an elimination ordering),"LRLEX" (the length-reverse-lexicographic ordering), and "DEGREVLEX" (the degree-reverse-lexicographic ordering).

Example

NC.RingEnv();

Coefficient field : CoCoA::QQ
Indeterminates : ["x[1]", "y[1]", "z[1]"]
Word ordering : LLEX

-------------------------------
NC.SetOrdering("ELIM");
NC.RingEnv();

Coefficient field : CoCoA::QQ
Indeterminates : ["x[1]", "y[1]", "z[1]"]
Word ordering : ELIM

-------------------------------

See also

Use




Retrieved from "http://apcocoa.uni-passau.de/wiki/index.php?title=ApCoCoA-1:NC.SetOrdering&oldid=16103"