付録
**

Appendix
********

文法の詳細
=====

Details of syntax
=================

     <式>:
         (<式>)
         <式> <二項演算子> <式>
         + <式>
         - <式>
         <左辺値>
         <左辺値> <代入演算子> <式>
         <左辺値> ++
         <左辺値> --
         ++ <左辺値>
         -- <左辺値>
         ! <式>
         <式> ? <式> : <式>
         <函数> ( <式並び> )
         <函数> ( <式並び> | <オプション並び> )
         <文字列>
         <指数ベクトル>
         <アトム>
         <リスト>

     <expression>:
         (<expression>)
         <expression> <binary operator> <expression>
         + <expression>
         - <expression>
         <left value>
         <left value> <assignment operator> <expression>
         <left value> ++
         <left value> --
         ++ <left value>
         -- <left value>
         ! <expression>
         <expression> ? <expression> : <expression>
         <function> ( <expr list> )
         <function> ( <expr list> | <option list> )
         <string>
         <exponent vector>
         <atom>
         <list>

(see さまざまな式)

(see various expressions)

     <左辺値>:
         <変数> [[<式>]]*

     <left value>:
         <program variable> [[<expression>]]*

     <二項演算子>:
         + - * / % ^(冪)

     <binary operator>:
         + - * / % ^(exponentiation)
         == != < > <= >= && ||

         == != < > <= >= && ||

     <代入演算子>:

     <assignment operator>:

         = += -= *= /= %= ^=

     <式並び>:
         <空>
         <式> [, <式>]*

     <expr list>:
         <empty>
         <expression> [, <expression>]*

     <オプション>:
         alphabet で始まる文字列 = <式>

     <option>:
         Character sequence beginning with an alphabetical letter = <expression>

     <オプション並び>:
         <オプション>
         <オプション> [, <オプション>]*

     <option list>:
         <option>
         <option> [, <option>]*

     <リスト>:
         [ <式並び> ]

     <list>:
         [ <expr list> ]

     <変数>:
         大文字で始まる文字列 (X,Y,Japan など)

     <program variable>:
        Sequence of alphabetical letters or numeric digits or _
        that begins with a capital alphabetical letter
        (X,Y,Japan etc.)

(see 変数および不定元)

(see variables and indeterminates)

     <函数>:
        小文字で始まる文字列 (fctr,gcd など)

     <function>:
        Sequence of alphabetical letters or numeric digits or _
        that begins with a small alphabetical letter
        (fctr,gcd etc.)

     <アトム>:
        <不定元>
        <数>

     <atom>:
        <indeterminate>
        <number>

     <不定元>:
        小文字で始まる文字列 (a,bCD,c1_2 など)

     <indeterminate>:
        Sequence of alphabetical letters or numeric digits or _
        that begin with a small alphabetical letter
        (a,bCD,c1_2 etc.)

(see 変数および不定元)

(see variables and indeterminates)

     <数>:
        <有理数>
        <浮動小数>
        <代数的数>
        <複素数>

     <number>:
        <rational number>
        <floating point number>
        <algebraic number>
        <complex number>

(see 数の型)

(see Types of numbers)

     <有理数>:

     <rational number>:

        0, 1, -2, 3/4

     <浮動小数>:

     <floating point number>:

        0.0, 1.2e10

     <代数的数>:

     <algebraic number>:

        newalg(x^2+1), alg(0)^2+1

(see 代数的数に関する演算)

(see Algebraic numbers)

     <複素数>:

     <complex number>:

        1+@i, 2.3*@i

     <文字列>:
        " で囲まれた文字列

     <string>:
        character sequence enclosed by two "'s.

     <指数ベクトル>:
        << <式並び> >>

     <exponent vector>:
        << <expr list> >>

(see グレブナ基底の計算)

(see Groebner basis computation)

     <文>:
         <式> <終端>
         <複文>
         break <終端>
         continue <終端>
         return <終端>
         return <式> <終端>
         if ( <式並び> ) <文>
         if ( <式並び> ) <文> else <文>
         for ( <式並び> ; <式並び> ; <式並び> ) <文>
         do <文> while ( <式並び> ) <終端>
         while ( <式並び> ) <文>
         def <函数> ( <式並び> ) { <変数宣言> <文並び> }
         end(quit) <終端>

     <statement>:
         <expression> <terminator>
         <compound statement>
         break <terminator>
         continue <terminator>
         return <terminator>
         return <expression> <terminator>
         if ( <expr list> ) <statement>
         if ( <expr list> ) <statement> else <statement>
         for ( <expr list> ; <expr list> ; <expr list> ) <statement>
         do <statement> while ( <expr list> ) <terminator>
         while ( <expr list> ) <statement>
         def <function> ( <expr list> ) { <variable declaration> <stat list> }
         end(quit) <terminator>

