Annotation of OpenXM/src/asir-contrib/packages/doc/noro_pd/noro_pd-ja.texi, Revision 1.2
1.2 ! noro 1: %comment $OpenXM: OpenXM/src/asir-contrib/packages/doc/noro_pd/noro_pd-ja.texi,v 1.1 2011/02/21 09:27:07 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)} は
116: @var{[[Q(i1),P(i1)],[Q(i2),P(i2)],...]} なるリスト.
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)} 全体が
143: @var{I} の最短準素分解を与える. 各 @var{QL(i)} はレベル @var{i} の成分全体
144: を与える. 特に @var{QL(1)} は孤立成分および極小付属素イデアル全体を与える.
145: @item
146: オプション @var{ass=1} が指定された場合, @var{QL(1)} に現われる成分 @var{Q(1j)} のみ準素成分
147: (孤立準素成分)となるが, @var{QL(2)} 以降に現われる @var{Q(ij)} は @var{I} のある中間
148: 分解成分となる. しかし, @var{P(ij)} は @var{I} の付属素イデアルであり,
149: @var{P(ij)} 全体が @var{I} の付属素イデアル全体の集合を与えることは保証される.
150: @item
151: デフォルトでは有理数体上での分解を計算するが, オプション @var{mod=p} (@var{p} は30ビット以下の素数) を
152: 指定すると @var{p}元体上での分解を計算する. ただし, @var{p} が小さいときには正しく計算
153: できないか, 無限ループに陥る. (@var{p} が 5桁以上なら問題ないであろう.)
154: @item
155: @var{iso=n} (@var{n}は 0,1,2,3のいずれか) を指定すると, saturation 計算の方法が変わる.
156: デフォルトでは @var{n=1} である.
157: @item
158: オプション @var{time=1} を指定すると, 計算時間の内訳を表示する.
159: @item
160: オプション @var{para=proclist} を指定すると, 部分的な分散計算を行う.
161: @var{proclist}は @code{noro_pd.init_pprocs} により生成されたプロセスのリストである.
162: @end itemize
163:
164: @example
165: [1539] load("noro_pd.rr");
166: [1707] B=[x00*x11-x01*x10,x01*x12-x02*x11,x02*x13-x03*x12,x03*x14-x04*x13,
167: -x11*x20+x21*x10,-x21*x12+x22*x11,-x22*x13+x23*x12,-x23*x14+x24*x13]$
168: [1708] V=[x00,x01,x02,x03,x04,x10,x11,x12,x13,x14,x20,x21,x22,x23,x24]$
169: [1709] QD=noro_pd.syci_dec(B,V|time=1)$
170: [total,1.08407,ass,0.620039,pd,0.33202,iso,0.260016,int,0.024003,
171: ext,0.464029]
172: [elapsed,1.09038,ass,0.624087,pd,0.338769,iso,0.244057,int,0.0343642,
173: ext,0.466293]
174: [1710] map(length,QD);
175: [10,5,3,1]
176: [1711] QD[2][0];
177: [[x03*x01*x14*x20-x21*x04*x03*x10,(x23*x21*x02-x22*x21*x03)*x10,
178: x23*x21*x03*x10,x01*x12*x20-x21*x02*x10,-x01*x13*x20+x21*x03*x10,
179: -x21*x03*x14+x23*x04*x11,-x22*x03*x14+x23*x04*x12,x01^2,x03^2,
180: -x00*x11+x01*x10,x10^2,x01*x11,-x01*x12+x02*x11,x01*x13-x03*x11,
181: x10*x11,x11^2,-x02*x13+x03*x12,-x11*x12,x12^2,x03*x13,-x03*x14+x04*x13,
182: x11*x13,-x12*x13,x13^2,x13*x14,x14^2,-x11*x20+x21*x10,x21*x11,
183: x21*x12-x22*x11,x21*x13-x23*x11,x21^2,x22*x13-x23*x12,-x23*x13,
184: -x23*x14+x24*x13,x23^2],
185: [x01,x03,x10,x11,x12,x13,x14,x21,x23]]
186: @end example
187:
188: @node noro_pd.prime_dec,,, 準素分解
189:
190: @subsection @code{noro_pd.prime_dec}
191: @findex noro_pd.prime_dec
192:
193: @table @t
194: @item noro_pd.syci_dec(@var{I},@var{vars}[|@var{options}])
195: イデアル @var{I} の根基の素イデアル分解を計算する.
196: @end table
197:
198: @table @var
199: @item return
200: リスト (成分の詳細は下で説明する)
201: @item I
202: 多項式リスト
203: @item vars
204: 変数リスト
205: @item options
206: 下の説明参照.
207: @end table
208:
209: @itemize @bullet
210: @item
211: デフォルトでは, @var{I} の根基の素イデアル分解の成分のリスト
212: @var{[P(1),P(2),...]} を返す.
213: @item
214: オプション @var{indep=1} が指定された場合, @var{[[P(1),Y(1)],[P(2),Y(2)],...]}
215: を返す. ここで, @var{Y(i)} は @var{P(i)} に対する極大独立集合である.
216: @item
217: オプション @var{radical=1} が指定された場合, 素イデアル成分のリスト @var{PL}
218: と, @var{I} の根基 @var{rad} のペアのリスト @var{[PL,rad]} が返される.
219: @end itemize
220:
221: @example
222: [1712] PD=noro_pd.prime_dec(B,V|radical=1)$
223: [1713] PD[0][0];
224: [x10,-x11,x12,x13,x14]
225: [1714] PD[1];
226: [-x03*x02*x01*x14*x20+x24*x02*x01*x00*x13,...,x23*x14-x24*x13]
227: @end example
228:
229:
230: @section 関連する関数
231:
232: @menu
233: * noro_pd.ideal_intersection::
234: * noro_pd.ideal_intersection_m::
235: * noro_pd.ideal_list_intersection::
236: * noro_pd.colon::
237: * noro_pd.ideal_colon::
238: * noro_pd.sat::
239: * noro_pd.ideal_sat::
240: * noro_pd.init_pprocs::
241: @end menu
242:
243: @node noro_pd.ideal_intersection,,, 関連する関数
244:
245: @subsection @code{noro_pd.ideal_intersection}
246: @findex noro_pd.ideal_intersection
247:
248: @table @t
249: @item noro_pd.ideal_intersection(@var{I1},@var{I2},@var{vars},@var{ord}[|@var{mod=p}])
250: イデアル @var{I1}, @var{I2} の共通部分を計算する.
251: @end table
252:
253: @table @var
254: @item return
255: 多項式リスト
256:
257: @item I
258: 多項式リスト
259: @item vars
260: 変数リスト
261: @item ord
262: 項順序
263: @end table
264:
265: @itemize @bullet
266: @item
267: 返されるリストは @var{I1} と @var{I2} の共通部分の @var{ord} に関するグレブナー
268: 基底になっている.
269: @item
270: デフォルトでは有理数体上で計算だが, オプション @var{mod=p} が指定された場合
271: @var{p}元体上での計算を行う.
272: @end itemize
273:
274: @example
275: [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]$
276: [1708] B=[a*d-j*c,b*c,d*e-f*g*h]$
277: [1709] V=[a,b,c,d,e,f,g,h,i,j,z]$
278: [1710] noro_pd.ideal_intersection(A,B,V,0);
279: [(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,
280: -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,
281: (-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,
282: 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]
283: @end example
284:
285: @node noro_pd.ideal_intersection_m,,, 関連する関数
286:
287: @subsection @code{noro_pd.ideal_intersection_m}
288: @findex noro_pd.ideal_intersection_m
289:
290: @table @t
291: @item noro_pd.ideal_intersection_m(@var{I1},@var{I2},@var{vars},@var{ord}[|@var{mod=p}])
292: イデアル @var{I1}, @var{I2} の共通部分を計算する.
293: @end table
294:
295: @table @var
296: @item return
297: 多項式リスト
298:
299: @item I
300: 多項式リスト
301: @item vars
302: 変数リスト
303: @item ord
304: 項順序
305: @end table
306:
307: @itemize @bullet
308: @var{I2} がグレブナー基底で, @var{I1} の生成系の個数が多い場合に
309: @code{noro_pd.ideal_intersection} より高速な場合がある.
310: @item
311: 返されるリストは共通部分の生成系だが
312: 必ずしも共通部分のグレブナー基底になってはいない.
313: @item
314: デフォルトでは有理数体上で計算だが, オプション @var{mod=p} が指定された場合
315: @var{p}元体上での計算を行う.
316: @end itemize
317:
318: @example
319: [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]
320: [1755] V=[b,c,d,e,f,g,h,i,j,z]
321: [1756] G=nd_gr(B,V,0,0)$
322: [1757] cputime(1)$
323: 0sec(1.907e-06sec)
324: [1758] I1=noro_pd.ideal_intersection(G,G,V,0)$
325: 0.316sec + gc : 0.012sec(0.3301sec)
326: [1759] I2=noro_pd.ideal_intersection_m(G,G,V,0)$
327: 0.064sec + gc : 0.012sec(0.07933sec)
328: @end example
329:
330: @node noro_pd.ideal_list_intersection,,, 関連する関数
331:
332: @subsection @code{noro_pd.ideal_list_intersection}
333: @findex noro_pd.ideal_list_intersection
334:
335: @table @t
336: @item noro_pd.ideal_intersection(@var{ilist},@var{vars},@var{ord}[|@var{mod=p}])
337: イデアルのリスト @var{ilist} の成分の共通部分を計算する.
338: @end table
339:
340: @table @var
341: @item return
342: 多項式リスト
343:
344: @item ilist
345: 多項式リストのリスト
346: @item vars
347: 変数リスト
348: @end table
349:
350: @itemize @bullet
351: @item
352: 返されるリストは共通部分のグレブナー基底になっている.
353: @item
354: デフォルトでは有理数体上で計算だが, オプション @var{mod=p} が指定された場合
355: @var{p}元体上での計算を行う.
356: @end itemize
357:
358: @example
359: [1709] PL=noro_pd.prime_dec(B,V|radical=1)$
360: [1710] Int=noro_pd.ideal_list_intersection(PL[0],V,0)$
361: [1711] gb_comp(Int,PL[1]);
362: 1
363: @end example
364:
365: @subsection @code{noro_pd.colon}
366: @findex noro_pd.colon
367:
368: @table @t
369: @item noro_pd.colon(@var{I},@var{f},@var{vars}[|@var{mod=p}])
370: @var{I:f} を計算する.
371: @end table
372:
373: @table @var
374: @item return
375: 多項式リスト
376:
377: @item I
378: 多項式リスト
379: @item f
380: 多項式
381: @item vars
382: 変数リスト
383: @end table
384:
385: @itemize @bullet
386: @item
387: 返されるリストは @var{I:f} のグレブナー基底とは限らない.
388: @item
389: デフォルトでは有理数体上で計算だが, オプション @var{mod=p} が指定された場合
390: @var{p}元体上での計算を行う.
391: @end itemize
392:
393: @example
394: [1640] B=[(x+y+z)^50,(x-y+z)^50]$
395: [1641] V=[x,y,z]$
396: [1642] noro_pd.colon(B,y^98,V);
397: [-x-z,-y]
398: @end example
399:
400: @subsection @code{noro_pd.ideal_colon}
401: @findex noro_pd.colon
402:
403: @table @t
404: @item noro_pd.colon(@var{I},@var{J},@var{vars}[|@var{mod=p}])
405: @var{I:J} を計算する.
406: @end table
407:
408: @table @var
409: @item return
410: 多項式リスト
411:
412: @item I
413: 多項式リスト
414: @item J
415: 多項式リスト
416: @item vars
417: 変数リスト
418: @end table
419:
420: @itemize @bullet
421: @item
422: 返されるリストは@var{I:J}のグレブナー基底になっている.
423: @item
424: デフォルトでは有理数体上で計算だが, オプション @var{mod=p} が指定された場合
425: @var{p}元体上での計算を行う.
426: @end itemize
427:
428: @example
429: [1640] B=[(x+y+z)^50,(x-y+z)^50]$
430: [1641] V=[x,y,z]$
431: [1642] noro_pd.ideal_colon(B,[(x+y+z)^49,(x-y+z)^49],V);
432: [-y^49*x-z*y^49,-y^50,-x^2-2*z*x+y^2-z^2]
433: @end example
434:
435: @subsection @code{noro_pd.sat}
436: @findex noro_pd.sat
437:
438: @table @t
439: @item noro_pd.sat(@var{I},@var{f},@var{vars}[|@var{mod=p}])
440: @var{I} の @var{f} による saturation を計算する.
441: @end table
442:
443: @table @var
444: @item return
445: 多項式リスト
446:
447: @item I
448: 多項式リスト
449: @item f
450: 多項式
451: @item vars
452: 変数リスト
453: @end table
454:
455: @itemize @bullet
456: @item
457: 返されるリストは@var{I:f}のグレブナー基底になっている.
458: @item
459: デフォルトでは有理数体上で計算だが, オプション @var{mod=p} が指定された場合
460: @var{p}元体上での計算を行う.
461: @end itemize
462:
463: @example
464: [1640] B=[(x+y+z)^50,(x-y+z)^50]$
465: [1641] V=[x,y,z]$
466: [1642] noro_pd.sat(B,y,V);
467: [1]
468: @end example
469:
470: @subsection @code{noro_pd.ideal_sat}
471: @findex noro_pd.ideal_sat
472:
473: @table @t
474: @item noro_pd.ideal_sat(@var{I},@var{J},@var{vars}[|@var{mod=p}])
475: @var{I:J} を計算する.
476: @end table
477:
478: @table @var
479: @item return
480: 多項式リスト
481:
482: @item I
483: 多項式リスト
484: @item J
485: 多項式リスト
486: @item vars
487: 変数リスト
488: @end table
489:
490: @itemize @bullet
491: @item
492: 返されるリストは@var{I:J}のグレブナー基底になっている.
493: @item
494: デフォルトでは有理数体上で計算だが, オプション @var{mod=p} が指定された場合
495: @var{p}元体上での計算を行う.
496: @end itemize
497:
498: @example
499: [1640] B=[(x+y+z)^50,(x-y+z)^50]$
500: [1641] V=[x,y,z]$
501: [1642] noro_pd.ideal_sat(B,[(x+y+z)^49,(x-y+z)^49],V);
502: [1]
503: @end example
504:
505: @subsection @code{noro_pd.init_pprocs}
506: @findex noro_pd.init_pprocs
507:
508: @table @t
509: @item noro_pd.init_pprocs(@var{m}[|@var{nox=1}])
510: 分散計算用プロセスを起動する.
511: @end table
512:
513: @table @var
514: @item return
515: 整数リスト
516:
517: @item m
518: 正整数
519: @end table
520:
521: @itemize @bullet
522: @item
523: 分散計算に用いるためのプロセス (@code{ox_asir})を起動し, その番号のリストを返す.
524: @item
525: ホームディレクトリの @samp{.asirrc} に @code{load("noro_pd.rr")$} を
526: 入れておくことで, @code{ox_asir} の起動時に @samp{noro_pd.rr} が
527: 読み込まれ, 分散計算の準備ができる.
528: @item
529: オプション @var{nox=1} が指定された場合, 起動されたプロセスからの
530: 画面出力のためのウィンドウが開かない.
531: @end itemize
532:
533: @example
534: [1544] P=noro_pd.init_pprocs(6|nox=1)$
535: [1545] B=[x00*x11-x01*x10,x01*x12-x02*x11,x02*x13-x03*x12,x03*x14-x04*x13,
536: x04*x15-x05*x14,x05*x16-x06*x15,x06*x17-x07*x16,-x11*x20+x21*x10,
537: -x21*x12+x22*x11,-x22*x13+x23*x12,-x23*x14+x24*x13,-x24*x15+x25*x14,
538: -x25*x16+x26*x15,-x26*x17+x27*x16]$
539: [1546] V=[x00,x01,x02,x03,x04,x05,x06,x07,x10,x11,x12,x13,x14,x15,x16,
540: x17,x20,x21,x22,x23,x24,x25,x26,x27]$
541: [1547] noro_pd.syci_dec(B,V|time=1)$
542: [total,205.581,ass,108.743,pd,31.582,iso,64.9081,int,11.7367,ext,96.8381]
543: [elapsed,206.177,ass,109.052,pd,31.679,iso,65.0682,int,11.7853,ext,97.1254]
544: [1548] noro_pd.syci_dec(B,V|time=1,para=P)$
545: [total,30.0339,ass,29.5498,pd,23.7695,iso,1.96412,int,3.32021,ext,0.48403]
546: [elapsed,79.0897,ass,62.5683,pd,26.0532,iso,28.037,int,7.97536,ext,16.5214]
547: @end example
548: @comment --- おまじない ---
549: @node Index,,, Top
550: @unnumbered Index
551: @printindex fn
552: @printindex cp
553: @iftex
554: @vfill @eject
555: @end iftex
556: @summarycontents
557: @contents
558: @bye
559: @comment --- おまじない終り ---
560:
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>