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