%% $OpenXM: OpenXM/doc/Papers/rims2000-tmp-ja.tex,v 1.1 2001/01/18 00:32:09 takayama Exp $ \documentclass{jarticle} %\usepackage{epsfig} \def\epsffile#1{ \fbox{PS file {\tt #1} is included here.} } \def\epsfxsize{ } \def\color#1{ } % do nothing. \begin{document} \section{OX サーバと提供される数学関数} OpenXM の各サーバおよびその数学的機能のうち幾つかを例を あげて説明しよう. \subsection{{\tt ox\_asir}} Risa/Asir は Free で配布されている汎用数式処理ソフトである. たとえば次のような機能を持つ. \begin{enumerate} \item ${\bf Q}$ 係数の $n$ 変数多項式の因数分解 (関数 {\tt fctr}). \\ 例: \begin{verbatim} fctr(y^5-4*y^4+(-x^2+2*x+3)*y^3-x^2*y^2+4*x^2*y+x^4-2*x^3-3*x^2); [[1,1],[y^3-x^2,1],[y-x-1,1],[y+x-3,1] \end{verbatim} \item ${\bf Q}$ の代数拡大体における 1 変数多項式の因数分解. (関数 {\tt af})\\ 次の例は多項式 $x^6-1$ を ${\bf Q}$ に $x^2+x+1=0$ の根を添加した 体で因数分解する例である. \begin{verbatim} [374] load("gr")$ load("sp")$ [375] A1=newalg(x^2+x+1); (#0) [476] af(x^6-1,[A1]); [[1,1],[x+(#0+1),1],[x+(#0),1],[x-1,1],[x+(-#0),1],[x+1,1],[x+(-#0-1),1]] \end{verbatim} $x^2+x+1=0$ の根を $\omega$ としよう. ($\omega^3=1$, $\omega+1 = -\omega^2$ である.) 上の結果は, $\omega$ を用いると, $$ x^6-1 = (x+\omega+1)(x+\omega)(x-1)(x-\omega)(x+1)(x-\omega-1)$$ と因数分解されることを示している. \item 多項式環および微分作用素環 (ワイル代数) におけるグレブナ基底計算 (関数 {\tt gr} および {\tt dp\_gr\_weyl\_main}). 応用として準素イデアル分解の機能ももつ (関数 {\tt primadec}). \\ 例として変数の消去をグレブナ基底の計算でおこなってみよう. $I$ を $n$ 変数多項式環 ${\bf Q}[x_1, \ldots, x_n]$ のイデアルとするとき $I \cap {\bf Q}[x_1]$ の生成元は, $I$ のグレブナ基底を 辞書式順序 (lexicographic order) $x_n > \cdots > x_2 > x_1$ で計算して, グレブナ基底の中から, $x_1$ のみの多項式を取り出してくれば求まる. たとえば, $I$ として, $x_1^2+x_2^2-4$, $x_1 x_2 -1$ で生成される イデアルを考える. \begin{verbatim} [375] load("gr")$ [461] gr([x1^2+x2^2-4,x1*x2-1],[x2,x1],2); [-x1^4+4*x1^2-1,x2+x1^3-4*x1] \end{verbatim} $-x_1^4+4*x_1^2-1$ が, $I \cap {\bf Q}[x_1]$ の生成元である. 消去法とグレブナ基底との関連については, たとえば Cox, Little, O'Shea の教科書 \cite{OpenXM:CLO} の 2 章, 3 章に 入門的な説明がある. \end{enumerate} Asir が用いている数学アルゴリズムについては, 野呂による解説 \cite{OpenXM:noro-book} を参照. \subsection{ {\tt ox\_sm1} } {\tt Kan/sm1} および {\tt Kan/k0} は微分作用素環(ワイル代数) $D$ における グレブナ基底計算をもとにして, $D$ 加群の種々の構成や, 代数多様体の コホモロジの計算をおこなう. 現在, 因数分解, 準素イデアル分解, $b$-関数の $D$ での計算などは, OpenXM プロトコル (OX-RFC 100, 101) を利用して, {\tt ox\_asir} が 担当しており, {\tt ox\_sm1} はサーバであるのみならず, asir の OpenXM サーバ機能をフルに利用しているクライアントでもある. Kan はたとえば次のような機能をもつ. \begin{enumerate} \item $D$ でのグレブナ基底計算 (関数 {\tt gb}). \\ グレブナ基底計算の応用として, あたえられた連立線形偏微分方程式系の 解空間の次元の計算 (holonomic rank) がある. これを例として挙げて おこう. \begin{verbatim} sm1>(cohom.sm1) run ; sm1> [ [( x*Dx + y*Dy -3 ) ( Dx-Dy )] (x,y)] rank :: 1 \end{verbatim} この出力は微分方程式系 $$ \left[ x\frac{\partial}{\partial x}+y\frac{\partial}{\partial y}-3 \right]f = \left[ \frac{\partial}{\partial x}-\frac{\partial}{\partial y}\right]f = 0$$ の解空間の次元は $1$ であることを意味する. この場合は実際に解を書き出すことができて, $f=(x+y)^3$ が解である. \item 代数多様体, たとえば ${\bf C}^n \setminus V(f)$ のコホモロジ群の 計算 ( 関数 {\tt deRham} ). \\ たとえば Kan/k0 での計算は次のようになる. \begin{verbatim} % cd OpenXM/src/k097/lib/restriction % k0 This is kan/k0 Version 1998,12/15 sm1 version = 3.001203 Default ring is Z[x,h]. In(2)= load("demo.k"); In(3)= DeRham2WithAsir( x^3-y^2 ): Step1: Annhilating ideal (II)[ -3*x^2*Dy-2*y*Dx , -2*x*Dx-3*y*Dy-6 ] Step2: (-1,1)-minimal resolution (Res0) [ [ [ 2*x*Dx+3*y*Dy-h^2 ] [ -3*y*Dx^2+2*x*Dy*h ] ] [ [ 3*y*Dx^2-2*x*Dy*h , 2*x*Dx+3*y*Dy ] ] ] Step3: computing the cohomology of the truncated complex. Roots and b-function are [ [ 1 ] , [ 9*s^3-18*s^2+11*s-2 ] ] [ [ 0 , 1 , 1 ] , [ [ 0 , [ ] ] , [ 1 , [ ] ] , [ 1 , [ ] ] ] ] \end{verbatim} Step1の $1/(x^3-y^2)$ の満たす最大の微分方程式の計算, Step3の一般化された $b$-関数とその根の計算では {\tt ox\_asir} を呼び出して 計算している. \item $D^m/I$ の $(u,v)$-minimal free resolution (関数 {\tt Sminimal}). \end{enumerate} $D$ 加群のアルゴリズムのアルゴリズムについては, 本 \cite{OpenXM:SST} が入門的話題から最先端の話題までを扱っている. \subsection{PHC} PHC pack は Jan Verschelde により開発された, 多面体ホモトピー法により代数方程式系の数値解を求める システムである. ホモトピー法というのは, たとえば 代数方程式 $ x^n - x^3+x^2-5 = 0$ を解くために, まずスタートシステム $ x^n - 5 = 0$ を解き, その解を連続的に もとの方程式の解に延長する方法である. 連立代数方程式系の場合には, よい性質をもつスタートシステムを作る 必要があり, そのために多面体の分割をもちいる. これが 多面体ホモトピー法である. 本 \cite{OpenXM:CLO2} の 7.5 節にこの方法の基礎となる 多面体の幾何と根の数の勘定に関する説明がある. 多面体ホモトピー法については, Verschelde による解説の他, 論文 \cite{OpenXM:HS} などが読みやすい. \subsection{gnuplot, M2, tigers, pari, mathematica, OMproxy} 長さの関係もあり詳しくは紹介できないので, 表題のソフトを簡単に紹介しよう. \begin{enumerate} \item gnuplot はグラフを作成するソフト. \item M2 (Macaulay 2) は D.Grayson と M.Stillman により開発されている, 計算代数幾何用のソフト. \item tigers は B.Hubert により開発された, affine toric variety の全ての グレブナ基底を求めるソフト. \item pari は A.Cohen らにより開発されている, 整数論用のソフト. \item Mathematica は有名なので説明の必要はないであろう. \item OMproxy は Java でかかれた, OpenXM のクラスライブラリおよび OpenMath とのデータの相互変換のためのソフトである. \end{enumerate} \subsection{ 1077 functions are available on our servers and libraries} OX server の提供する関数にどのようなものがあるか, リストと簡単なデモを掲載しておこう. これらの関数のなかの一部については, 前節までで簡単に説明した. より詳しくは各コンポーネントシステムのマニュアルや参照されている 論文, 本を見る必要がある. \fbox{\huge {\color{green}Operations on Integers}} \noindent {\color{red} idiv},{\color{red} irem} (division with remainder), {\color{red} ishift} (bit shifting), {\color{red} iand},{\color{red} ior},{\color{red} ixor} (logical operations), {\color{red} igcd},(GCD by various methods such as Euclid's algorithm and the accelerated GCD algorithm), {\color{red} fac} (factorial), {\color{red} inv} (inverse modulo an integer), {\color{red} random} (random number generator by the Mersenne twister algorithm). \medbreak \noindent \fbox{\huge {\color{green}Ground Fields}} \noindent Arithmetics on various fields: the rationals, ${\bf Q}(\alpha_1,\alpha_2,\ldots,\alpha_n)$ ($\alpha_i$ is algebraic over ${\bf Q}(\alpha_1,\ldots,\alpha_{i-1})$), $GF(p)$ ($p$ is a prime of arbitrary size), $GF(2^n)$. \medbreak \noindent \fbox{\huge {\color{green}Operations on Polynomials}} \noindent {\color{red} sdiv }, {\color{red} srem } (division with remainder), {\color{red} ptozp } (removal of the integer content), {\color{red} diff } (differentiation), {\color{red} gcd } (GCD over the rationals), {\color{red} res } (resultant), {\color{red} subst } (substitution), {\color{red} umul} (fast multiplication of dense univariate polynomials by a hybrid method with Karatsuba and FFT+Chinese remainder), {\color{red} urembymul\_precomp} (fast dense univariate polynomial division with remainder by the fast multiplication and the precomputed inverse of a divisor), \noindent \fbox{\huge {\color{green}Polynomial Factorization}} {\color{red} fctr } (factorization over the rationals), {\color{red} fctr\_ff } (univariate factorization over finite fields), {\color{red} af } (univariate factorization over algebraic number fields), {\color{red} sp} (splitting field computation). \medbreak \noindent \fbox{\huge {\color{green} Groebner basis}} \noindent {\color{red} dp\_gr\_main } (Groebner basis computation of a polynomial ideal over the rationals by the trace lifting), {\color{red} dp\_gr\_mod\_main } (Groebner basis over small finite fields), {\color{red} tolex } (Modular change of ordering for a zero-dimensional ideal), {\color{red} tolex\_gsl } (Modular rational univariate representation for a zero-dimensional ideal), {\color{red} dp\_f4\_main } ($F_4$ over the rationals), {\color{red} dp\_f4\_mod\_main } ($F_4$ over small finite fields). \medbreak \noindent \fbox{\huge {\color{green} Ideal Decomposition}} \noindent {\color{red} primedec} (Prime decomposition of the radical), {\color{red} primadec} (Primary decomposition of ideals by Shimoyama/Yokoyama algorithm). \medbreak \noindent \fbox{\huge {\color{green} Quantifier Elimination}} \noindent {\color{red} qe} (real quantifier elimination in a linear and quadratic first-order formula), {\color{red} simpl} (heuristic simplification of a first-order formula). {\scriptsize \begin{verbatim} [0] MTP2 = ex([x11,x12,x13,x21,x22,x23,x31,x32,x33], x11+x12+x13 @== a1 @&& x21+x22+x23 @== a2 @&& x31+x32+x33 @== a3 @&& x11+x21+x31 @== b1 @&& x12+x22+x32 @== b2 @&& x13+x23+x33 @== b3 @&& 0 @<= x11 @&& 0 @<= x12 @&& 0 @<= x13 @&& 0 @<= x21 @&& 0 @<= x22 @&& 0 @<= x23 @&& 0 @<= x31 @&& 0 @<= x32 @&& 0 @<= x33)$ [1] TSOL= a1+a2+a3@=b1+b2+b3 @&& a1@>=0 @&& a2@>=0 @&& a3@>=0 @&& b1@>=0 @&& b2@>=0 @&& b3@>=0$ [2] QE_MTP2 = qe(MTP2)$ [3] qe(all([a1,a2,a3,b1,b2,b3],QE_MTP2 @equiv TSOL)); @true \end{verbatim}} \medbreak \noindent \fbox{\huge {\color{green} Visualization of curves}} \noindent {\color{red} plot} (plotting of a univariate function), {\color{red} ifplot} (plotting zeros of a bivariate polynomial), {\color{red} conplot} (contour plotting of a bivariate polynomial function). \medbreak \noindent \fbox{\huge {\color{green} Miscellaneous functions}} \noindent {\color{red} det} (determinant), {\color{red} qsort} (sorting of an array by the quick sort algorithm), {\color{red} eval} (evaluation of a formula containing transcendental functions such as {\color{red} sin}, {\color{red} cos}, {\color{red} tan}, {\color{red} exp}, {\color{red} log}) {\color{red} roots} (finding all roots of a univariate polynomial), {\color{red} lll} (computation of an LLL-reduced basis of a lattice). \noindent \fbox{\huge {\color{green} $D$-modules}} ($D$ is the Weyl algebra) \noindent {\color{red} gb } (Gr\"obner basis), {\color{red} syz} (syzygy), {\color{red} annfs} (Annhilating ideal of $f^s$), {\color{red} bfunction}, {\color{red} schreyer} (free resolution by the Schreyer method), {\color{red} vMinRes} (V-minimal free resolution), {\color{red} characteristic} (Characteristic variety), {\color{red} restriction} in the derived category of $D$-modules, {\color{red} integration} in the derived category, {\color{red} tensor} in the derived category, {\color{red} dual} (Dual as a D-module), {\color{red} slope}. \medbreak \noindent \fbox{\huge {\color{green} Cohomology groups}} \noindent {\color{red} deRham} (The de Rham cohomology groups of ${\bf C}^n \setminus V(f)$, {\color{red} ext} (Ext modules for a holonomic $D$-module $M$ and the ring of formal power series). \medbreak \noindent \fbox{\huge {\color{green} Differential equations}} \noindent Helping to derive and prove {\color{red} combinatorial} and {\color{red} special function identities}, {\color{red} gkz} (GKZ hypergeometric differential equations), {\color{red} appell} (Appell's hypergeometric differential equations), {\color{red} indicial} (indicial equations), {\color{red} rank} (Holonomic rank), {\color{red} rrank} (Holonomic rank of regular holonomic systems), {\color{red} dsolv} (series solutions of holonomic systems). \medbreak \noindent \fbox{\huge {\color{green} OpenMATH support}} \noindent {\color{red} om\_xml} (CMO to OpenMATH XML), {\color{red} om\_xml\_to\_cmo} (OpenMATH XML to CMO). \medbreak \noindent \fbox{\huge {\color{green} Homotopy Method}} \noindent {\color{red} phc} (Solving systems of algebraic equations by numerical and polyhedral homotopy methods). \medbreak \noindent \fbox{\huge {\color{green} Toric ideal}} \noindent {\color{red} tigers} (Enumerate all Gr\"obner basis of a toric ideal. Finding test sets for integer program), {\color{red} arithDeg} (Arithmetic degree of a monomial ideal), {\color{red} stdPair} (Standard pair decomposition of a monomial ideal). \medbreak \noindent \fbox{\huge {\color{green} Communications}} \noindent {\color{red} ox\_launch} (starting a server), {\color{red} ox\_launch\_nox}, {\color{red} ox\_shutdown}, {\color{red} ox\_launch\_generic}, {\color{red} generate\_port}, {\color{red} try\_bind\_listen}, {\color{red} try\_connect}, {\color{red} try\_accept}, {\color{red} register\_server}, {\color{red} ox\_rpc}, {\color{red} ox\_cmo\_rpc}, {\color{red} ox\_execute\_string}, {\color{red} ox\_reset} (reset the server), {\color{red} ox\_intr}, {\color{red} register\_handler}, {\color{red} ox\_push\_cmo}, {\color{red} ox\_push\_local}, {\color{red} ox\_pop\_cmo}, {\color{red} ox\_pop\_local}, {\color{red} ox\_push\_cmd}, {\color{red} ox\_sync}, {\color{red} ox\_get}, {\color{red} ox\_pops}, {\color{red} ox\_select}, {\color{red} ox\_flush}, {\color{red} ox\_get\_serverinfo} \medbreak \noindent In addition to these functions, {\color{green} Mathematica functions} can be called as server functions. \medbreak \noindent \fbox{\huge {\color{green} Examples}} {\footnotesize \begin{verbatim} [345] sm1_deRham([x^3-y^2*z^2,[x,y,z]]); [1,1,0,0] /* dim H^i = 1 (i=0,1), =0 (i=2,3) */ \end{verbatim}} \noindent {\footnotesize \begin{verbatim} [287] phc(katsura(7)); B=map(first,Phc)$ [291] gnuplot_plotDots(B,0)$ \end{verbatim} } \epsfxsize=3cm \begin{center} \epsffile{../calc2000/katsura7.ps} %\epsffile{katsura7.ps} \end{center} %%The first components of the solutions to the system of algebraic equations Katsura 7. \medbreak \noindent \fbox{ {\color{green} Authors}} Castro-Jim\'enez, Dolzmann, Hubert, Murao, Noro, Oaku, Okutani, Shimoyama, Sturm, Takayama, Tamura, Verschelde, Yokoyama. \section{OX サーバを組み合わせて利用した例} 具体的な数学的問題をもとに数学ソフトの開発をするというのは 一つの健全な開発手法であろう. OX サーバの開発でも, そのような開発手法をとりたいと思っており, いろいろな数学的問題をさがしている. その中の一つの問題は, 多変数超幾何関数に関して何でも答えられるシステムの 開発である. ここでは, 多変数超幾何関数として, いわゆる GKZ hypergeometric system の解を考えている. GKZ hypergeometric system は $n$ 次元空間の点集合に付随してきまる 連立線形偏微分方程式系である. $n$ 次元空間の点集合を考えるため, 多面体の幾何を扱う必要があるし, 連立線形偏微分方程式系を考えるため, $D$ 加群を扱う必要もある. GKZ system は affine toric ideal を含むため, affine toric ideal の システムも必要である. 関数の数値計算のためには, 数値積分的な手法も重要であるが, これはまだ 全く手をつけていない. GKZ hypergeometric system については, 本 \cite{OpenXM:SST} を参照. 現在の {\tt OpenXM/src/asir-contrib} のパッケージは, GKZ hypergeometric system に関して何でもこたえられるシステムを目標に, asir をクライアントとして, ox servers をいろいろくっつけたシステムである. 例を一つあげよう. {\tt dsolv\_starting\_term} は正則ホロノミック系を cone 上で収束する 多変数の級数で解くための 関数の一つであり, 級数展開の主部をもとめる. \begin{enumerate} \item 行列(点配置) $\pmatrix{ 1&1&1&1&1 \cr 1&1&0&-1&0 \cr 0&1&1&-1&0 \cr}$ に付随する GKZ hypergeometric system を関数 {\tt sm1\_gkz} で求める. \begin{verbatim} [1076] F = sm1_gkz( [ [[1,1,1,1,1],[1,1,0,-1,0],[0,1,1,-1,0]], [1,0,0]]); [[x5*dx5+x4*dx4+x3*dx3+x2*dx2+x1*dx1-1,-x4*dx4+x2*dx2+x1*dx1, -x4*dx4+x3*dx3+x2*dx2, -dx2*dx5+dx1*dx3,dx5^2-dx2*dx4],[x1,x2,x3,x4,x5]] \end{verbatim} \item このシステム {\tt F} の 方向 $(1,1,1,1,0)$ における 級数解の主部を求める. \begin{verbatim} [1077] A= dsolv_starting_term(F[0],F[1],[1,1,1,1,0])$ Computing the initial ideal. Done. Computing a primary ideal decomposition. Primary ideal decomposition of the initial Frobenius ideal to the direction [1,1,1,1,0] is [[[x5+2*x4+x3-1,x5+3*x4-x2-1,x5+2*x4+x1-1,3*x5^2+(8*x4-6)*x5-8*x4+3, x5^2-2*x5-8*x4^2+1,x5^3-3*x5^2+3*x5-1], [x5-1,x4,x3,x2,x1]]] ----------- root is [ 0 0 0 0 1 ] ----------- dual system is [x5^2+(-3/4*x4-1/2*x3-1/4*x2-1/2*x1)*x5+1/8*x4^2 +(1/4*x3+1/4*x1)*x4+1/4*x2*x3-1/8*x2^2+1/4*x1*x2, x4-2*x3+3*x2-2*x1,x5-x3+x2-x1,1] \end{verbatim} \item 展開の主部 4 通りあり, それぞれを因数分解すると, 次のようになる. たとえば, 3 番目の {\tt [[1,1],[x5,1],[-log(x1)+log(x2)-log(x3)+log(x5),1]], } は, $$ x_5 (-\log x_1 + \log x_2 - \log x_3 + \log x_5) = x+5 \log \frac{x_2 x_5}{x_1 x_3} $$ から始まる級数解が存在することを意味する. \begin{verbatim} [1078] A[0]; [[ 0 0 0 0 1 ]] [1079] map(fctr,A[1][0]); [[[1/8,1],[x5,1],[log(x2)+log(x4)-2*log(x5),1], [2*log(x1)-log(x2)+2*log(x3)+log(x4)-4*log(x5),1]], [[1,1],[x5,1],[-2*log(x1)+3*log(x2)-2*log(x3)+log(x4),1]], [[1,1],[x5,1],[-log(x1)+log(x2)-log(x3)+log(x5),1]], [[1,1],[x5,1]]] \end{verbatim} \end{enumerate} {\tt dsolv\_starting\_term} では, kan/sm1 が D-加群の計算, asir が準素イデアル分解の計算, 解の計算を担当している. 解の展開の方向が何通り存在するかを調べるには, tigers を援用するとよい. \begin{thebibliography}{99} \bibitem{OpenXM:CLO} Cox, D., Little, J., O'Shea; \bibitem{OpenXM:CLO2} Cox, D., Little, J., O'Shea, {\it Using Algebraic Geometry}, Springer, 1998. \bibitem{OpenXM:HS} Huber, B., Sturmfels, B., A Polyhedral Method for Solving Sparse Polynomial Systems, Mathematics of Computation, {\bf 64} (1995), 1541--1555. \bibitem{OpenXM:noro-book} 野呂: 計算代数入門, Rokko Lectures in Mathematics, 9, 2000. ISBN 4-907719-09-4. \\ {\tt ftp://ftp.math.kobe-u.ac.jp/pub/OpenXM/Head/openxm-head.tar.gz} のディレクトリ {\tt OpenXM/doc/compalg} にこの本の TeX ソースがある. \bibitem{OpenXM:SST} Saito, M., Sturmfels, B., Takayama, N., {\it Gr\"obner deformations of hypergeometric differential equations}. Algorithms and Computation in Mathematics, 6. Springer-Verlag, Berlin, 2000. \end{thebibliography} \end{document}