Difference between revisions of "ApCoCoA-1:NC.SetOrdering"
m (replaced <quotes> tag by real quotes) |
|||
| (19 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 | + | Set a word ordering on the monoid of all words in a non-commutative polynomial ring. |
</short_description> | </short_description> | ||
<syntax> | <syntax> | ||
| Line 8: | Line 9: | ||
</syntax> | </syntax> | ||
<description> | <description> | ||
| − | Note that | + | 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>_{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<j</tt>. Thus, we have <tt>x[1]>_{LEX}x[2]>_{LEX}...>_{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> | + | <item>LLEX: we say <tt>W>_{LLEX}W'</tt> if <tt>len(W)>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]>_{LEX}...>_{LEX}x[n]</tt>. That is, we say <tt>W>_{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>_{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>_{LRLEX}W'</tt> if <tt>len(W)>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, 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]>x[2]>y[1]>y[1]>z. | ||
<itemize> | <itemize> | ||
| − | <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 | + | |
| − | + | Coefficient field : CoCoA::QQ | |
| + | Indeterminates : ["x[1]", "y[1]", "z[1]"] | ||
| + | Word ordering : LLEX | ||
------------------------------- | ------------------------------- | ||
| − | NC.SetOrdering( | + | NC.SetOrdering("ELIM"); |
NC.RingEnv(); | NC.RingEnv(); | ||
| − | Coefficient | + | |
| − | + | Coefficient field : CoCoA::QQ | |
| + | Indeterminates : ["x[1]", "y[1]", "z[1]"] | ||
| + | Word ordering : ELIM | ||
------------------------------- | ------------------------------- | ||
| Line 34: | Line 44: | ||
</description> | </description> | ||
<seealso> | <seealso> | ||
| − | <see> | + | <see>ApCoCoA-1:Use|Use</see> |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
</seealso> | </seealso> | ||
<types> | <types> | ||
| + | <type>polynomial</type> | ||
<type>non_commutative</type> | <type>non_commutative</type> | ||
</types> | </types> | ||
| − | <key> | + | <key>ncpoly.SetOrdering</key> |
<key>NC.SetOrdering</key> | <key>NC.SetOrdering</key> | ||
<key>SetOrdering</key> | <key>SetOrdering</key> | ||
| − | <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
