Annotation of OpenXM/src/kan96xx/Doc/ex.tex, Revision 1.3
1.3 ! takayama 1: % $OpenXM: OpenXM/src/kan96xx/Doc/ex.tex,v 1.2 2000/01/16 07:58:58 takayama Exp $
! 2: \documentclass{article}
1.1 maekawa 3: \title{\bf kan/examples}
4: \author{Nobuki Takayama}
5: \date{January 7,1995 : Revised, August 15, 1996; \\ Revised December 17, 1998.}
6:
7: \def\kansm{ {\tt kan/sm1}\ }
8: \def\pd#1{ \partial_{#1} }
9: \newtheorem{example}{Example}
10: \newtheorem{grammer}{Grammer}
11:
12: \begin{document}
13: \maketitle
14: \tableofcontents
15:
16: \section{About this document}
17:
18: The system \kansm is a Gr\"obner engine specialized especially
19: to the ring of differential operators with a subset of
20: Postscript language and an extension for object oriented programming.
21: It is designed to be a back-end engine for a
22: heterotic distributed computing system.
23: However, it is not difficult to control \kansm directly.
24: This document is a collection of programs for \kansm Version 2.xxxx.
25: Since the system is still evolving, there is no comprehensive manual
26: for the libraries of kan and the Postscript-like language {\tt sm1}.
27: However, all operators in \kansm are shortly explained in
28: {\tt onlinehelp.tex} in this directory and
29: it will be enough once one understands the fundamental design of the system.
30: This document provides introductory examples
31: and explains the fundamental design of the system.
32: If there are questions,
33: please send an E-mail to the author
34: ({\tt kan\at math.kobe-u.ac.jp}).
35:
36:
37: There are two design goals of \kansm.
38: \begin{enumerate}
39: \item Providing a backend engine in a distributed computing system for
40: computations in the ring of differential operators.
41: \item Providing a virtual machine based on stacks to teach intermediate
42: level computer science especially for mathematics students.
43: \end{enumerate}
44:
45: \section{Getting started}
46:
47: To start the system, type in {\tt sm1}.
48: To quit the system, type in {\tt quit}.
49: You can make a program run in \kansm by the operator
50: \begin{verbatim}
51: (filename) run ;
52: \end{verbatim}
53: or
54: \begin{verbatim}
55: $filename$ run ;
56: \end{verbatim}
57: The two expressions \verb! $xyz$ ! and {\tt (xyz)} have the same meaning;
58: they means the string {\tt xyz}.
59: The pair of brackets generates a string object.
60: The dollar sign is used for a compatibility to \kansm Version 1.x.
61:
62:
63: There are three groups of functions.
64: The first group is those of primitive operators.
65: They are functions written in C.
66: The second group is those of macro operators.
67: They are functions written in {\tt sm1} language and automatically
68: loaded when the system starts.
69: The third group is those of macro operators defined in the library files
70: in {\tt lib/} directory.
71: These operators provide a user friendly interfaces of computing
72: characteristic ideal, holonomic rank, $b$-function, annihilating
73: ideal, hypergeometric differential operators,
74: restrictions, de Rham cohomology groups.
75: You can get a list of primitive operators and macros
76: by {\tt ?} and {\tt ??} respectively.
77: To see the usage of a macro, type in
78: {\tt (macro name) usage ; }.
79: Note that you need a space before {\tt ;}.
80: All tokens should be separated by the space
81: or special characters \verb+ ( ) [ ] { } $ % +.
82: The help message usually provides examples.
83: For example, the line
84: {\tt (add) usage } present the example
85: \verb+ Example: 2 3 add :: ==> 5+
86: You may try the input line
87: {\tt 2 3 add ::}
88: and will get the output {\tt 5}.
89: All printable characters except the special characters
90: \verb+ ( ) [ ] { } $ % +
91: can be a part of a name
92: of a macro or primitive operator.
93: For example, {\tt ::} is a name of macro which
94: outputs the top of the stack and the prompt.
95:
96:
97: \kansm is a stack machine.
98: Any object that has been input is put on the top of the stack.
99: Any operator picks up objects from the stack, executes computations and
100: puts results on the stack.
101: For example, the primitive operator {\tt print} picks up one object
102: from the stack and print it to the screen.
103: If you type in
104: {\tt (Hello World) print},
105: then the string ``Hello World'' is put on the stack and the operator
106: {\tt print} picks up the string and print it.
107: The macro {\tt message} works like {\tt print} and outputs the newline.
108: The macro {\tt :: } is similar to {\tt message},
109: but it also outputs the newline and the prompt;
110: it picks up one object from the stack, print the object to the screen and
111: output the prompt {\tt sm1>}.
112: For example, when you type in
113: \begin{verbatim}
114: (Hello World) ::
115: \end{verbatim}
116: you get
117: \begin{verbatim}
118: Hello World
119: sm1>
120: \end{verbatim}
121: We introduce two more useful stack operators.
122: \begin{enumerate}
123: \item[] {\tt pop} \quad Remove the top element from the stack.
124: \item[] {\tt pstack} \quad Print the contents of the entire stack.
125: \end{enumerate}
126: You can use \kansm as a reverse Polish calculator; try the following lines.
127: \begin{verbatim}
128: 11 4 mul ::
129: 3 4 add /a set
130: 5 3 mul /b set
131: a b add ::
132: \end{verbatim}
133:
134: Mathematical expressions such as \verb! x^2-1 ! are not parsed by the
135: stackmachine.
136: The parsing is done by the primitive operator {\tt .} (dot) in the current
137: ring.
138: For example, type in the following line just after you started \kansm
139: \begin{verbatim}
140: ( (x+2)^10 ). ::
141: \end{verbatim}
142: then you will get the expansion of $ (x+2)^{10} $.
143: \verb! ( (x+2)^10 ) ! is a string and is pushed on the stack.
144: Next, the operator {\tt .} parses the expression and convert it
145: to an internal expression of the polynomial.
146: Note that the given string is parsed in the current ring.
147: In order to see the current ring, use the operator
148: {\tt show\_ring}.
149: Note that the polynomials in {\tt sm1} means
150: polynomials with the coefficients in a given ring such as {\bf Z}.
151: So,
152: \verb! (x/3+2). !
153: is {\em not accepted}.
154:
155: A variable is defined by placing the variable's name, value and
156: {\tt def} operator on the stack of \kansm as in the following
157: line:
158: \begin{verbatim}
159: /abc 23 def
160: \end{verbatim}
161: The macro {\tt set} is an alternative way to define a variable and set a value.
162: \begin{verbatim}
163: 23 /abc set
164: \end{verbatim}
165: means to set the value {\tt 23} to the variable {\tt abc}.
166:
167: In order to output an expression to a file,
168: the macro {\tt output} is convinient.
169: For example, the lines
170: \begin{verbatim}
171: ( (x+2)^10 ). /a set
172: a output
173: \end{verbatim}
174: output the expansion of $(x+2)^{10}$ to the file
175: {\tt sm1out.txt}.
176:
177: If you need to run a start-up script,
178: modify the shell script {\tt Doc/startsm1} and write what you need
179: in the file {\tt Doc/Sm1rc}.
180:
181: \smallbreak
182: The system \kansm is not designed for a heavy interactive use.
183: So, unless you are a stackmachine fan,
184: it is recommended to write your input in a file, for example,
185: in {\tt abc.sm1}, and execute your input as
186: {\footnotesize \begin{verbatim}
187: sm1 -q <abc.sm1
188: \end{verbatim}}
189: \noindent Here is an example of an input file {\tt abc.sm1}:
190: {\footnotesize \begin{verbatim}
191: (cohom.sm1) run
192: [(y^2-x^3-2) (x,y)] deRham ::
193: \end{verbatim}}
194: \noindent The option {\tt -q} is for not outputting starting messages.
195:
196:
197: \medbreak
198:
199: We close this section with introducing some useful references.
200:
201: For the reader who are interested in writing a script for {\tt kan/sm1},
202: it is strongly recommended to go through Chapters 2 and 4
203: (stack and arithmetic, procedures and variables) of the so called
204: ``postscript blue book'' \cite{Postscript}.
205: The control structure of {\tt Kan/sm1} is based on a subset of
206: Postscript.
207:
208: The book \cite{Oaku} is a nice introduction to compute $D$-module invariants
209: with Gr\"obner bases.
210: The book \cite{SST} is the latest book on this subject.
211: This book explains the notion of homogenized Weyl algebra,
212: which is the main ring for computations in \kansm.
213: and algorithms for $D$-modules.
214: As to an introduction to mathematical aspect of $D$-modules,
215: Chapter 5 of \cite{Hotta} is recommended.
216:
217: The latest information on {\tt kan/sm1} and related papers are put on the
218: http address \cite{www}.
219:
220: \section{Package files in the Doc/ (lib/) directory}
221:
222: A set of user friendly packages are provided
223: for people who are interested in $D$-modules
224: ($D$ is the ring of differential operators), but
225: are not interested in the aspect of {\tt sm1}
226: as a part of distributed computing system.
227: Here is a list of packages.
228: \begin{enumerate}
229: \item {\tt bfunction.sm1} : Computing b-functions.
230: This script is written by T.Oaku.
231: \item{\tt factor-a.sm1} : A sample interface with {\tt risa/asir} \cite{asir}
232: to factor given polynomials.
233: \item{\tt hol.sm1} : A basic package for holonomic systems (Gr\"obner basis and
234: initial ideals, holonomic rank, characteristic variety, annihilating ideal
235: of $f^s$).
236: \item{\tt gkz.sm1} : Generate GKZ system for a given $A$ and $b$.
237: \item{\tt appell.sm1} : Generate Appell hypergeometric differential equations.
238: \item{\tt cohom.sm1} : An experimental package for computing restrictions
239: and de Rham cohomology groups mainly written by T.Oaku.
240: \item {\tt kanlib1.c} : An example to explain an interface between kan and
241: C-program. Type in ``make kanlib1'' to compile it.
242: \item{\tt ox.sm1} : A package for communication based on the open XM protocol.
243: The open sm1 server {\tt ox\_sm1} can be obtainable from the same ftp cite
244: of {\tt kan/sm1}.
245: See {\tt http://www.math.kobe-u.ac.jp/openxxx} for the protocol design.
246: \item{\tt oxasir.sm1} : A package to use open asir server based on the open
247: XM protocol.
248: Open asir server {\tt ox\_asir} will be distributed from \cite{asir}.
249: The package {\tt cohom.sm1} ({\tt deRham}) and {\tt annfs} need this package
250: to analyze the roots of $b$-functions.
251: The built-in function to analyze the roots is slow. The open asir server
252: and {\tt oxasir.sm1} should be used for efficient analysis of the roots
253: of $b$-functions.
254: See the usage of {\tt oxasir} for the latest information.
255: \item{\tt intw.sm1} : Compute $0$-th integration of a given $D$-module
256: by using a generic weight vector.
257: \end{enumerate}
258:
259: See the section three of {\tt onlinehelp.tex} for more informations.
260:
261: \subsection{Examples: {\tt gb, rrank, gkz, bfunction, deRham}}
262:
263: Execute {\tt Loadall} to load packages before executing examples.
264: {\tt Dx} means $\partial_x$.
265:
266: \begin{example} \rm
267: Compute a Gr\"obner basis and the initial ideal
268: with respect to the weight vector
269: $(0,0,1,1)$ of the $D$-ideal
270: $$D \cdot \{ (x \partial_x)^2 + (y \partial_y)^2 -1,
271: x y \partial_x \partial_y-1 \}.$$
272: See \cite{SST} on the notion of
273: Gr\"obner basis and the initial ideal with respect
274: to a weight vector.
275: \begin{verbatim}
276: [ [( (x Dx)^2 + (y Dy)^2 -1) ( x y Dx Dy -1)] (x,y)
277: [ [ (Dx) 1 (Dy) 1] ] ] gb pmat ;
278: \end{verbatim}
279: {\footnotesize
280: Output:
281: \begin{verbatim}
282: [
283: [ x^2*Dx^2+y^2*Dy^2+x*Dx+y*Dy-1 , x*y*Dx*Dy-1 , y^3*Dy^3+3*y^2*Dy^2+x*Dx ]
284: [ x^2*Dx^2+y^2*Dy^2 , x*y*Dx*Dy , y^3*Dy^3 ]
285: ]
286: \end{verbatim}
287: }
288: The first line is the Gr\"obner basis and the second line is a set of
289: generators of the initial ideal with respect to the weight
290: vector $(0,0,1,1)$.
291: In order to get syzygies, use {\tt syz}.
292: \end{example}
293:
294: \begin{example} \rm
295: Generate the GKZ system for $A=\pmatrix{1 & 1 & 1 & 1 \cr
296: 0 & 1 & 3 & 4 \cr}$
297: and $\beta = (1,2)$.
298: Here, the GKZ system is a holonomic system of differential equations
299: introduced by Gel'fand, Kapranov and Zelevinsky.
300: The system is also called ${\cal A}$-hypergeometric system.
301: \begin{verbatim}
302: [ [[1 1 1 1] [0 1 3 4]] [1 2]] gkz ::
303: \end{verbatim}
304: {\footnotesize
305: Output:
306: \begin{verbatim}
307: [ x1*Dx1+x2*Dx2+x3*Dx3+x4*Dx4-1 , x2*Dx2+3*x3*Dx3+4*x4*Dx4-2 ,
308: Dx2*Dx3-Dx1*Dx4 , -Dx1*Dx3^2+Dx2^2*Dx4 , Dx2^3-Dx1^2*Dx3 ,
309: -Dx3^3+Dx2*Dx4^2 ]
310: \end{verbatim}
311: }
312: \end{example}
313:
314: \begin{example} \rm
315: Evaluate the holonomic rank of
316: the GKZ systems for $A=\pmatrix{1 & 1 & 1 & 1 \cr
317: 0 & 1 & 3 & 4 \cr}$
318: and $\beta = (1,2)$ and $\beta=(0,0)$.
319: Show also the time of the execution.
320: \begin{verbatim}
321: { [ [[1 1 1 1] [0 1 3 4]] [1 2]] gkz rrank ::} timer
322: { [ [[1 1 1 1] [0 1 3 4]] [0 0]] gkz rrank ::} timer
323: \end{verbatim}
324: {\footnotesize
325: Output:
326: \begin{verbatim}
327: 5
328: User time: 1.000000 seconds, System time: 0.010000 seconds, Real time: 1 s
329: 4
330: User time: 1.320000 seconds, System time: 0.000000 seconds, Real time: 1 s
331: \end{verbatim}
332: }
333: \end{example}
334:
335: \begin{example} \rm
336: Compute the $b$-function of $f=x^3-y^2 z^2$
337: and the annihilating ideal of $f^{r_0}$ where
338: $r_0$ is the minimal integral root of the $b$-function.
339: \begin{verbatim}
340: (oxasir.sm1) run
341: [(x^3 - y^2 z^2) (x,y,z)] annfs /ff set
342: ff message
343: ff 1 get 1 get fctr ::
344: \end{verbatim}
345: {\footnotesize
346: Output:
347: \begin{verbatim}
348: [ [ -y*Dy+z*Dz , 2*x*Dx+3*y*Dy+6 , -2*y*z^2*Dx-3*x^2*Dy ,
349: -2*y^2*z*Dx-3*x^2*Dz , -2*z^3*Dx*Dz-3*x^2*Dy^2-2*z^2*Dx ] ,
350: [-1,-139968*s^7-1119744*s^6-3802464*s^5-7107264*s^4-7898796*s^3-5220720*s^2-1900500*s-294000]]
351: [[ -12 , 1 ] , [ s+1 , 1 ], [3*s+5 , 1], [ 3*s+4, 1], [6*s+7, 2], [6*s+5, 2]]
352: \end{verbatim}
353: }
354: The first two rows of the output give generators of the annihilating
355: ideal of
356: $(x^3-y^2 z^2)^{-1}$.
357: The $b$-function is
358: $(s+1)(3s+5)(3s+4)(6s+7)^2(6s+5)^2$
359: and $-1$ is the minimal integral root.
360: \end{example}
361:
362:
363: \begin{example} \rm
364: Compute the de Rham cohomology group
365: of $X={\bf C}^2 \setminus V(x^3-y^2)$.
366: \begin{verbatim}
367: (cohom.sm1) run
368: [(x^3-y^2) (x,y)] deRham ;
369: \end{verbatim}
370: {\footnotesize
371: Output:
372: \begin{verbatim}
373: 0-th cohomology: [ 0 , [ ] ]
374: -1-th cohomology: [ 1 , [ ] ]
375: -2-th cohomology: [ 1 , [ ] ]
376: [1 , 1 , 0 ]
377: \end{verbatim}
378: }
379: This means that $H^2(X,{\bf C}) = 0$,
380: $H^1(X,{\bf C}) = {\bf C}^1$,
381: $H^0(X,{\bf C}) = {\bf C}^1$.
382: \end{example}
383:
384: \begin{example} \rm
385: Compute the integral of
386: $ I=D\cdot \{\partial_t -(3 t^2-x) ,\, \partial_x+t \}$,
387: which annihilates the function $e^{t^3-x t}$,
388: with respect to $t$.
389: \begin{verbatim}
390: (cohom.sm1) run
391: [ [(Dt - (3 t^2-x)) (Dx + t)] [(t)]
392: [ [(t) (x)] [ ]] 0] integration
393: \end{verbatim}
394: {\footnotesize Output:
395: \begin{verbatim}
396: [ [ 1 , [ 3*Dx^2-x ] ] ]
397: \end{verbatim} }
398:
399: \end{example}
400:
401:
402:
403: \section{Data types}
404:
405: Each object in {\tt sm1} has a data type.
406: Here is a list of main primitive data types,
407: which are common to other languages except the type polynomial
408: and the type ring.
409: \begin{enumerate}
410: \item[] {\bf null}
411: \item[] {\bf integer}(machine integer), \quad
412: 32 bit integer. \quad Example: {\tt 152}
413: \item[] {\bf literal}, \quad
414: literal. \quad Example: {\tt /abc}
415: \item[] {\bf string}, \quad
416: string. \quad Example: {\tt (Hello)}
417: \item[] {\bf executableArray}, \quad
418: program data. \quad Example: {\tt \{ add\ 2 \ mul \} }
419: \item[] {\bf array}, \quad
420: array, \quad Example: {\tt [(abc) \ 5 ]}
421: \item[] {\bf polynomial}, \quad
422: polynomial, \quad Example: \verb! (x^2-1). !
423: \item[] {\bf ring}, \quad
424: ring definition.
425: \item[] {\bf number}(universalNumber), \quad
426: Big num. \quad Example: \verb! (123).. 456 power !
427: \item[] {\bf class}, \quad
428: Class.
429: \end{enumerate}
430:
431: \subsection{Array}
432: Array is a collection of one dimensional objects surrounded by square
433: brackets and
434: indexed by integers (machine integers) $0, 1, 2, \ldots$.
435: Elements of any array may be arrays again, so we can express
436: list structures by using arrays.
437: An array is constructed when the {\tt sm1} encounters the right square
438: bracket.
439: Note that square brackets are also operators.
440: Thus, the line
441: \begin{verbatim}
442: [(Hello) 2 50 add]
443: \end{verbatim}
444: sets up an array
445: \begin{verbatim}
446: [(Hello) 52]
447: \end{verbatim}
448: where the $0$-th element of the array is the string
449: {\tt (Hello)}
450: and the $1$-th element is the integer {\tt 52}.
451: The {\tt put} and {\tt get} operator store and fetch an element of
452: an array.
453: The {\tt get} operator takes an array and an index from the stack
454: and returned the object indexed by the second argument.
455: The line
456: \begin{verbatim}
457: [(sm1) 12 [(is) (fun)] 15] 2 get
458: \end{verbatim}
459: would return the array
460: {\tt [(is) (fun)]} on the stack.
461: The {\tt put} operator takes an array, an index {\tt i}, an object
462: from the stack
463: and store the object at the $i$-th position of the array.
464: That is,
465: \begin{verbatim}
466: /a [(sm1) (is) (fun)] def
467: a 2 (a stackmachine) put
468: \end{verbatim}
469: would rewrite the contents of the variable {\tt a} as
470: \begin{verbatim}
471: [(sm1) (is) (a stackmachine)]
472: \end{verbatim}
473:
474: \subsection{Ring}
475:
476: The ring object is generated by the operator {\tt define\_ring}.
477: This operator has a side effect;
478: it also changes the {\it current ring}.
479: The line
480: \begin{verbatim}
481: [(x,y) ring_of_differential_operators 0] define_ring /R set
482: \end{verbatim}
483: would create the ring of differential operators
484: $$ {\bf Z} \langle x, y, \partial_x, \partial_y \rangle, $$
485: store it in the variable {\tt R} and changes the current ring
486: to this Weyl algebra.
487: $\partial_x$ is denoted by ${\tt Dx}$ on {\tt sm1}.
488: The suffix ${\tt D}$ can be changed;
489: for example, if you want to use {\tt dx} instead of {\tt Dx},
490: execute the command
491: {\tt /\at \at \at}\verb+.Dsymbol (d) def +
492: The current ring can be obtained by
493: {\tt [(CurrentRingp)] system\_variable }.
494: The current ring is the ring of polynomials of
495: two variables $x, h$ when the system starts.
496:
497: All polynomial except $0$ belongs to a ring.
498: For a non-zero polynomial {\tt f},
499: the line
500: \begin{verbatim}
501: f (ring) dc /rr set
502: \end{verbatim}
503: put the associated ring object of {\tt f} to the variable {\tt rr}.
504: As we have seen before,
505: a given string is parsed as a polynomial in the current ring by the operator
506: ``{\tt .}''.
507: To parse in a given ring,
1.3 ! takayama 508: the operator ``{\tt \_\_}'' is used.
1.1 maekawa 509: That is,
510: \begin{verbatim}
511: [(x,y) ring_of_differential_operators 0] define_ring /R set
1.3 ! takayama 512: (x^2-y) R __ /f set
1.1 maekawa 513: \end{verbatim}
514: means to parse the string \verb! x^2-y ! in the ring {\tt R}
515: and put the polynomial $x^2-y$ in the variable {\tt f}.
516: Arithmetic operators for two polynomials can be performed only
517: when the two polynomials belong to a same ring.
518: If you want to map a polynomial to a different ring,
519: the easiest way is to translate the polynomial into a string and
520: parse it in the ring.
521: That is,
522: \begin{verbatim}
523: [(x,y) ring_of_polynomials 0] define_ring /R1 set
524: (x-y). /f set
525: [(x,y,z) ring_of_differential_operators 0] define_ring /R2 set
526: (y+Dz). /g set
527: f toString . /f set
528: f g add ::
529: \end{verbatim}
530: would output
531: $ (x-y) + (y+Dz) = Dz$.
532:
533: It is convinient to have a class of numbers that is contained in
534: any ring.
535: The datatype number (universalNumber) is the class of bignum, which is
536: allowed to be added and multiplied to any polynomials with characteristic 0.
537:
538: \subsection{Tag}
539: Each object of {\tt kan/sm1} has the tag expressed by an integer.
540: The tag expresses the class to which the object belongs.
541: You can see the tag of a given object by the operator {\tt tag}.
542: For example, if you type in
543: \begin{verbatim}
544: 10 tag ::
545: \end{verbatim}
546: then you get the number $1$.
547: If you type in
548: \begin{verbatim}
549: [ 1 2] tag ::
550: \end{verbatim}
551: then you get the number $6$.
552: The number $1$ is the tag of the integer objects and
553: the number $6$ is the tag of the array objects.
554: These tag numbers are stored in the variables
555: {\tt IntegerP} and {\tt ArrayP}.
556: In order to translate one object to that in a different class,
557: there is the operator {\tt data\_conversion} or {\tt dc}.
558: For example,
559: \begin{verbatim}
560: (10). (integer) dc ::
561: \end{verbatim}
562: translates the polynomial $10$ in the current ring into the integer $10$
563: and
564: \begin{verbatim}
565: (10). (string) dc ::
566: \end{verbatim}
567: translates the polynomial $10$ into the string 10.
568:
569: \section{Gr\"obner basis and Syzygy computation in \kansm}
570: \subsection{Computing Gr\"obner or standard basis in the ring of the polynomials}
571:
572: \begin{example}
573: Obtain the Gr\"obner basis of the ideal generated by
574: the polynomials $x^2+y^2-4$ and $xy-1$ in terms of the graded reverse
575: lexicographic order :
576: $$ 1 < x < y < x^2 < xy < y^2 < \cdots. $$
577: \end{example}
578:
579: All inputs must be homogenized to get Gr\"obner basis
580: by the command {\tt groebner}.
581: Usually, the variable $h$ is used for the homogenization.
582: In this example,
583: Gr\"obner bases in
584: ${\bf Q}[x,y,h]$ are computed,
585: but rational coefficients in the input is not allowed.
586: All coefficients must be integers.
587:
588: The operator {\tt groebner\_sugar} is for non-homogenized
589: computation of Gr\"obner basis.
590:
591: The following code is a convinient template to obtain
592: Gr\"obner bases.
593:
594: @gbrev.sm1
595:
596: The letters after the symbol {\tt \%} are ignored by \kansm ;
597: comments begin with the symbol {\tt \%}.
598: If one needs to compute Gr\"obner basis of a given set of polynomials,
599: one may only change the lines marked by the comment
600: {\tt \% Change here}.
601:
602: \begin{grammer}
603: Any string of alphabets can be used as a name of a variable except
604: {\tt h}, {\tt E}, {\tt H} and {\tt e\_}.
605: For $q$-difference operators, {\tt q} is also reserved.
606: Upper and lower case letters are distinct.
607: \end{grammer}
608:
609: \bigbreak
610:
611: \begin{example}
612: Obtain the Gr\"obner basis of the ideal generated by
613: the polynomials $x^2+y^2-4$ and $xy-1$ in terms of the
614: lexicographic order :
615: $$ 1 < x < x^2 < x^3 < \cdots < y < yx < yx^2 < \cdots. $$
616: \end{example}
617:
618:
619: @gblex.sm1
620: In this example, the order is specified by the weight vector.
621: If the line \\
622: \verb+ [vec1 vec2 ...] weight_vector +
623: is given in the definition of the ring,
624: monomials are compared by the weight vector {\tt vec1}.
625: If two monomials have the same weight, then they are
626: compared by the weight vector {\tt vec2}.
627: This procedure will be repeated until all weight vectors are used.
628:
629: The weigth vector is expressed in the form
630: {\tt [v1 \ w1 \ v2 \ w2 \ ... vp \ wp ]},
631: which
632: means that the variable {\tt v1} has the weight {\tt w1},
633: the variable {\tt v2} has the weight {\tt w2}, $\ldots$.
634: For example,
635: when the ring is defined by
636: \begin{verbatim}
637: [(x,y,z) ring_of_polynomials
638: [[(x) 1 (y) 3] [(z) -5]] weight_vector 0]
639: define_ring
640: \end{verbatim}
641: two monomials
642: $x^a y^b z^c \succ x^A y^B z^C$
643: if and only if
644: $ a+3b > A+3B$ or
645: ($ a+3b = A+3B$ and $ -5 c > -5 C$)
646: or
647: ($ a+3b = A+3B$ and $ -5 c = -5 C$ and $(a,b,c) \succ_{grlex} (A,B,C)$)
648: where $\succ_{grlex}$ denotes the graded reverse lexicographic order.
649: \bigbreak
650:
651: The Buchberger's criterion 1 is turned off by default,
652: because it does not work in case of the ring of differential operators.
653: To turn it on,
654: input \\
655: \verb! [(UseCriterion1) 1] system_variable !
656:
657: The operator {\tt groebner} outputs the status of degree by degree computation
658: of Gr\"obner basis.
659: To turn off this message, input
660: \verb! [(KanGBmessage) 0] system_variable !
661:
662:
663: \begin{example}
664: Obtain the Gr\"obner basis of the ideal generated by
665: the polynomials
666: $$x^2+y^2+z^2-1,xy+yz+zx-1, xyz-1 $$
667: in terms of the
668: elimination order
669: $ x,y > z. $
670: \end{example}
671:
672: @gbelim.sm1
673: \bigbreak
674:
675:
676: \subsection{Computing Gr\"obner basis in the ring of differential operators}
677:
678: \begin{example}
679: Obtain the Gr\"obner basis of the ideal in the Weyl algebra
680: $$ {\bf Q } \langle x,y,\pd{x},\pd{y} \rangle, \quad \hbox{ where }\
681: \pd{x}=\frac{\partial}{\partial x},
682: \pd{y}=\frac{\partial}{\partial y}
683: $$
684: generated by
685: the differential operators
686: $$ x \pd{x} + y \pd{y},
687: \pd{x}^2 + \pd{y}^2
688: $$
689: in terms of the elimination order
690: $ \pd{x}, \pd{y} > x,y $
691: by using the homogenized Weyl algebra.
692: \end{example}
693:
694: @gbdiff.sm1
695: \bigbreak
696:
697: \subsection{Computing Gr\"obner basis in $R^n$}
698:
699: \begin{example}
700: Let $S$ be the ring of polynomials
701: $Q [x,y]$.
702: Obtain the Gr\"obner basis of the $S$-submodule of $S^3$
703: generated by the vectors
704: $$ (x-1,y-1,z-1), (xy-1,yz-2,zx-3). $$
705: \end{example}
706:
707: @gbvec.sm1
708: \bigbreak
709:
710: \subsection{Computing syzygies}
711:
712: Let $R$ be a ring and $f_1, \ldots, f_m$ be elements of $R$.
713: The left $R$-module
714: $$ \{ (s_1, \ldots, s_m \in R^m \,|\, \sum_{i=1}^m s_i f_i = 0 \} $$
715: is called the syzygy among $f_1, \ldots, f_m$.
716: The following script computes the generators of the syzygy
717: among
718: $$ x \pd{x} + y \pd{y},
719: \pd{x}^2+\pd{y}^2
720: $$
721: in the homogenized Weyl algebra.
722:
723: @syz.sm1
724: The 0-th element of {\tt ans} is the Gr\"obner basis.
725: The 1st element of {\tt ans} is the transformation matrix from the input
726: to the Gr\"obner basis.
727: The 2nd element of {\tt ans} is a set of generators of the syzygies
728: of the input.
729:
730: \bigbreak
731:
732:
733: \section{Control Structures and programming}
734:
735: \subsection{if}
736: The conditional operator {\tt if} requires three objects on the stack:
737: an integer value and two executable arrays, which are program data.
738: The first executable array will be executed if the integer value is not 0.
739: The second executable array will be executed if the integer value is 0.
740: For example, the program line
741: \begin{verbatim}
742: 1 { op1 } {op2} ifelse
743: \end{verbatim}
744: executes {\tt \{ op1 \}} and the program line
745: \begin{verbatim}
746: 0 { op1 } {op2} ifelse
747: \end{verbatim}
748: executes {\tt \{ op2 \}}.
749:
750: Here is a list of comparison operators.
751: \begin{enumerate}
752: \item[] {\tt eq} \quad $=$ \quad Example: {\tt [1 2] [1 3] eq }
753: \item[] {\tt gt} \quad $>$ \quad Example: {\tt 3 2 gt}
754: \item[] {\tt lt} \quad $<$ \quad Example: {\tt 3 2 lt}
755: \item[] {\tt not} \quad Example: {\tt 3 2 eq not}
756: \item[] {\tt and} \quad Example: {\tt 3 2 eq 5 6 lt and }
757: \item[] {\tt or} \quad Example: {\tt 3 2 eq 5 6 lt or }
758: \end{enumerate}
759:
760:
761: \subsection{for}
762: The {\tt for} operator implements a counting loop.
763: This operator takes three integers and one executable array:
764: \begin{verbatim}
765: i0 d i1 { ops } for
766: \end{verbatim}
767: {\tt i0} is the loop counter's starting value,
768: {\tt d} is the increment amount,
769: {\tt i1} is the final value.
770: The {\tt for} operator put the value of the counter on the stack before
771: each execution of {\tt ops}.
772: For example, the program line
773: \begin{verbatim}
774: 1 1 5 { /i set i message } for
775: \end{verbatim}
776: outputs
777: \begin{verbatim}
778: 1 2 3 4 5
779: \end{verbatim}
780:
781:
782:
783: \subsection{{\tt map} function}
784:
785: {\tt map} function is used to apply an operator to each element
786: of a given array.
787: For example, the following line is used to translate each polynomial
788: of the given array {\tt aa} into the corresponding string
789: \begin{verbatim}
790: /aa [( (x-1)^2 ). (2^10).] def
791: aa { (string) dc } map /ff set ;
792: ff ::
793: \end{verbatim}
794: It becomes easier to writing script for {\tt kan/sm1} by using the {\tt map}
795: function.
796:
797: \subsection{Function definition}
798:
799: Programs are stored in executable arrays and
800: the curly brackets generate executable arrays.
801: For example, if you input the line
802: \begin{verbatim}
803: { add 2 mul }
804: \end{verbatim}
805: then the executable array object which represents the program
806: ``take two elements from the stack, add them, and multiply two
807: and put the result on the stack''
808: will be store on the top of the stack.
809: You can bind the program to a name.
810: That is,
811: \begin{verbatim}
812: /abc { add 2 mul } def
813: \end{verbatim}
814: binds the executable array to the variable {\tt abc}.
815: The input \verb+ 2 4 abc :: + outputs {\tt 12}.
816: When {\tt sm1} encounters the name {\tt abc},
817: it looks up the user dictionary and finds that
818: the value of {\tt abc} is the executable array
819: \verb+ { add 2 mul } +.
820: The executable array is loaded to the stack machine and
821: executed.
822:
823: Funtions can be defined by using executable arrays.
824: Here is a complete example of a function definition in {\tt sm1}
825: following standard conventions.
826: \begin{verbatim}
827: /foo {
828: /arg1 set
829: [/n /i /ans] pushVariables
830: [
831: /n arg1 def
832: /ans 0 def
833: 1 1 n {
834: /i set
835: /ans ans i add def
836: } for
837: ans /arg1 set
838: ] pop
839: popVariables
840: arg1
841: } def
842: \end{verbatim}
843: The function returns the sum $1+2+\cdots+ n$.
844: For example,
845: {\tt 100 foo ::} outputs $5050$.
846: The arguments of the function should firstly be stored in the variables
847: {\tt arg1}, {\tt arg2}, $\ldots$.
848: It is a convension in {\tt sm1} programming.
849: The local variables are declared in the line
850: \begin{verbatim}
851: [/n /i /ans] pushVariables
852: \end{verbatim}
853: The macro {\tt pushVariables} stores the previous values of
854: {\tt n}, {\tt i}, {\tt ans} on the stack and
855: the macro {\tt popVariables} restores the previous values.
856: So, you can use {\tt n}, {\tt i}, {\tt ans}
857: as a local variable of this function.
858: The function body should be enclosed as
859: \begin{verbatim}
860: [
861:
862: ] pop
863: \end{verbatim}
864: It is also a convension in {\tt sm1} programming
865: to avoid unmatched use of
866: {\tt pushVariables} and {\tt popVariables}.
867:
868:
869: \begin{example} \rm
870: {\tt cv0.sm1} is a script to compute characteristic variety
871: for $D$-submodules in $D^n$.
872:
873: {\tt cv2.sm1} is a script to compute the multiplicites of
874: $D$-modules.
875: \end{example}
876:
877:
878: \section{Dictionaries and contexts}
879:
880: The {\tt def} or {\tt set} operators associate a key with a value
881: and that key-value pair is stored in the current dictionary.
882: They key may starts with any printable character except
883: \verb+ ( ) [ ] { } $ % +
884: and numbers and be followed by any printable characters
885: except the special characters.
886: For example,
887: \begin{verbatim}
888: foo test Test! foo?59
889: \end{verbatim}
890: are accepted as names for keys.
891:
892: A key-value pair is stored in the current dictionary
893: when you use the operator {\tt def}
894: or the operator {\tt set}.
895: For example,
896: when you input the line
897: \begin{verbatim}
898: /foo 15 def
899: \end{verbatim}
900: then the key-value pair
901: ({\tt foo}, 15) is stored in the current dictionary.
902: We can generate several dictionaries in {\tt sm1}.
903: Each dictionary must have its parent dictionary.
904: When you input a token (key) that is not a number or a string or a literal,
905: {\tt sm1} looks up the current dictionary to find the value of the key.
906: If the value is an executable array, then it will be executed.
907: If the value is not an executable array, then the value is put on the stack
908: as an object.
909: If the looking-up fails,
910: then it tries to find the value in the parent dictionary.
911: If it fails again, then it tries to find the value in the grandparent
912: dictionary and so on.
913: This mechanism enables us to write an object oriented system.
914: When the system starts, there are two dictionaries:
915: primitive dictionary and the standard user dictionary.
916: For example, the input {\tt ?} makes {\tt sm1} to look up
917: the standard user dictionary and {\tt sm1} finds the value of {\tt ?},
918: which is an executable array that displays all keys in the primitive
919: dictionary.
920:
921: A new dictionary can be created by the operator {\tt newcontext}.
922: Here is an example of creating a new dictionary.
923: \begin{verbatim}
924: /abc { (Bye) message } def
925: /aaa 20 def
926: abc aaa ::
927: \end{verbatim}
928: The key-value pairs ({\tt abc}, \verb+ { (Bye) message } +
929: and
930: ({\tt aaa}, \verb+ 20 +)
931: are stored in the current dictionary ({\tt StandardContextp}).
932: Here is the output from the system.
933: {\footnotesize \begin{verbatim}
934: Bye
935: 20
936: \end{verbatim} }
937: \begin{verbatim}
938: (mycontext) StandardContextp newcontext /nc set ;
939: nc setcontext ;
940: \end{verbatim}
941: Create a new dictionary and change the current dictionary
942: by {\tt setcontext}.
943: \begin{verbatim}
944: /abc { (Hello) message } def ;
945: abc aaa ::
946: \end{verbatim}
947: Store a new key-value pair in the new dictionary.
948: Here is the output of the system.
949: {\footnotesize \begin{verbatim}
950: Hello
951: 20
952: \end{verbatim} }
953: The key {\tt abc} was found in the current dictionary, so
954: the system outputs {\tt Hello}.
955: The key {\tt aaa} was not found in the current dictionary,
956: so the system looked for it in the parent dictionary and
957: outputs the value {\tt 20}.
958:
959:
960: It is sometimes preferable to protect the key-value pairs
961: from unexpected rewriting.
962: If you input the following lines, then all pairs in the current dictionary
963: except
964: {\tt arg1}, {\tt arg2}, {\tt arg3}, {\tt v1}, {\tt v2}, {\tt \at.usages}
965: will become readonly pairs.
966: {\footnotesize \begin{verbatim}
967: [(Strict2) 1] system_variable %% from var.sm1
968: [(chattrs) 2] extension
969: [(chattr) 0 /arg1] extension
970: [(chattr) 0 /arg2] extension
971: [(chattr) 0 /arg3] extension
972: [(chattr) 0 /v1] extension %% used in join.
973: [(chattr) 0 /v2] extension
974: \end{verbatim}
975: {\tt [(chattr) 0 /\at.usages] extension}}
976:
977: \section{Using {\tt sm1} to teach computer science for
978: students in mathematics}
979:
980: There are two design goals in {\tt sm1}.
981: One goal is to provide a backend engine for the ring of differential
982: operators in a
983: heterotic distributed computing system.
984: Another interesting design goal is to help to teach basics of
985: intermediate level computer science quickly
986: and invite students to mathematical programmers' world.
987: It is a fun to learn computer science with {\tt sm1}!
988: Here are some topics that I tried in class rooms.
989: These are intermediate level topics that should be learned after
990: students have learned elementary programming by languages like
991: Pascal, C, C++, Java, Basic, Mathematica, Maple, Macaulay 2, etc.
992:
993: \subsection{Recursive call and the stack}
994:
995: The notion of stack is one of the most important idea in computer science.
996: The notion of recursive call of functions is usually taught in the first
997: course of programming.
998: I think it is important to understand how the stack is used to emulate
999: recurisve calls.
1000: The idea is the use of the stack.
1001: Function arguments and local variables are stored in the stack.
1002: It enables the system to restore the values of the local variables and arguments
1003: after an execution of the function.
1004: However, it should be noted that, for each function call, the stack
1005: dynamically grows.
1006:
1007: As an example that I used in a class room,
1008: let us evaluate the $n$-th Fibonacci number
1009: defined by
1010: $$ f_n = f_{n-1}+f_{n-2}, \ f_1 = f_2 = 1 $$
1011: by using a recurisive call.
1012: \begin{verbatim}
1013: /fib {
1014: /arg1 set
1015: [/n /ans] pushVariables
1016: pstack
1017: /n arg1 def
1018: (n=) messagen n message
1019: (-------------------------------) message
1020: n 2 le {
1021: /ans 1 def
1022: }
1023: {
1024: n 1 sub fib n 2 sub fib add /ans set
1025: } ifelse
1026: /arg1 ans def
1027: popVariables
1028: arg1
1029: } def
1030: \end{verbatim}
1031: The program would return the $n$-th Fibonacci number.
1032: That is,
1033: \verb+ 4 fib :: +
1034: would return $f_4=3$.
1035: It also output the entire stack at each call,
1036: so you can observe how stack grows during the computation
1037: and how local variables {\tt n}, {\tt ans} are stored
1038: in the stack.
1039: You would also realize that this program is not efficient
1040: and exhausts huge memory space.
1041:
1042:
1043: \subsection{Implementing a Java-like language}
1044:
1045: One of the exciting topic in the course of computer science
1046: is mathematical theory of parsing.
1047: After learning the basics of the theory,
1048: it is a very good Exercise to design a small language and
1049: write a compiler or interpreter for the language.
1050: If you do not like to write a compiler for real CPU,
1051: the stackmachine {\tt sm1} will be a good target
1052: machine.
1053: For example, the language may accept the input
1054: \begin{verbatim}
1055: 12345678910111213*(256+2)
1056: \end{verbatim}
1057: and the interpreter or the compiler generate the following code for {\tt sm1}
1058: \begin{verbatim}
1059: (12345678910111213)..
1060: (256)..
1061: (2).. add
1062: mul message
1063: \end{verbatim}
1064: One can easily write an arbitrary precision calculator by using
1065: {\tt sm1}
1066: and also try algorithms in the number theory by one's own language.
1067:
1068: \noindent
1069: Exercise 1: parse a set of linear equations like
1070: {\tt 2x+3y+z = 2; y-z =4; }, output the equation in the matrix form
1071: and find solutions. \\
1072: Exercise 2:
1073: Modify the calculator {\tt hoc} so that it can use {\tt sm1} as the
1074: backend engine.
1075: The calculator {\tt hoc} is discussed in the book:
1076: Kerningham and Pike, Unix programming environment.
1077:
1078: The stackmachine {\tt sm1} provides a very strong virtual machine for
1079: object oriented system by the dictionary tree.
1080: We can easily implement a language, on which Java-like object
1081: oriented programming mechanism is installed,
1082: by using {\tt sm1}.
1083: Here is a sample program of {\tt kan/k0}, which is an object oriented
1084: language and works on {\tt sm1}.
1085: I taught a course on writing mathematical softwares
1086: in a graduate school with {\tt k0}.
1087: \begin{verbatim}
1088: class Complex extends Object {
1089: local re, /* real part */
1090: im; /* imaginary part*/
1091: def new2(a,b) {
1092: this = new(super.new0());
1093: re = a;
1094: im = b;
1095: return(this);
1096: }
1097: def real() { return(re); }
1098: def imaginary() { return(im); }
1099: def operator add(b) {
1100: return( new2(re+b.real(), im+b.imaginary()) );
1101: }
1102: def operator sub(b) {
1103: return( new2(re-b.real(), im-b.imaginary()) );
1104: }
1105: def operator mul(b) {
1106: return(new2( re*b.real()-im*b.imaginary(), re*b.imaginary()+im*b.real()));
1107: }
1108: def operator div(b) {
1109: local den,num1,num2;
1110: den = (b.real())^2 + (b.imaginary())^2 ;
1111: num1 = re*b.real() + im*b.imaginary();
1112: num2 = -re*b.imaginary()+im*b.real();
1113: return(new2(num1/den, num2/den));
1114: }
1115:
1116: def void show() {
1117: Print(re); Print(" +I["); Print(im); Print("]");
1118: }
1119: def void showln() {
1120: this.show(); Ln();
1121: }
1122: }
1123:
1124: \end{verbatim}
1125: \verb! a = Complex.new2(1,3); ! \\
1126: \verb! a: ! \\
1127: 1 +I[3] \\
1128: \verb! a*a: ! \\
1129: -8 +I[6] \\
1130:
1131:
1132:
1133: \subsection{Interactive distributed computing}
1134:
1135: The plugin modules file2, cmo, socket and the package file
1136: {\tt ox.sm1} provide functions for
1137: interactive distributed computing.
1138: To install these plugin modules, compile {\tt sm1} after modifying
1139: {\tt kan/Makefile}.
1140: See {\tt README} for details.
1141: These plugins are already installed in the binary distributions of {\tt sm1}.
1142: The sm1 server {\tt ox\_sm1} and {\tt ox} which are complient to the Open XM
1143: protocol
1144: (see \cite{openxxx})
1145: is distributed from the same ftp cite with {\tt sm1}.
1146: The sm1 server is also a stack machine.
1147: Here is an example input of server and client computation.
1148:
1149: \noindent Server:
1150: \begin{verbatim}
1151: ./ox -ox ox_sm1 -data 1300 -control 1200
1152: \end{verbatim}
1153:
1154: \noindent Client:
1155: \begin{verbatim}
1156: (ox.sm1) run
1157: [(localhost) 1300 1200] oxconnect /oxserver set
1158: /f (123).. def ;
1159: oxserver f oxsendcmo ; %% send the data f to the server
1160: oxserver f oxsendcmo ; %% send the data f to the server
1161: oxserver (power) oxexec ; %% execute f f power
1162: oxserver oxpopcmo :: %% get data from the server.
1163: \end{verbatim}
1164: The output is $123^{123}$ and equal to
1165: $114374367....9267$.
1166:
1167:
1168: \noindent
1169: Exercise:
1170: write a graphical interface for functions in packages of {\tt sm1} by Java
1171: and call sm1 server to execute them.
1172:
1173: \subsection{More exercises}
1174:
1175: \begin{enumerate}
1176: \item \kansm contains the GNU MP package for computations of bignumbers.
1177: You can call the functions in GNU MP by the operator {\tt mpzext}.
1178: Write a program to find integral solution $(x,y)$ of
1179: $ a x + b y = d$ for given integers $a, b, d$.
1180: \item Write a program for RSA encryption.
1181: \end{enumerate}
1182:
1183: \begin{thebibliography}{99}
1184: \bibitem{asir} Risa/Asir --- computer algebra system, \hfill\break
1185: {\tt ftp://endaevor.fujitsu.co.jp/pub/isis/asir}.
1186: \bibitem{Postscript} PostScript --- Language Turorial and Cookbook,
1187: (1985), Addison-Wesley
1188: \bibitem{Hotta} R.Hotta, Introduction to Algebra, Asakura-shoten, Tokyo
1189: (in Japanese).
1190: \bibitem{Oaku} T.Oaku,
1191: Gr\"obner basis and systems of differential equations,
1192: (1994) Seminor note series of Sophia University.
1193: (in Japanese).
1194: \bibitem{SST}
1195: M.Saito, B.Sturmfels, N.Takayama,
1196: Gr\"obner deformations of hypergeometric differential equations,
1197: to appear from Springer.
1198: \bibitem{www} {\tt http://www.math.kobe-u.ac.jp/KAN} and \hfill\break
1199: {\tt http://www.math.kobe-u.ac.jp/$\tilde{\ }$taka}
1200: \bibitem{openxxx}
1201: {\tt http://www.math.kobe-u.ac.jp/openxxx}
1202: \end{thebibliography}
1203:
1204: \end{document}
1205:
1206:
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to ex.tex CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [local] / OpenXM / src / kan96xx / Doc