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

From ApCoCoAWiki
Line 6: Line 6:
 
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).
 
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).
  
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 (left-to-right) lexicographic ordering <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> <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.
 
<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><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>
Line 12: Line 12:
 
<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><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><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 right-to-left lexicographic ordering.</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>
 
</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, <quotes>LLEX</quotes> and <quotes>LRLEX</quotes> are length compatible while <quotes>ELIM</quotes> is not.
Line 20: Line 20:
 
</syntax>
 
</syntax>
 
<description>
 
<description>
Note that each word ordering is induced by the order of indeterminates. 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.
+
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 <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>
Line 36: Line 36:
 
</example>
 
</example>
 
</description>
 
</description>
 +
<seealso>
 +
<see>Use</see>
 +
</seealso>
 
<types>
 
<types>
 
<type>polynomial</type>
 
<type>polynomial</type>

Revision as of 14:54, 30 April 2013

NC.SetOrdering

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

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.

Syntax

NC.SetOrdering(Ordering:STRING)

Description

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 the word ordering is 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 ring : Q
Ordering : LLEX
-------------------------------
NC.SetOrdering(<quotes>ELIM</quotes>);
NC.RingEnv();
Coefficient ring : Q
Ordering : ELIM
-------------------------------

See also

Use