#### ideals.tex3.9 KB Permalink History Raw

 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130 \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}