(see 文)

(see statements)

     <終端>:

     <terminator>:

         ; $

     <変数宣言>:
         [extern <変数> [, <変数>]* <終端>]*

     <variable declaration>:
         [extern <program variable> [, <program variable>]* <terminator>]*

     <複文>:
         { <文並び> }

     <compound statement>:
         { <stat list> }

     <文並び>:
         [<文>]*

     <stat list>:
         [<statement>]*

添付のユーザ定義函数ファイル
==============

Files of user defined functions
===============================

標準ライブラリディレクトリ (デフォルトでは /usr/local/lib/asir) にはいくつかのユーザ定義函数ファイルがおかれている. これらのうちの主なものについて説明する.

There are several files of user defined functions under the standard library directory. (/usr/local/lib/asir by default.) Here, we explain some of them.

fff
     大標数素体および標数 2 の有限体上の一変数多項式因数分解 (see 有限体に関する演算)

     Univariate factorizer over large finite fields (see Finite fields)

gr
     グレブナ基底計算パッケージ.  (see グレブナ基底の計算)

     Groebner basis package.  (see Groebner basis computation)

sp
     代数的数の演算および因数分解, 最小分解体. (see 代数的数に関する演算)

     Operations over algebraic numbers and factorization, Splitting fields. (see Algebraic numbers)

alpi
bgk
cyclic
katsura
kimura
     グレブナ基底計算において, ベンチマークその他で用いられる例.

     Example polynomial sets for benchmarks of Groebner basis computation.

     (see katsura hkatsura cyclic hcyclic)

defs.h
     いくつかのマクロ定義. (see プリプロセッサ)

     Macro definitions. (see preprocessor)

fctrtest

     整数上の多項式の因数分解のテスト. REDUCE の factor.tst および重複度の大きいいくつかの例を含む. これは, load() すると直ちに計算が始まる. 入手した Asir が正しく動作しているかのテストにも使うことができる.

     Test program of factorization of integral polynomials. It includes  factor.tst of REDUCE and several examples for large multiplicity factors.  If this file is load()'ed, computation will begin immediately. You may use it as a first test whether Asir at you hand runs correctly.

