@@ -1,129 +1,129 @@ -\documentstyle[12pt]{article} -\begin{document} -\begin{center} {\Large Polynomial Ideals} \end{center} -\begin{center} Arithmetic for polynomial ideals supported by -Gr\"obner bases \end{center} -\begin{center} Version 1.0 May 1992 \end{center} - -\begin{center} Herbert Melenk \\ Konrad-Zuse-Zentrum f\"ur -Informationstechnik \\ -Heilbronner Str. 10 \\ D1000 Berlin 31 \\ Federal Republic of Germany \\ -melenk@sc.zib-berlin.de \\ May 1992 \end{center} - -\section{Introduction} - -This package implements the basic arithmetic for polynomial ideals -by exploiting the Gr\"obner bases package of REDUCE. -In order to save computing time all intermediate Gr\"obner bases -are stored internally such that time consuming repetitions -are inhibited. A uniform setting facilitates the access. - -\section{Initialization} - -Prior to any computation the set of variables has to be declared -by calling the operator $I\_setting$ . E.g. in order to initiate -computations in the polynomial ring $Q[x,y,z]$ call -\begin{verbatim} - I_setting(x,y,z); -\end{verbatim} -A subsequent call to $I\_setting$ allows one to select another set -of variables; at the same time the internal data structures -are cleared in order to free memory resources. - -\section{Bases} - -An ideal is represented by a basis (set of polynomials) tagged -with the symbol $I$, e.g. -\begin{verbatim} - u := I(x*z-y**2, x**3-y*z); -\end{verbatim} -Alternatively a list of polynomials can be used as input basis; however, -all arithmetic results will be presented in the above form. The -operator $ideal2list$ allows one to convert an ideal basis into a -conventional REDUCE list. - -\subsection{Operators} - -Because of syntactical restrictions in REDUCE, special operators -have to be used for ideal arithmetic: - -\begin{verbatim} - .+ ideal sum (infix) - .* ideal product (infix) - .: ideal quotient (infix) - ./ ideal quotient (infix) - .= ideal equality test (infix) - subset ideal inclusion test (infix) - intersection ideal intersection (prefix,binary) - member test for membership in an ideal - (infix: polynomial and ideal) - gb Groebner basis of an ideal (prefix, unary) - ideal2list convert ideal basis to polynomial list - (prefix,unary) -\end{verbatim} - -Example: - -\begin{verbatim} - I(x+y,x^2) .* I(x-z); - - 2 2 2 - I(X + X*Y - X*Z - Y*Z,X*Y - Y *Z) -\end{verbatim} - -The test operators return the values 1 (=true) or 0 (=false) -such that they can be used in REDUCE $if-then-else$ statements -directly. - -The results of $sum,product, quotient,intersction$ are ideals -represented by their Gr\"obner basis in the current setting and -term order. The term order can be modified using the operator -$torder$ from the Gr\"obner package. Note that ideal equality -cannot be tested with the REDUCE equal sign: - -\begin{verbatim} - - I(x,y) = I(y,x) is false - I(x,y) .= I(y,x) is true - -\end{verbatim} - -\section{Algorithms} - -The operators $groebner$, $preduce$ and $idealquotient$ of the -REDUCE Gr\"obner package support the basic algorithms: - -$GB(Iu_1,u_2...) \rightarrow groebner(\{u_1,u_2...\},\{x,...\})$ - -$p \in I_1 \rightarrow p=0 \ mod \ I_1$ - -$I_1 : I(p) \rightarrow (I_1 \bigcap I(p)) / p \ elementwise$ - -\noindent -On top of these the Ideals package implements the following -operations: - - -$I(u_1,u_2...)+I(v_1,v_2...) \rightarrow GB(I(u_1,u_2...,v_1,v_2...))$ - - -$I(u_1,u_2...)*I(v_1,v_2...)\rightarrow - GB(I(u_1*v_1,u_1*v2,...,u_2*v_1,u_2*v_2...))$ - - -$I_1 \bigcap I_2 \rightarrow - Q[x,...] \bigcap GB_{lex}(t*I_1 + (1-t)*I_2,\{t,x,..\}) $ - - -$I_1 : I(p_1,p_2,...) \rightarrow I_1 : I(p_1) \bigcap I_1 : I(p_2) -\bigcap ...$ - -$I_1 = I_2 \rightarrow GB(I_1)=GB(I_2)$ - -$I_1 \subseteq I_2 - \rightarrow \ u_i \in I_2 \ \forall \ u_i \in I_1=I(u_1,u_2...)$ - -\section{Examples} - -Please consult the file $ideals.tst$. -\end{document} +\documentstyle[12pt]{article} +\begin{document} +\begin{center} {\Large Polynomial Ideals} \end{center} +\begin{center} Arithmetic for polynomial ideals supported by +Gr\"obner bases \end{center} +\begin{center} Version 1.0 May 1992 \end{center} + +\begin{center} Herbert Melenk \\ Konrad-Zuse-Zentrum f\"ur +Informationstechnik \\ +Heilbronner Str. 10 \\ D1000 Berlin 31 \\ Federal Republic of Germany \\ +melenk@sc.zib-berlin.de \\ May 1992 \end{center} + +\section{Introduction} + +This package implements the basic arithmetic for polynomial ideals +by exploiting the Gr\"obner bases package of REDUCE. +In order to save computing time all intermediate Gr\"obner bases +are stored internally such that time consuming repetitions +are inhibited. A uniform setting facilitates the access. + +\section{Initialization} + +Prior to any computation the set of variables has to be declared +by calling the operator $I\_setting$ . E.g. in order to initiate +computations in the polynomial ring $Q[x,y,z]$ call +\begin{verbatim} + I_setting(x,y,z); +\end{verbatim} +A subsequent call to $I\_setting$ allows one to select another set +of variables; at the same time the internal data structures +are cleared in order to free memory resources. + +\section{Bases} + +An ideal is represented by a basis (set of polynomials) tagged +with the symbol $I$, e.g. +\begin{verbatim} + u := I(x*z-y**2, x**3-y*z); +\end{verbatim} +Alternatively a list of polynomials can be used as input basis; however, +all arithmetic results will be presented in the above form. The +operator $ideal2list$ allows one to convert an ideal basis into a +conventional REDUCE list. + +\subsection{Operators} + +Because of syntactical restrictions in REDUCE, special operators +have to be used for ideal arithmetic: + +\begin{verbatim} + .+ ideal sum (infix) + .* ideal product (infix) + .: ideal quotient (infix) + ./ ideal quotient (infix) + .= ideal equality test (infix) + subset ideal inclusion test (infix) + intersection ideal intersection (prefix,binary) + member test for membership in an ideal + (infix: polynomial and ideal) + gb Groebner basis of an ideal (prefix, unary) + ideal2list convert ideal basis to polynomial list + (prefix,unary) +\end{verbatim} + +Example: + +\begin{verbatim} + I(x+y,x^2) .* I(x-z); + + 2 2 2 + I(X + X*Y - X*Z - Y*Z,X*Y - Y *Z) +\end{verbatim} + +The test operators return the values 1 (=true) or 0 (=false) +such that they can be used in REDUCE $if-then-else$ statements +directly. + +The results of $sum,product, quotient,intersction$ are ideals +represented by their Gr\"obner basis in the current setting and +term order. The term order can be modified using the operator +$torder$ from the Gr\"obner package. Note that ideal equality +cannot be tested with the REDUCE equal sign: + +\begin{verbatim} + + I(x,y) = I(y,x) is false + I(x,y) .= I(y,x) is true + +\end{verbatim} + +\section{Algorithms} + +The operators $groebner$, $preduce$ and $idealquotient$ of the +REDUCE Gr\"obner package support the basic algorithms: + +$GB(Iu_1,u_2...) \rightarrow groebner(\{u_1,u_2...\},\{x,...\})$ + +$p \in I_1 \rightarrow p=0 \ mod \ I_1$ + +$I_1 : I(p) \rightarrow (I_1 \bigcap I(p)) / p \ elementwise$ + +\noindent +On top of these the Ideals package implements the following +operations: + + +$I(u_1,u_2...)+I(v_1,v_2...) \rightarrow GB(I(u_1,u_2...,v_1,v_2...))$ + + +$I(u_1,u_2...)*I(v_1,v_2...)\rightarrow + GB(I(u_1*v_1,u_1*v2,...,u_2*v_1,u_2*v_2...))$ + + +$I_1 \bigcap I_2 \rightarrow + Q[x,...] \bigcap GB_{lex}(t*I_1 + (1-t)*I_2,\{t,x,..\}) $ + + +$I_1 : I(p_1,p_2,...) \rightarrow I_1 : I(p_1) \bigcap I_1 : I(p_2) +\bigcap ...$ + +$I_1 = I_2 \rightarrow GB(I_1)=GB(I_2)$ + +$I_1 \subseteq I_2 + \rightarrow \ u_i \in I_2 \ \forall \ u_i \in I_1=I(u_1,u_2...)$ + +\section{Examples} + +Please consult the file $ideals.tst$. +\end{document}