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

From ApCoCoAWiki
m (replaced <quotes> tag by real quotes)
 
(9 intermediate revisions by 3 users not shown)
Line 1: Line 1:
 +
{{Version|1}}
 
<command>
 
<command>
 
<title>NC.SetOrdering</title>
 
<title>NC.SetOrdering</title>
 
<short_description>
 
<short_description>
 
Set a word ordering on the monoid of all words in a non-commutative polynomial ring.
 
Set a word ordering on the monoid of all words in a non-commutative polynomial ring.
<par/>
+
</short_description>
Note that a <em>word ordering</em> is a well-ordering which is compatible with multiplication. The default ordering is <quotes>LLEX</quotes> (the length-lexicographic ordering).
+
<syntax>
 +
NC.SetOrdering(Ordering:STRING)
 +
</syntax>
 +
<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> <quotes>LEX</quotes> 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 <quotes>LEX</quotes> 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 <quotes>LLEX</quotes>, <quotes>ELIM</quotes>, <quotes>LRLEX</quotes>, and <quotes>DEGREVLEX</quotes> on <tt>W^n</tt> as follows.
+
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>
 
<itemize>
<item><quotes>LLEX</quotes>: 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>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><quotes>ELIM</quotes>: 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 <quotes>ELIM</quotes> 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>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><quotes>LRLEX</quotes>: 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>
+
<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>
 
</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, <quotes>LLEX</quotes> and <quotes>LRLEX</quotes> are length compatible while <quotes>ELIM</quotes> is not.
+
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.
</short_description>
+
<par/>
<syntax>
+
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.
NC.SetOrdering(Ordering:STRING)
 
</syntax>
 
<description>
 
Note that each word ordering is induced by the order of indeterminates (see <ref>Use</ref>). For instance, assume that we are working in the ring QQ[x[1..2],y[1..2],z]. Then the word ordering is induced by x[1]&gt;x[2]&gt;y[1]&gt;y[1]&gt;z.
 
 
<itemize>
 
<itemize>
<item>@param <em>Ordering</em>: a string which indicates a word ordering. For the time being, the package supports <quotes>LLEX</quotes> (the length-lexicographic ordering), <quotes>ELIM</quotes> (an elimination ordering),<quotes>LRLEX</quotes> (the length-reverse-lexicographic ordering), and <quotes>DEGREVLEX</quotes> (the degree-reverse-lexicographic 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.RingEnv();
 
NC.RingEnv();
Coefficient ring : Q
+
 
Ordering : LLEX
+
Coefficient field : CoCoA::QQ
 +
Indeterminates : ["x[1]", "y[1]", "z[1]"]
 +
Word ordering : LLEX
 +
 
 
-------------------------------
 
-------------------------------
NC.SetOrdering(<quotes>ELIM</quotes>);
+
NC.SetOrdering("ELIM");
 
NC.RingEnv();
 
NC.RingEnv();
Coefficient ring : Q
+
 
Ordering : ELIM
+
Coefficient field : CoCoA::QQ
 +
Indeterminates : ["x[1]", "y[1]", "z[1]"]
 +
Word ordering : ELIM
 +
 
 
-------------------------------
 
-------------------------------
 
</example>
 
</example>
 
</description>
 
</description>
 
<seealso>
 
<seealso>
<see>Use</see>
+
<see>ApCoCoA-1:Use|Use</see>
 
</seealso>
 
</seealso>
 
<types>
 
<types>
Line 46: Line 53:
 
<key>NC.SetOrdering</key>
 
<key>NC.SetOrdering</key>
 
<key>SetOrdering</key>
 
<key>SetOrdering</key>
<wiki-category>Package_ncpoly</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