fctrdata

     fctrtest で使われている例を含む, 因数分解テスト用の例. Alg[] に収められている例は, af() (see asq af) 用の例である.

     This contains example polynomials for factorization.  It includes polynomials used in fctrtest. Polynomials contained in vector Alg[] is for the algebraic factorization af() (see asq af).

          [45] load("sp")$
          [84] load("fctrdata")$
          [175] cputime(1)$
          0msec
          [176] Alg[5];
          x^9-15*x^6-87*x^3-125
          0msec
          [177] af(Alg[5],[newalg(Alg[5])]);
          [[1,1],[75*x^2+(10*#0^7-175*#0^4-470*#0)*x+(3*#0^8-45*#0^5-261*#0^2),1],
          [75*x^2+(-10*#0^7+175*#0^4+395*#0)*x+(3*#0^8-45*#0^5-261*#0^2),1],
          [25*x^2+(25*#0)*x+(#0^8-15*#0^5-87*#0^2),1],[x^2+(#0)*x+(#0^2),1],
          [x+(-#0),1]]
          3.600sec + gc : 1.040sec

ifplot

     描画 (see ifplot conplot plot plotover) のための例. IS[] には有名な曲線の例, 変数 H, D, C, S にはトランプのハート, ダイヤ, クラブ, スペード (らしき) 曲線の例が入っている.

     Examples for plotting (see ifplot conplot plot plotover). Vector IS[] contains several famous algebraic curves. Variables H, D, C, S contains something like the suits (Heart, Diamond, Club, and Spade) of cards.

num
     数に関する簡単な演算函数の例.

     Examples of simple operations on numbers.

mat
     行列に関する簡単な演算函数の例.

     Examples of simple operations on matrices.

ratint

     有理函数の不定積分. sp, gr が必要. ratint() という函数が定義されているが, その返す結果はやや複雑である. 例で説明する.

     Indefinite integration of rational functions.  For this, files sp and gr is necessary.  A function ratint() is defined.  Its returns a rather complex result.

          [0] load("gr")$
          [45] load("sp")$
          [84] load("ratint")$
          [102] ratint(x^6/(x^5+x+1),x);
          [1/2*x^2,
          [[(#2)*log(-140*x+(-2737*#2^2+552*#2-131)),161*t#2^3-23*t#2^2+15*t#2-1],
          [(#1)*log(-5*x+(-21*#1-4)),21*t#1^2+3*t#1+1]]]

     この例では, x^6/(x^5+x+1) の不定積分の計算を行っている. 結果は 2 つの要素からなるリストで, 第 1 要素は不定積分の有理部分, 第 2 要素は対数部分を表す. 対数部分は更にリストとなっていて, 各要素は, [root*log(poly),defpoly] という形をしている. これは, 不定積分においては, defpoly の全ての根 root に対して root*log(poly) を作りそれらを足し合わせるという意味である. ここで poly は root を含んでいて, root を入れ替える場合には poly に対しても同じ操作を行うものとする. この操作を, 結果の第 2 要素の各成分に対して行って, 全てを足し合わせたものが対数部分となる.

     In this example, indefinite integral of the rational function x^6/(x^5+x+1) is computed. The result is a list which comprises two elements: The first element is the rational part of the integral; The second part is the logarithmic part of the integral. The logarithmic part is again a list which comprises finite number of elements, each of which is of form [root*log(poly),defpoly]. This pair should be interpreted to sum up the expression root*log(poly) through all root's root's of the defpoly. Here, poly contains root, and substitution for root is equally applied to poly. The logarithmic part in total is obtained by applying such interpretation to all element pairs in the second element of the result and then summing them up all.

primdec

     多項式イデアルの準素イデアル分解とその根基の素イデアル分解 (see primadec primedec).

     Primary ideal decomposition of polynomial ideals and prime compotision of radicals (see primadec primedec).

入力インタフェース
=========

Input interfaces
================

既に述べたように, DOS 版, Windows 版, Macintosh 版では入力インタフェースとしてコマンドライン編集およびヒストリ置き換えが組み込まれている. UNIX 版ではこのような機能は組み込まれていないが, 以下で述べるような入力インタフェースが用意されている. これらは Asir バイナリとともに ftp 可能である. ftp server に関しては see 入手方法.

As already mentioned a command line editing facility and a history substitution facility are built-in for DOS, Windows Macintosh version of Asir. UNIX versions of Asir do not have such built-in facilites. Instead, the following input interfaces are prepared. This are also available from our ftp server. As for our ftp server see How to get Risa/Asir.

fep
---

fep とは, SRA の歌代氏により開発されたコマンドライン編集, ヒストリ置き換え用の入力フロントエンドである. このプログラムの元で asir を起動することにより vi あるいは emacs 風のコマンドライン編集および csh 風のヒストリ置き換えが可能になる.

Fep is a general purpose front end processor. The author is K. Utashiro (SRA Inc.).

Under fep, emacs- or vi-like command line editing and csh-like history substitution are available for UNIX commands, including asir.

     % fep asir
     ...
     [0] fctr(x^5-1);
     [[1,1],[x-1,1],[x^4+x^3+x^2+x+1,1]]
     [1] !!                              /* !!+Return                      */

     fctr(x^5-1);                        /* 直前の入力が現れるて編集できる */
     ...                                 /* 編集+Return                    */

     fctr(x^5-1);                        /* The last input appears.        */
     ...                                 /* Edit+Return                    */

     fctr(x^5+1);
     [[1,1],[x+1,1],[x^4-x^3+x^2-x+1,1]]

fep はフリーソフトでソースが入手可能であるが, オリジナルのものは make できる機種 (OS) が限られている. いくつかの機種上で動作するように我々が改造したものが, ftp で入手可能である.

Fep is a free software and the source is available. However machines or operating systems on which the original one can run are limited. The modified version by us running on several unsupported environments is available from our ftp server.

asir.el
-------

asir.el は, Asir の GNU Emacs インタフェースである (著者は宮嶋光治氏 (YVE25250@pcvan.or.jp).  asir.el においては, 通常の emacs で可能な編集機能の他に, ファイル名, コマンド名の completion が実現されている.

asir.el is a GNU Emacs interface for Asir. The author is Koji Miyajima (YVE25250@pcvan.or.jp). In asir.el, completion of file names and command names is realized other than the ordinary editing functions which are available on Emacs.

asir.el は PC-VAN で既に公開されているが, 今回の改訂に伴う変更を行ったものが, やはり ftp で入手可能である.

asir.el is distributed on PC-VAN. The version where several changes have been made according to the current version of Asir is available via ftp.

セットアップ, 使用方法は, asir.el の先頭に記述されている.

The way of setting up and the usage can be found at the top of asir.el.

変更点
===

Appendix
========

Version 990831
--------------

4 年ぶりの大改訂. 整数の 32bit 化他, 中身はずいぶん変わっているものの, 見掛けはそれほど変わっているようには見えない. むしろ, Windows 版などは, plot が使えないため, 退化している.

旧版のユーザがもっとも注意すべき点は, 旧版で作った bsave file を読み込む場合は bload27 を使う必要がある, という点である.

Four years have passed since the last distribution. Though the look and feel seem unchanged, internally there are several changes such as 32-bit representation of bignums. Plotting facilities are not available on Windows.

If you have files created by bsave on the older version, you have to use bload27 to read such files.

Version 950831
--------------

デバッガ
....

Debugger
........

  * 任意の時点にデバッグモードに入れる.

     One can enter the debug mode anytime.

  * finish コマンドの追加.

     A command finish has been appended.

  * up, down, frame コマンドによる, 任意のスタックフレームの参照.

     One can examine any stack frame with up, down and frame.

  * trace コマンドの追加.

     A command trace has been appended.

組み込み函数
......

Built-in functions
..................

  * sdiv() などにおける, 主変数の指定のサポート.

  * sdivm() など, 有限体上での多項式除算の追加.

  * det(), res() などにおける, 有限体上での計算のサポート

  * vtol() (ベクトルからリストへの変換) の追加.

  * map() の追加.

  * One can specify a main variable for sdiv() etc.

  * Functions for polynomial division over finite fields such as sdivm() have been appended.

  * det(), res() can produce results over finite fields.

  * vtol(), conversion from a vector to a list has been appended.

  * map() has been appended.

グレブナ基底
......

Groebner basis computation
..........................

  * グレブナ基底計算機能の組み込み函数化.

  * grm(), hgrm() が gr(), hgr() に変更.

  * gr(), hgr() において, 項順序の指定が必要になった.

  * 項順序の指定方法が拡張された.

  * 有限体上のグレブナ基底計算のサポート.

  * 基底変換による辞書式順序グレブナ基底計算のサポート.

  * いくつかの新しい組み込み函数の提供.

  * Functions for Groebner basis computation have been implemented as built-in functions.

  * grm() and hgrm() have been changed to gr() and hgr() respectively.

  * gr() and hgr() requires explicit specification of an ordering type.

  * Extension of specification of a term ordering type.

  * Groebner basis computations over finite fields.

  * Lex order Groebner basis computation via a modular change of ordering algorithm.

  * Several new built-in functions.

その他
...

Others
......

  * 分散計算用ツール, 函数の追加.

  * 代数体上の GCD 計算におけるモジュラ計算の応用.

  * イデアルの準素分解のサポート.

  * Windows への移植.

  * Implementation of tools for distributed computation.

  * Application of modular computation for GCD computation over algebraic number fields.

  * Implementation of primary decompostion of ideals.

  * Porting to Windows.

Version 940420
--------------

最初の公開版.

The first public verion.

文献
==

References
==========

[Batut et al.]
     Batut, C., Bernardi, D., Cohen, H., Olivier, M., "User's Guide to PARI-GP", 1993.

[Becker,Weispfenning]
     Becker, T., Weispfenning, V., "Groebner Bases", Graduate Texts in Math. 141, Springer-Verlag, 1993.

[Boehm,Weiser]
     Boehm, H., Weiser, M., "Garbage Collection in an Uncooperative Environment", Software Practice & Experience, September 1988, 807-820.

[Gebauer,Moeller]
     Gebauer, R., Moeller, H. M., "An installation of Buchberger's algorithm", J. of Symbolic Computation 6, 275-286.

[Giovini et al.]
     Giovini, A., Mora, T., Niesi, G., Robbiano, L., Traverso, C., ""One sugar cube, please" OR Selection strategies in the Buchberger algorithm", Proc. ISSAC'91, 49-54.

[Noro,Takeshima]
     Noro, M., Takeshima, T., "Risa/Asir -- A Computer Algebra System", Proc. ISSAC'92, 387-396.

[Noro,Yokoyama]
     Noro, M., Yokoyama, K., "A Modular Method to Compute the Rational Univariate Representation of Zero-Dimensional Ideals", J. Symb. Comp. 28/1 (1999), 243-263.

[Shimoyama,Yokoyama]
     Shimoyama, T., Yokoyama, K., "Localization and primary decomposition of polynomial ideals", J. Symb. Comp. 22 (1996), 247-277.

[Shoup]
     Shoup, V., "A new polynomial factorization algorithm and its implementation", J. Symb. Comp. 20 (1995), 364-397.

[Traverso]
     Traverso, C., "Groebner trace algorithms", Proc. ISSAC '88(LNCS 358), 125-138.

[Weber]
     Weber, K., "The accelerated Integer GCD Algorithm", ACM TOMS, 21, 1(1995), 111-122.