Annotation of OpenXM/src/asir-contrib/packages/doc/noro_pd/noro_pd-ja.texi, Revision 1.3
1.3 ! noro 1: %comment $OpenXM: OpenXM/src/asir-contrib/packages/doc/noro_pd/noro_pd-ja.texi,v 1.2 2011/02/21 09:40:11 noro Exp $
1.1 noro 2: %comment --- おまじない ---
3: \input ../../../../asir-doc/texinfo
4: @iftex
5: @catcode`@#=6
6: @def@fref#1{@xrefX[#1,,@code{#1},,,]}
7: @def@b#1{{@bf@gt #1}}
8: @catcode`@#=@other
9: @end iftex
10: @overfullrule=0pt
11: @c -*-texinfo-*-
12: @comment %**start of header
13: @comment --- おまじない終り ---
14:
15: @comment --- GNU info ファイルの名前 ---
16: @setfilename asir-contrib-noro_pd
17:
18: @comment --- タイトル ---
19: @settitle noro_pd
20:
21: @comment %**end of header
22: @comment %@setchapternewpage odd
23:
24: @comment --- おまじない ---
25: @ifinfo
26: @macro fref{name}
27: @ref{\name\,,@code{\name\}}
28: @end macro
29: @end ifinfo
30:
31: @iftex
32: @comment @finalout
33: @end iftex
34:
35: @titlepage
36: @comment --- おまじない終り ---
37:
38: @comment --- タイトル, バージョン, 著者名, 著作権表示 ---
39: @title noro_pd
40: @subtitle noro_pd User's Manual
41: @subtitle Edition 1.0
1.2 noro 42: @subtitle Feb 2011
1.1 noro 43:
44: @author by Masayuki Noro
45: @page
46: @vskip 0pt plus 1filll
47: Copyright @copyright{} Masayuki Noro
48: 2011. All rights reserved.
49: @end titlepage
50:
51: @comment --- おまじない ---
52: @synindex vr fn
53: @comment --- おまじない終り ---
54:
55: @comment --- @node は GNU info, HTML 用 ---
56: @comment --- @node の引数は node-name, next, previous, up ---
57: @node Top,, (dir), (dir)
58:
59: @comment --- @menu は GNU info, HTML 用 ---
60: @comment --- chapter 名を正確に並べる ---
61: @menu
62: * 準素分解パッケージ noro_pd.rr::
63: * Index::
64: @end menu
65:
66: @comment --- chapter の開始 ---
67: @comment --- 親 chapter 名を正確に ---
68: @node 準素分解パッケージ noro_pd.rr,,, Top
69: @chapter 準素分解パッケージ noro_pd.rr
70:
71: @comment --- section 名を正確に並べる ---
72: @menu
73: * 準素分解::
74: @end menu
75:
76: このマニュアルでは, asir-contrib パッケージに収録されている,
77: 準素パッケージ @samp{noro_pd.rr} について解説する.
78: このパッケージを使うには, まず @samp{noro_pd.rr} をロードする.
79: @example
80: [1539] load("noro_pd.rr");
81: @end example
82: このパッケージの函数を呼び出すには, 全て @code{noro_pd.} を先頭につける.
83: @example
84:
85: @end example
86:
87: @comment --- section の開始 ---
88: @comment --- 書体指定について ---
89: @comment --- @code{} はタイプライタ体表示 ---
90: @comment --- @var{} は斜字体表示 ---
91: @comment --- @b{} はボールド表示 ---
92: @comment --- @samp{} はファイル名などの表示 ---
93:
94: @node アルゴリズムの概要,,, 準素分解パッケージ noro_pd.rr
95:
96: @section 準素分解
97:
98: @menu
99: * noro_pd.syci_dec::
100: * noro_pd.prime_dec::
101: @end menu
102:
103: @node noro_pd.syci_dec,,, 準素分解
104:
105: @subsection @code{noro_pd.syci_dec}
106: @findex noro_pd.syci_dec
107:
108: @table @t
109: @item noro_pd.syci_dec(@var{I},@var{vars}[|@var{options}])
110: イデアル @var{I} の最短準素分解を計算する.
111: @end table
112:
113: @table @var
114: @item return
115: @var{[QL(1),QL(2),...]} なるリスト, 各 @var{QL(i)} は
1.3 ! noro 116: @var{[[Q(i1),P(i1)],[(i2),P(i2)],...]} なるリスト.
1.1 noro 117:
118: @item I
119: 多項式リスト
120: @item vars
121: 変数リスト
122: @item options
123: 下の説明参照.
124: @end table
125:
126: @itemize @bullet
127: @item
128: イデアル @var{I} の最短準素分解を計算する.
129: @samp{noro_pd.rr} で実装されている準素分解アルゴリズムは SYCI アルゴリズム
130: と呼ばれるもので, @samp{primdec} に実装されている Shimoyama-Yokoyama
131: (SY アルゴリズム) を改良したものである.
132:
133: イデアル @var{I} の付属素イデアル全体 @var{Ass(I)} を次のように分ける:
134: @var{A(1)} を極小付属素イデアル全体とし, @var{Ass(I)}から
135: @var{A(1)},...,@var{A(i-1)} を除いたものの中で極小なもの全体を @var{A(i)}
136: とする. SYCI アルゴリズムは, @var{A(i)} を @var{i} の小さい順に
137: 計算しつつ, 対応する準素成分
138: を計算するアルゴリズムである. 準素成分の計算は省略することができる. この
139: 場合, @var{I} の付属素イデアルのみを計算するアルゴリズムとなる. @var{A(i)}
140: に属する付属素イデアルおよび対応する準素成分はレベル @var{i} であるという.
141:
142: 出力において, @var{Q(ij)} は @var{I} の @var{Pij}-準素成分であり, @var{Q(ij)} 全体が
1.3 ! noro 143: @var{I} の最短準素分解を与える.
! 144: 各 @var{QL(i)} はレベル @var{i} の成分全体
1.1 noro 145: を与える. 特に @var{QL(1)} は孤立成分および極小付属素イデアル全体を与える.
1.3 ! noro 146: @var{QL(1)} の各成分のみ, 3つ目の要素として極大独立集合を持つ.
1.1 noro 147: @item
148: オプション @var{ass=1} が指定された場合, @var{QL(1)} に現われる成分 @var{Q(1j)} のみ準素成分
149: (孤立準素成分)となるが, @var{QL(2)} 以降に現われる @var{Q(ij)} は @var{I} のある中間
150: 分解成分となる. しかし, @var{P(ij)} は @var{I} の付属素イデアルであり,
151: @var{P(ij)} 全体が @var{I} の付属素イデアル全体の集合を与えることは保証される.
152: @item
153: デフォルトでは有理数体上での分解を計算するが, オプション @var{mod=p} (@var{p} は30ビット以下の素数) を
154: 指定すると @var{p}元体上での分解を計算する. ただし, @var{p} が小さいときには正しく計算
155: できないか, 無限ループに陥る. (@var{p} が 5桁以上なら問題ないであろう.)
156: @item
157: @var{iso=n} (@var{n}は 0,1,2,3のいずれか) を指定すると, saturation 計算の方法が変わる.
158: デフォルトでは @var{n=1} である.
159: @item
160: オプション @var{time=1} を指定すると, 計算時間の内訳を表示する.
161: @item
162: オプション @var{para=proclist} を指定すると, 部分的な分散計算を行う.
163: @var{proclist}は @code{noro_pd.init_pprocs} により生成されたプロセスのリストである.
1.3 ! noro 164: @item
! 165: オプション @var{f4=1} が指定された場合, 可能な限り F4 アルゴリズムを用いる.
! 166: デフォルトでは Buchberger アルゴリズムを用いる.
! 167: @item
! 168: オプション @var{trace=1} が指定された場合, 可能な限り trace アルゴリズムを用いる.
! 169: デフォルトでは trace なしの Buchberger または F4 アルゴリズムを用いる.
! 170: @item
! 171: オプション @var{intgb=1} が指定された場合, 複数のイデアルの共通部分を, 2 つずつの
! 172: イデアルの共通部分計算の繰り返しとして計算する際に, 毎回その共通部分のグレブナー基底を
! 173: 計算する. デフォルトではグレブナー基底を計算せずに繰り返す.
! 174:
1.1 noro 175: @end itemize
176:
177: @example
178: [1539] load("noro_pd.rr");
179: [1707] B=[x00*x11-x01*x10,x01*x12-x02*x11,x02*x13-x03*x12,x03*x14-x04*x13,
180: -x11*x20+x21*x10,-x21*x12+x22*x11,-x22*x13+x23*x12,-x23*x14+x24*x13]$
181: [1708] V=[x00,x01,x02,x03,x04,x10,x11,x12,x13,x14,x20,x21,x22,x23,x24]$
182: [1709] QD=noro_pd.syci_dec(B,V|time=1)$
183: [total,1.08407,ass,0.620039,pd,0.33202,iso,0.260016,int,0.024003,
184: ext,0.464029]
185: [elapsed,1.09038,ass,0.624087,pd,0.338769,iso,0.244057,int,0.0343642,
186: ext,0.466293]
187: [1710] map(length,QD);
188: [10,5,3,1]
189: [1711] QD[2][0];
190: [[x03*x01*x14*x20-x21*x04*x03*x10,(x23*x21*x02-x22*x21*x03)*x10,
191: x23*x21*x03*x10,x01*x12*x20-x21*x02*x10,-x01*x13*x20+x21*x03*x10,
192: -x21*x03*x14+x23*x04*x11,-x22*x03*x14+x23*x04*x12,x01^2,x03^2,
193: -x00*x11+x01*x10,x10^2,x01*x11,-x01*x12+x02*x11,x01*x13-x03*x11,
194: x10*x11,x11^2,-x02*x13+x03*x12,-x11*x12,x12^2,x03*x13,-x03*x14+x04*x13,
195: x11*x13,-x12*x13,x13^2,x13*x14,x14^2,-x11*x20+x21*x10,x21*x11,
196: x21*x12-x22*x11,x21*x13-x23*x11,x21^2,x22*x13-x23*x12,-x23*x13,
197: -x23*x14+x24*x13,x23^2],
198: [x01,x03,x10,x11,x12,x13,x14,x21,x23]]
199: @end example
200:
201: @node noro_pd.prime_dec,,, 準素分解
202:
203: @subsection @code{noro_pd.prime_dec}
204: @findex noro_pd.prime_dec
205:
206: @table @t
207: @item noro_pd.syci_dec(@var{I},@var{vars}[|@var{options}])
208: イデアル @var{I} の根基の素イデアル分解を計算する.
209: @end table
210:
211: @table @var
212: @item return
213: リスト (成分の詳細は下で説明する)
214: @item I
215: 多項式リスト
216: @item vars
217: 変数リスト
218: @item options
219: 下の説明参照.
220: @end table
221:
222: @itemize @bullet
223: @item
224: デフォルトでは, @var{I} の根基の素イデアル分解の成分のリスト
225: @var{[P(1),P(2),...]} を返す.
226: @item
227: オプション @var{indep=1} が指定された場合, @var{[[P(1),Y(1)],[P(2),Y(2)],...]}
228: を返す. ここで, @var{Y(i)} は @var{P(i)} に対する極大独立集合である.
229: @item
230: オプション @var{radical=1} が指定された場合, 素イデアル成分のリスト @var{PL}
231: と, @var{I} の根基 @var{rad} のペアのリスト @var{[PL,rad]} が返される.
232: @end itemize
233:
234: @example
235: [1712] PD=noro_pd.prime_dec(B,V|radical=1)$
236: [1713] PD[0][0];
237: [x10,-x11,x12,x13,x14]
238: [1714] PD[1];
239: [-x03*x02*x01*x14*x20+x24*x02*x01*x00*x13,...,x23*x14-x24*x13]
240: @end example
241:
242:
243: @section 関連する関数
244:
245: @menu
246: * noro_pd.ideal_intersection::
247: * noro_pd.ideal_intersection_m::
248: * noro_pd.ideal_list_intersection::
249: * noro_pd.colon::
250: * noro_pd.ideal_colon::
251: * noro_pd.sat::
252: * noro_pd.ideal_sat::
253: * noro_pd.init_pprocs::
254: @end menu
255:
256: @node noro_pd.ideal_intersection,,, 関連する関数
257:
258: @subsection @code{noro_pd.ideal_intersection}
259: @findex noro_pd.ideal_intersection
260:
261: @table @t
262: @item noro_pd.ideal_intersection(@var{I1},@var{I2},@var{vars},@var{ord}[|@var{mod=p}])
263: イデアル @var{I1}, @var{I2} の共通部分を計算する.
264: @end table
265:
266: @table @var
267: @item return
268: 多項式リスト
269:
270: @item I
271: 多項式リスト
272: @item vars
273: 変数リスト
274: @item ord
275: 項順序
276: @end table
277:
278: @itemize @bullet
279: @item
280: 返されるリストは @var{I1} と @var{I2} の共通部分の @var{ord} に関するグレブナー
281: 基底になっている.
282: @item
283: デフォルトでは有理数体上で計算だが, オプション @var{mod=p} が指定された場合
284: @var{p}元体上での計算を行う.
285: @end itemize
286:
287: @example
288: [1707] A=[j*h*g*f*e*d*b,j*i*g*d*c*b,j*i*h*g*d*b,j*i*h*e*b,i*e*c*b,z]$
289: [1708] B=[a*d-j*c,b*c,d*e-f*g*h]$
290: [1709] V=[a,b,c,d,e,f,g,h,i,j,z]$
291: [1710] noro_pd.ideal_intersection(A,B,V,0);
292: [(j*h*g*f*e^2*d^2-j*h^2*g^2*f^2*e*d)*b,j*h*g*f*e*d*b*a,
293: -j*h*g*f*e*d*c*b,j*i*h*g*f*e*b*a,(-j*i*h*e*d^2+j*i*h^2*g*f*d)*b,
294: (-j*i*h*e^2*d+j*i*h^2*g*f*e)*b,-j*i*h*e*d*b*a,-j*i*h*g*d*b*a,
295: j*i*g*d*c*b,i*e*c*b,-z*e*d+z*h*g*f,-z*c*b,-z*d*a+z*j*c]
296: @end example
297:
298: @node noro_pd.ideal_intersection_m,,, 関連する関数
299:
300: @subsection @code{noro_pd.ideal_intersection_m}
301: @findex noro_pd.ideal_intersection_m
302:
303: @table @t
304: @item noro_pd.ideal_intersection_m(@var{I1},@var{I2},@var{vars},@var{ord}[|@var{mod=p}])
305: イデアル @var{I1}, @var{I2} の共通部分を計算する.
306: @end table
307:
308: @table @var
309: @item return
310: 多項式リスト
311:
312: @item I
313: 多項式リスト
314: @item vars
315: 変数リスト
316: @item ord
317: 項順序
318: @end table
319:
320: @itemize @bullet
321: @var{I2} がグレブナー基底で, @var{I1} の生成系の個数が多い場合に
322: @code{noro_pd.ideal_intersection} より高速な場合がある.
323: @item
324: 返されるリストは共通部分の生成系だが
325: 必ずしも共通部分のグレブナー基底になってはいない.
326: @item
327: デフォルトでは有理数体上で計算だが, オプション @var{mod=p} が指定された場合
328: @var{p}元体上での計算を行う.
329: @end itemize
330:
331: @example
332: [1754] B=[z*j*i*e*d*c*b+(z*i*h*g+z*j*h)*f*e*d*c,...,z*j*e*c*b+4*z*i*h*g*e*c]
333: [1755] V=[b,c,d,e,f,g,h,i,j,z]
334: [1756] G=nd_gr(B,V,0,0)$
335: [1757] cputime(1)$
336: 0sec(1.907e-06sec)
337: [1758] I1=noro_pd.ideal_intersection(G,G,V,0)$
338: 0.316sec + gc : 0.012sec(0.3301sec)
339: [1759] I2=noro_pd.ideal_intersection_m(G,G,V,0)$
340: 0.064sec + gc : 0.012sec(0.07933sec)
341: @end example
342:
343: @node noro_pd.ideal_list_intersection,,, 関連する関数
344:
345: @subsection @code{noro_pd.ideal_list_intersection}
346: @findex noro_pd.ideal_list_intersection
347:
348: @table @t
349: @item noro_pd.ideal_intersection(@var{ilist},@var{vars},@var{ord}[|@var{mod=p}])
350: イデアルのリスト @var{ilist} の成分の共通部分を計算する.
351: @end table
352:
353: @table @var
354: @item return
355: 多項式リスト
356:
357: @item ilist
358: 多項式リストのリスト
359: @item vars
360: 変数リスト
361: @end table
362:
363: @itemize @bullet
364: @item
365: 返されるリストは共通部分のグレブナー基底になっている.
366: @item
367: デフォルトでは有理数体上で計算だが, オプション @var{mod=p} が指定された場合
368: @var{p}元体上での計算を行う.
369: @end itemize
370:
371: @example
372: [1709] PL=noro_pd.prime_dec(B,V|radical=1)$
373: [1710] Int=noro_pd.ideal_list_intersection(PL[0],V,0)$
374: [1711] gb_comp(Int,PL[1]);
375: 1
376: @end example
377:
378: @subsection @code{noro_pd.colon}
379: @findex noro_pd.colon
380:
381: @table @t
382: @item noro_pd.colon(@var{I},@var{f},@var{vars}[|@var{mod=p}])
383: @var{I:f} を計算する.
384: @end table
385:
386: @table @var
387: @item return
388: 多項式リスト
389:
390: @item I
391: 多項式リスト
392: @item f
393: 多項式
394: @item vars
395: 変数リスト
396: @end table
397:
398: @itemize @bullet
399: @item
400: 返されるリストは @var{I:f} のグレブナー基底とは限らない.
401: @item
402: デフォルトでは有理数体上で計算だが, オプション @var{mod=p} が指定された場合
403: @var{p}元体上での計算を行う.
404: @end itemize
405:
406: @example
407: [1640] B=[(x+y+z)^50,(x-y+z)^50]$
408: [1641] V=[x,y,z]$
409: [1642] noro_pd.colon(B,y^98,V);
410: [-x-z,-y]
411: @end example
412:
413: @subsection @code{noro_pd.ideal_colon}
414: @findex noro_pd.colon
415:
416: @table @t
417: @item noro_pd.colon(@var{I},@var{J},@var{vars}[|@var{mod=p}])
418: @var{I:J} を計算する.
419: @end table
420:
421: @table @var
422: @item return
423: 多項式リスト
424:
425: @item I
426: 多項式リスト
427: @item J
428: 多項式リスト
429: @item vars
430: 変数リスト
431: @end table
432:
433: @itemize @bullet
434: @item
435: 返されるリストは@var{I:J}のグレブナー基底になっている.
436: @item
437: デフォルトでは有理数体上で計算だが, オプション @var{mod=p} が指定された場合
438: @var{p}元体上での計算を行う.
439: @end itemize
440:
441: @example
442: [1640] B=[(x+y+z)^50,(x-y+z)^50]$
443: [1641] V=[x,y,z]$
444: [1642] noro_pd.ideal_colon(B,[(x+y+z)^49,(x-y+z)^49],V);
445: [-y^49*x-z*y^49,-y^50,-x^2-2*z*x+y^2-z^2]
446: @end example
447:
448: @subsection @code{noro_pd.sat}
449: @findex noro_pd.sat
450:
451: @table @t
452: @item noro_pd.sat(@var{I},@var{f},@var{vars}[|@var{mod=p}])
453: @var{I} の @var{f} による saturation を計算する.
454: @end table
455:
456: @table @var
457: @item return
458: 多項式リスト
459:
460: @item I
461: 多項式リスト
462: @item f
463: 多項式
464: @item vars
465: 変数リスト
466: @end table
467:
468: @itemize @bullet
469: @item
470: 返されるリストは@var{I:f}のグレブナー基底になっている.
471: @item
472: デフォルトでは有理数体上で計算だが, オプション @var{mod=p} が指定された場合
473: @var{p}元体上での計算を行う.
474: @end itemize
475:
476: @example
477: [1640] B=[(x+y+z)^50,(x-y+z)^50]$
478: [1641] V=[x,y,z]$
479: [1642] noro_pd.sat(B,y,V);
480: [1]
481: @end example
482:
483: @subsection @code{noro_pd.ideal_sat}
484: @findex noro_pd.ideal_sat
485:
486: @table @t
487: @item noro_pd.ideal_sat(@var{I},@var{J},@var{vars}[|@var{mod=p}])
488: @var{I:J} を計算する.
489: @end table
490:
491: @table @var
492: @item return
493: 多項式リスト
494:
495: @item I
496: 多項式リスト
497: @item J
498: 多項式リスト
499: @item vars
500: 変数リスト
501: @end table
502:
503: @itemize @bullet
504: @item
505: 返されるリストは@var{I:J}のグレブナー基底になっている.
506: @item
507: デフォルトでは有理数体上で計算だが, オプション @var{mod=p} が指定された場合
508: @var{p}元体上での計算を行う.
509: @end itemize
510:
511: @example
512: [1640] B=[(x+y+z)^50,(x-y+z)^50]$
513: [1641] V=[x,y,z]$
514: [1642] noro_pd.ideal_sat(B,[(x+y+z)^49,(x-y+z)^49],V);
515: [1]
516: @end example
517:
518: @subsection @code{noro_pd.init_pprocs}
519: @findex noro_pd.init_pprocs
520:
521: @table @t
522: @item noro_pd.init_pprocs(@var{m}[|@var{nox=1}])
523: 分散計算用プロセスを起動する.
524: @end table
525:
526: @table @var
527: @item return
528: 整数リスト
529:
530: @item m
531: 正整数
532: @end table
533:
534: @itemize @bullet
535: @item
536: 分散計算に用いるためのプロセス (@code{ox_asir})を起動し, その番号のリストを返す.
537: @item
538: ホームディレクトリの @samp{.asirrc} に @code{load("noro_pd.rr")$} を
539: 入れておくことで, @code{ox_asir} の起動時に @samp{noro_pd.rr} が
540: 読み込まれ, 分散計算の準備ができる.
541: @item
542: オプション @var{nox=1} が指定された場合, 起動されたプロセスからの
543: 画面出力のためのウィンドウが開かない.
544: @end itemize
545:
546: @example
547: [1544] P=noro_pd.init_pprocs(6|nox=1)$
548: [1545] B=[x00*x11-x01*x10,x01*x12-x02*x11,x02*x13-x03*x12,x03*x14-x04*x13,
549: x04*x15-x05*x14,x05*x16-x06*x15,x06*x17-x07*x16,-x11*x20+x21*x10,
550: -x21*x12+x22*x11,-x22*x13+x23*x12,-x23*x14+x24*x13,-x24*x15+x25*x14,
551: -x25*x16+x26*x15,-x26*x17+x27*x16]$
552: [1546] V=[x00,x01,x02,x03,x04,x05,x06,x07,x10,x11,x12,x13,x14,x15,x16,
553: x17,x20,x21,x22,x23,x24,x25,x26,x27]$
554: [1547] noro_pd.syci_dec(B,V|time=1)$
555: [total,205.581,ass,108.743,pd,31.582,iso,64.9081,int,11.7367,ext,96.8381]
556: [elapsed,206.177,ass,109.052,pd,31.679,iso,65.0682,int,11.7853,ext,97.1254]
557: [1548] noro_pd.syci_dec(B,V|time=1,para=P)$
558: [total,30.0339,ass,29.5498,pd,23.7695,iso,1.96412,int,3.32021,ext,0.48403]
559: [elapsed,79.0897,ass,62.5683,pd,26.0532,iso,28.037,int,7.97536,ext,16.5214]
560: @end example
561: @comment --- おまじない ---
562: @node Index,,, Top
563: @unnumbered Index
564: @printindex fn
565: @printindex cp
566: @iftex
567: @vfill @eject
568: @end iftex
569: @summarycontents
570: @contents
571: @bye
572: @comment --- おまじない終り ---
573:
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>