@@ -1,296 +1,296 @@ -\documentstyle[11pt,reduce]{article} -\title{NCPOLY: Computation in non--commutative polynomial ideals} -\date{} -\author{ -Herbert Melenk\\[0.05in] -Konrad--Zuse--Zentrum f\"ur Informationstechnik Berlin \\ -Heilbronner Strasse 10 \\ -D--10711 Berlin -- Wilmersdorf \\ -Federal Republic of Germany \\[0.05in] -E--mail: melenk@zib--berlin.de \\[0.1in] -Joachim Apel\\[0.05in] -Institut f\"ur Informatik \\[0.05in] -Universit\"at Leipzig \\[0.05in] -Augustusplatz 10--11\\[0.05in] -D--04109 Leipzig \\[0.05in] -Federal Republic of Germany \\[0.05in] -E--mail: apel@informatik.uni--leipzig.de \\[0.05in] -} - -\begin{document} -\maketitle - -\index{Groebner Bases} -\section{Introduction} - -{\small REDUCE} supports a very general mechanism for computing -with objects under a non--commutative multiplication, where -commutator relations must be introduced explicitly by rule -sets when needed. The package {\bf NCPOLY} allows you to -set up automatically a consistent environment for computing in an algebra -where the non--commutativity is defined by Lie-bracket commutators. -The package uses the {\small REDUCE} {\bf noncom} -mechanism for elementary polynomial arithmetic; the commutator -rules are automatically computed from the Lie brackets. -You can perform polynomial arithmetic directly, including -{\bf division} and {\bf factorization}. -Additionally {\bf NCPOLY} supports computations in a one sided ideal (left or right), -especially one sided {\bf Gr\"obner} bases and {\bf polynomial reduction}. - -\section{Setup, Cleanup} - -Before the computations can start the environment for a -non--commutative computation must be defined by a -call to {\bf nc\_setup}: -\begin{verbatim} - nc_setup([,][,]); -\end{verbatim} -where - -$$ is a list of variables; these must include the -non--commutative quantities. - -$$ is a list of equations \verb&* - *=& -where $$ and $$ are members of $$, and $$ is -a polynomial. - -$$ is either $left$ or $right$ selecting a left or a -right one sided ideal. The initial direction is $left$. - -{\bf nc\_setup} generates from $$ the necessary -rules to support an algebra where all monomials are -ordered corresponding to the given variable sequence. -All pairs of variables which are not explicitly covered in -the commutator set are considered as commutative and the -corresponding rules are also activated. - -The second parameter in {\bf nc\_setup} may be -omitted if the operator is called for the second time, -e.g. with a reordered variable sequence. In such a case -the last commutator set is used again. - -Remarks: \begin{itemize} -\item The variables need not be declared {\bf noncom} - - {\bf nc\_setup} performs all necessary declarations. -\item The variables need not be formal operator expressions; - {\bf nc\_setup} encapsulates a variable $x$ internally - as \verb+nc!*(!_x)+ expressions anyway where the operator $nc!*$ - keeps the noncom property. -\item The commands {\bf order} and {\bf korder} should be avoided - because {\bf nc\_setup} sets these such that the computation - results are printed in the correct term order. -\end{itemize} - -Example: -\begin {verbatim} - nc_setup({KK,NN,k,n}, - {NN*n-n*NN= NN, KK*k-k*KK= KK}); - - NN*n; -> NN*n - n*NN; -> NN*n - NN - nc_setup({k,n,KK,NN}); - NN*n - NN -> n*NN; - -\end{verbatim} -Here $KK,NN,k,n$ are non--commutative variables where -the commutators are described as $[NN,n]=NN$, $[KK,k]=KK$. - -The current term order must be compatible with the commutators: -the product $*$ must precede all terms on the right hand -side $$ under the current term order. Consequently -\begin{itemize} -\item the maximal degree of $$ or $$ in $$ is 1, -\item in a total degree ordering the total degree of $$ may be -not higher than 1, -\item in an elimination degree order (e.g. $lex$) all variables in -$$ must be below the minimum of $$ and $$. -\item If $$ does not contain any variables or has at most $$ or -$$, any term order can be selected. -\end{itemize} - -If you want to use the non--commutative variables or results from -non--commutative computations later in commutative operations -it might be necessary to switch off the non--commutative -evaluation mode because not -all operators in REDUCE are prepared for that environment. In -such a case use the command -\begin{verbatim} - nc_cleanup; -\end{verbatim} -without parameters. It removes all internal rules and definitions -which {\bf nc\_setup} had introduced. To reactive non--commutative -call {\bf nc\_setup} again. - -\section{Left and right ideals} - -A (polynomial) left ideal $L$ is defined by the axioms - -$u \in L, v \in L \Longrightarrow u+v \in L$ - -$u \in L \Longrightarrow k*u \in L$ for an arbitrary polynomial $k$ - -where ``*'' is the non--commutative multiplication. Correspondingly, -a right ideal $R$ is defined by - -$u \in R, v \in R \Longrightarrow u+v \in R$ - -$u \in R \Longrightarrow u*k \in R$ for an arbitrary polynomial $k$ - -\section{Gr\"obner bases} - -When a non--commutative environment has been set up -by {\bf nc\_setup}, a basis for a left or right polynomial ideal -can be transformed into a Gr\"obner basis by the operator -{\bf nc\_groebner}: -\begin{verbatim} - nc_groebner(); -\end{verbatim} -Note that the variable set and variable sequence must be -defined before in the {\bf nc\_setup} call. The term order -for the Gr\"obner calculation can be set by using the -{\bf torder} declaration. The internal steps of the -Gr\"obner calculation can be watched by setting the -switches {\bf trgroeb} (=list all internal basis polynomials) -or {\bf trgroebs} (=list additionally the $S$-polynomials) -\footnote{The command \verb+lisp(!*trgroebfull:=t);+ causes additionally -all elementary polynomial operations to be printed.}. - - -For details about {\bf torder}, {\bf trgroeb} and {\bf trgroebs} -see the {\bf {\small REDUCE} GROEBNER} manual. -\begin{verbatim} -2: nc_setup({k,n,NN,KK},{NN*n-n*NN=NN,KK*k-k*KK=KK},left); - -3: p1 := (n-k+1)*NN - (n+1); - -p1 := - k*nn + n*nn - n + nn - 1 - -4: p2 := (k+1)*KK -(n-k); - -p2 := k*kk + k - n + kk - -5: nc_groebner ({p1,p2}); - -{k*nn - n*nn + n - nn + 1, - - k*kk + k - n + kk, - - n*nn*kk - n*kk - n + nn*kk - kk - 1} - -\end{verbatim} -Important: Do not use the operators of the GROEBNER -package directly as they would not consider the non--commutative -multiplication. - -\section{Left or right polynomial division} - -The operator {\bf nc\_divide} computes the one sided quotient and remainder of -two polynomials: -\begin{verbatim} - nc_divide(,); -\end{verbatim} -The result is a list with quotient and remainder. -The division is performed as a pseudo--division, multiplying -$$ by coefficients if necessary. The result $\{,\}$ -is defined by the relation - - $*=* + $ for direction $left$ and - - $*=* + $ for direction $right$, - -where $$ is an expression that does not contain any of the -ideal variables, and the leading term of $$ is lower than -the leading term of $$ according to the actual term order. - -\section{Left or right polynomial reduction} - -For the computation of the one sided remainder of a polynomial -modulo a given set of other polynomials the operator -{\bf nc\_preduce} may be used: -\begin{verbatim} - nc_preduce(,); -\end{verbatim} -The result of the reduction is unique (canonical) if -and only if $$ is a one sided Gr\"obner basis. -Then the computation is at the same time an ideal -membership test: if the result is zero, the -polynomial is member of the ideal, otherwise not. - -\section{Factorization} - -Polynomials in a non--commutative ring cannot be factored -using the ordinary {\bf factorize} command of {\small REDUCE}. -Instead one of the operators of this section must be used: -\begin{verbatim} - nc_factorize(); -\end{verbatim} -The result is a list of factors of $$. A list -with the input expression is returned if it is irreducible. - -As non--commutative factorization is not unique, there is -an additional operator which computes all possible factorizations -\begin{verbatim} - nc_factorize_all(); -\end{verbatim} -The result is a list of factor decompositions of $$. -If there are no factors at all the result list has only one -member which is a list containing the input polynomial. - -In contrast to factoring in commutative polynomial rings, the non--commutative -factorization is rather time consuming. Therefore two additional -operators allow you to reduce the amount of computing time when -you look only for isolated factors in special context, e.g. factors -with a limited degree or factors which contain only explicitly -specified variables: -\begin{verbatim} - left_factor([,[,]]) - right_factor([,[,]]) - left_factors([,[,]]) - right_factors([,[,]]) -\end{verbatim} -where $$ is the form under investigation, -$$ is an optional list of variables which must appear in the -factor, and $$ -is an optional integer degree bound for the total degree of the -factor, a zero for an unbounded search, or a monomial -(product of powers of the variables) where each exponent -is an individual degree bound for its base variable; unmentioned -variables are allowed in arbitrary degree. The operators -$*\_factor$ stop when they have found one factor, while -the operators $*\_factors$ select all one--sided factors -within the given range. If there is no factor of the -desired type, an empty list is returned by $*\_factors$ -while the routines $*\_factor$ return the input polynomial. - - -The share variable $nc\_factor\_time$ sets an upper limit -for the time to be spent for a call to the non--commutative -factorizer. If the value is a positive integer, a -factorization is terminated with an error message as soon -as the time limit is reached. The time units are milliseconds. - -\section{Output of expressions} - -It is often desirable to have the commutative parts (coefficients) -in a non--commutative operation condensed by factorization. The operator -\begin{verbatim} - nc_compact() -\end{verbatim} -collects the coefficients to the powers of the lowest possible -non-commutative variable. -\begin{verbatim} -load ncpoly; - -nc_setup({n,NN},{NN*n-n*NN=NN})$ -p1 := n**4 + n**2*nn + 4*n**2 + 4*n*nn + 4*nn + 4; - - 4 2 2 -p1 := n + n *nn + 4*n + 4*n*nn + 4*nn + 4 - -nc_compact p1; - - 2 2 2 -(n + 2) + (n + 2) *nn -\end{verbatim} -\end{document} - +\documentstyle[11pt,reduce]{article} +\title{NCPOLY: Computation in non--commutative polynomial ideals} +\date{} +\author{ +Herbert Melenk\\[0.05in] +Konrad--Zuse--Zentrum f\"ur Informationstechnik Berlin \\ +Heilbronner Strasse 10 \\ +D--10711 Berlin -- Wilmersdorf \\ +Federal Republic of Germany \\[0.05in] +E--mail: melenk@zib--berlin.de \\[0.1in] +Joachim Apel\\[0.05in] +Institut f\"ur Informatik \\[0.05in] +Universit\"at Leipzig \\[0.05in] +Augustusplatz 10--11\\[0.05in] +D--04109 Leipzig \\[0.05in] +Federal Republic of Germany \\[0.05in] +E--mail: apel@informatik.uni--leipzig.de \\[0.05in] +} + +\begin{document} +\maketitle + +\index{Groebner Bases} +\section{Introduction} + +{\small REDUCE} supports a very general mechanism for computing +with objects under a non--commutative multiplication, where +commutator relations must be introduced explicitly by rule +sets when needed. The package {\bf NCPOLY} allows you to +set up automatically a consistent environment for computing in an algebra +where the non--commutativity is defined by Lie-bracket commutators. +The package uses the {\small REDUCE} {\bf noncom} +mechanism for elementary polynomial arithmetic; the commutator +rules are automatically computed from the Lie brackets. +You can perform polynomial arithmetic directly, including +{\bf division} and {\bf factorization}. +Additionally {\bf NCPOLY} supports computations in a one sided ideal (left or right), +especially one sided {\bf Gr\"obner} bases and {\bf polynomial reduction}. + +\section{Setup, Cleanup} + +Before the computations can start the environment for a +non--commutative computation must be defined by a +call to {\bf nc\_setup}: +\begin{verbatim} + nc_setup([,][,]); +\end{verbatim} +where + +$$ is a list of variables; these must include the +non--commutative quantities. + +$$ is a list of equations \verb&* - *=& +where $$ and $$ are members of $$, and $$ is +a polynomial. + +$$ is either $left$ or $right$ selecting a left or a +right one sided ideal. The initial direction is $left$. + +{\bf nc\_setup} generates from $$ the necessary +rules to support an algebra where all monomials are +ordered corresponding to the given variable sequence. +All pairs of variables which are not explicitly covered in +the commutator set are considered as commutative and the +corresponding rules are also activated. + +The second parameter in {\bf nc\_setup} may be +omitted if the operator is called for the second time, +e.g. with a reordered variable sequence. In such a case +the last commutator set is used again. + +Remarks: \begin{itemize} +\item The variables need not be declared {\bf noncom} - + {\bf nc\_setup} performs all necessary declarations. +\item The variables need not be formal operator expressions; + {\bf nc\_setup} encapsulates a variable $x$ internally + as \verb+nc!*(!_x)+ expressions anyway where the operator $nc!*$ + keeps the noncom property. +\item The commands {\bf order} and {\bf korder} should be avoided + because {\bf nc\_setup} sets these such that the computation + results are printed in the correct term order. +\end{itemize} + +Example: +\begin {verbatim} + nc_setup({KK,NN,k,n}, + {NN*n-n*NN= NN, KK*k-k*KK= KK}); + + NN*n; -> NN*n + n*NN; -> NN*n - NN + nc_setup({k,n,KK,NN}); + NN*n - NN -> n*NN; + +\end{verbatim} +Here $KK,NN,k,n$ are non--commutative variables where +the commutators are described as $[NN,n]=NN$, $[KK,k]=KK$. + +The current term order must be compatible with the commutators: +the product $*$ must precede all terms on the right hand +side $$ under the current term order. Consequently +\begin{itemize} +\item the maximal degree of $$ or $$ in $$ is 1, +\item in a total degree ordering the total degree of $$ may be +not higher than 1, +\item in an elimination degree order (e.g. $lex$) all variables in +$$ must be below the minimum of $$ and $$. +\item If $$ does not contain any variables or has at most $$ or +$$, any term order can be selected. +\end{itemize} + +If you want to use the non--commutative variables or results from +non--commutative computations later in commutative operations +it might be necessary to switch off the non--commutative +evaluation mode because not +all operators in REDUCE are prepared for that environment. In +such a case use the command +\begin{verbatim} + nc_cleanup; +\end{verbatim} +without parameters. It removes all internal rules and definitions +which {\bf nc\_setup} had introduced. To reactive non--commutative +call {\bf nc\_setup} again. + +\section{Left and right ideals} + +A (polynomial) left ideal $L$ is defined by the axioms + +$u \in L, v \in L \Longrightarrow u+v \in L$ + +$u \in L \Longrightarrow k*u \in L$ for an arbitrary polynomial $k$ + +where ``*'' is the non--commutative multiplication. Correspondingly, +a right ideal $R$ is defined by + +$u \in R, v \in R \Longrightarrow u+v \in R$ + +$u \in R \Longrightarrow u*k \in R$ for an arbitrary polynomial $k$ + +\section{Gr\"obner bases} + +When a non--commutative environment has been set up +by {\bf nc\_setup}, a basis for a left or right polynomial ideal +can be transformed into a Gr\"obner basis by the operator +{\bf nc\_groebner}: +\begin{verbatim} + nc_groebner(); +\end{verbatim} +Note that the variable set and variable sequence must be +defined before in the {\bf nc\_setup} call. The term order +for the Gr\"obner calculation can be set by using the +{\bf torder} declaration. The internal steps of the +Gr\"obner calculation can be watched by setting the +switches {\bf trgroeb} (=list all internal basis polynomials) +or {\bf trgroebs} (=list additionally the $S$-polynomials) +\footnote{The command \verb+lisp(!*trgroebfull:=t);+ causes additionally +all elementary polynomial operations to be printed.}. + + +For details about {\bf torder}, {\bf trgroeb} and {\bf trgroebs} +see the {\bf {\small REDUCE} GROEBNER} manual. +\begin{verbatim} +2: nc_setup({k,n,NN,KK},{NN*n-n*NN=NN,KK*k-k*KK=KK},left); + +3: p1 := (n-k+1)*NN - (n+1); + +p1 := - k*nn + n*nn - n + nn - 1 + +4: p2 := (k+1)*KK -(n-k); + +p2 := k*kk + k - n + kk + +5: nc_groebner ({p1,p2}); + +{k*nn - n*nn + n - nn + 1, + + k*kk + k - n + kk, + + n*nn*kk - n*kk - n + nn*kk - kk - 1} + +\end{verbatim} +Important: Do not use the operators of the GROEBNER +package directly as they would not consider the non--commutative +multiplication. + +\section{Left or right polynomial division} + +The operator {\bf nc\_divide} computes the one sided quotient and remainder of +two polynomials: +\begin{verbatim} + nc_divide(,); +\end{verbatim} +The result is a list with quotient and remainder. +The division is performed as a pseudo--division, multiplying +$$ by coefficients if necessary. The result $\{,\}$ +is defined by the relation + + $*=* + $ for direction $left$ and + + $*=* + $ for direction $right$, + +where $$ is an expression that does not contain any of the +ideal variables, and the leading term of $$ is lower than +the leading term of $$ according to the actual term order. + +\section{Left or right polynomial reduction} + +For the computation of the one sided remainder of a polynomial +modulo a given set of other polynomials the operator +{\bf nc\_preduce} may be used: +\begin{verbatim} + nc_preduce(,); +\end{verbatim} +The result of the reduction is unique (canonical) if +and only if $$ is a one sided Gr\"obner basis. +Then the computation is at the same time an ideal +membership test: if the result is zero, the +polynomial is member of the ideal, otherwise not. + +\section{Factorization} + +Polynomials in a non--commutative ring cannot be factored +using the ordinary {\bf factorize} command of {\small REDUCE}. +Instead one of the operators of this section must be used: +\begin{verbatim} + nc_factorize(); +\end{verbatim} +The result is a list of factors of $$. A list +with the input expression is returned if it is irreducible. + +As non--commutative factorization is not unique, there is +an additional operator which computes all possible factorizations +\begin{verbatim} + nc_factorize_all(); +\end{verbatim} +The result is a list of factor decompositions of $$. +If there are no factors at all the result list has only one +member which is a list containing the input polynomial. + +In contrast to factoring in commutative polynomial rings, the non--commutative +factorization is rather time consuming. Therefore two additional +operators allow you to reduce the amount of computing time when +you look only for isolated factors in special context, e.g. factors +with a limited degree or factors which contain only explicitly +specified variables: +\begin{verbatim} + left_factor([,[,]]) + right_factor([,[,]]) + left_factors([,[,]]) + right_factors([,[,]]) +\end{verbatim} +where $$ is the form under investigation, +$$ is an optional list of variables which must appear in the +factor, and $$ +is an optional integer degree bound for the total degree of the +factor, a zero for an unbounded search, or a monomial +(product of powers of the variables) where each exponent +is an individual degree bound for its base variable; unmentioned +variables are allowed in arbitrary degree. The operators +$*\_factor$ stop when they have found one factor, while +the operators $*\_factors$ select all one--sided factors +within the given range. If there is no factor of the +desired type, an empty list is returned by $*\_factors$ +while the routines $*\_factor$ return the input polynomial. + + +The share variable $nc\_factor\_time$ sets an upper limit +for the time to be spent for a call to the non--commutative +factorizer. If the value is a positive integer, a +factorization is terminated with an error message as soon +as the time limit is reached. The time units are milliseconds. + +\section{Output of expressions} + +It is often desirable to have the commutative parts (coefficients) +in a non--commutative operation condensed by factorization. The operator +\begin{verbatim} + nc_compact() +\end{verbatim} +collects the coefficients to the powers of the lowest possible +non-commutative variable. +\begin{verbatim} +load ncpoly; + +nc_setup({n,NN},{NN*n-n*NN=NN})$ +p1 := n**4 + n**2*nn + 4*n**2 + 4*n*nn + 4*nn + 4; + + 4 2 2 +p1 := n + n *nn + 4*n + 4*n*nn + 4*nn + 4 + +nc_compact p1; + + 2 2 2 +(n + 2) + (n + 2) *nn +\end{verbatim} +\end{document} +