Annotation of OpenXM/src/asir-doc/parts/groebner.texi, Revision 1.25
1.25 ! noro 1: @comment $OpenXM: OpenXM/src/asir-doc/parts/groebner.texi,v 1.24 2020/09/01 09:25:32 noro Exp $
1.2 noro 2: \BJP
1.25 ! noro 3: @node グレブナ基底の計算,,, Top
! 4: @chapter グレブナ基底の計算
1.2 noro 5: \E
6: \BEG
7: @node Groebner basis computation,,, Top
8: @chapter Groebner basis computation
9: \E
1.1 noro 10:
11: @menu
1.2 noro 12: \BJP
1.25 ! noro 13: * 分散表現多項式::
! 14: * 基本的な函数::
! 15: * 計算および表示の制御::
! 16: * 項順序の設定::
1.13 noro 17: * Weight::
1.25 ! noro 18: * 有理式を係数とするグレブナ基底計算::
! 19: * 基底変換::
! 20: * Weyl 代数::
! 21: * 多項式環上の加群::
! 22: * グレブナ基底に関する函数::
1.2 noro 23: \E
24: \BEG
25: * Distributed polynomial::
26: * Reading files::
27: * Fundamental functions::
28: * Controlling Groebner basis computations::
29: * Setting term orderings::
1.13 noro 30: * Weight::
1.2 noro 31: * Groebner basis computation with rational function coefficients::
32: * Change of ordering::
1.5 noro 33: * Weyl algebra::
1.23 noro 34: * Module over a polynomial ring::
1.2 noro 35: * Functions for Groebner basis computation::
36: \E
1.1 noro 37: @end menu
38:
1.2 noro 39: \BJP
1.25 ! noro 40: @node 分散表現多項式,,, グレブナ基底の計算
! 41: @section 分散表現多項式
1.2 noro 42: \E
43: \BEG
44: @node Distributed polynomial,,, Groebner basis computation
45: @section Distributed polynomial
46: \E
1.1 noro 47:
48: @noindent
1.2 noro 49: \BJP
1.25 ! noro 50: 分散表現多項式とは, 多項式の内部形式の一つである. 通常の多項式
! 51: (@code{type} が 2) は, 再帰表現と呼ばれる形式で表現されている. すなわ
! 52: ち, 特定の変数を主変数とする 1 変数多項式で, その他の変数は, その 1 変
! 53: 数多項式の係数に, 主変数を含まない多項式として現れる. この係数が, また,
! 54: ある変数を主変数とする多項式となっていることから再帰表現と呼ばれる.
1.2 noro 55: \E
56: \BEG
57: A distributed polynomial is a polynomial with a special internal
58: representation different from the ordinary one.
59:
60: An ordinary polynomial (having @code{type} 2) is internally represented
61: in a format, called recursive representation.
62: In fact, it is represented as an uni-variate polynomial with respect to
63: a fixed variable, called main variable of that polynomial,
64: where the other variables appear in the coefficients which may again
65: polynomials in such variables other than the previous main variable.
66: A polynomial in the coefficients is again represented as
67: an uni-variate polynomial in a certain fixed variable,
68: the main variable. Thus, by this recursive structure of polynomial
69: representation, it is called the `recursive representation.'
70: \E
1.1 noro 71:
72: @iftex
73: @tex
1.2 noro 74: \JP $(x+y+z)^2 = 1 \cdot x^2 + (2 \cdot y + (2 \cdot z)) \cdot x + ((2 \cdot z) \cdot y + (1 \cdot z^2 ))$
75: \EG $(x+y+z)^2 = 1 \cdot x^2 + (2 \cdot y + (2 \cdot z)) \cdot x + ((2 \cdot z) \cdot y + (1 \cdot z^2 ))$
1.1 noro 76: @end tex
77: @end iftex
78: @ifinfo
79: @example
80: (x+y+z)^2 = 1 x^2 + (2 y + (2 z)) x + ((2 z) y + (1 z^2 ))
81: @end example
82: @end ifinfo
83:
84: @noindent
1.2 noro 85: \BJP
1.25 ! noro 86: これに対し, 多項式を, 変数の冪積と係数の積の和として表現したものを分散
! 87: 表現と呼ぶ.
1.2 noro 88: \E
89: \BEG
90: On the other hand,
91: we call a representation the distributed representation of a polynomial,
92: if a polynomial is represented, according to its original meaning,
93: as a sum of monomials,
94: where a monomial is the product of power product of variables
95: and a coefficient. We call a polynomial, represented in such an
96: internal format, a distributed polynomial. (This naming may sounds
97: something strange.)
98: \E
1.1 noro 99:
100: @iftex
101: @tex
1.2 noro 102: \JP $(x+y+z)^2 = 1 \cdot x^2 + 2 \cdot xy + 2 \cdot xz + 1 \cdot y^2 + 2 \cdot yz +1 \cdot z^2$
103: \EG $(x+y+z)^2 = 1 \cdot x^2 + 2 \cdot xy + 2 \cdot xz + 1 \cdot y^2 + 2 \cdot yz +1 \cdot z^2$
1.1 noro 104: @end tex
105: @end iftex
106: @ifinfo
107: @example
108: (x+y+z)^2 = 1 x^2 + 2 xy + 2 xz + 1 y^2 + 2 yz +1 z^2$
109: @end example
110: @end ifinfo
111:
112: @noindent
1.2 noro 113: \BJP
1.25 ! noro 114: グレブナ基底計算においては, 単項式に注目して操作を行うため多項式が分散表現
! 115: されている方がより効率のよい演算が可能になる. このため, 分散表現多項式が,
! 116: 識別子 9 の型として @b{Asir} のトップレベルから利用可能となっている.
! 117: ここで, 後の説明のために, いくつかの言葉を定義しておく.
1.2 noro 118: \E
119: \BEG
120: For computation of Groebner basis, efficient operation is expected if
121: polynomials are represented in a distributed representation,
122: because major operations for Groebner basis are performed with respect
123: to monomials.
124: From this view point, we provide the object type distributed polynomial
125: with its object identification number 9, and objects having such a type
126: are available by @b{Asir} language.
127:
128: Here, we provide several definitions for the later description.
129: \E
1.1 noro 130:
131: @table @b
1.2 noro 132: \BJP
1.25 ! noro 133: @item 項 (term)
! 134: 変数の冪積. すなわち, 係数 1 の単項式のこと. @b{Asir} においては,
1.2 noro 135: \E
136: \BEG
137: @item term
138: The power product of variables, i.e., a monomial with coefficient 1.
139: In an @b{Asir} session, it is displayed in the form like
140: \E
1.1 noro 141:
142: @example
143: <<0,1,2,3,4>>
144: @end example
145:
1.2 noro 146: \BJP
1.25 ! noro 147: という形で表示され, また, この形で入力可能である. この例は, 5 変数の項
! 148: を示す. 各変数を @code{a}, @code{b}, @code{c}, @code{d}, @code{e} とすると
! 149: この項は @code{b*c^2*d^3*e^4} を表す.
1.2 noro 150: \E
151: \BEG
152: and also can be input in such a form.
153: This example shows a term in 5 variables. If we assume the 5 variables
154: as @code{a}, @code{b}, @code{c}, @code{d}, and @code{e},
155: the term represents @code{b*c^2*d^3*e^4} in the ordinary expression.
156: \E
1.1 noro 157:
1.2 noro 158: \BJP
1.25 ! noro 159: @item 項順序 (term order)
! 160: 分散表現多項式における項は, 次の性質を満たす全順序により整列される.
1.2 noro 161: \E
162: \BEG
163: @item term order
164: Terms are ordered according to a total order with the following properties.
165: \E
1.1 noro 166:
167: @enumerate
168: @item
1.25 ! noro 169: \JP 任意の項 @code{t} に対し @code{t} > 1
1.2 noro 170: \EG For all @code{t} @code{t} > 1.
1.1 noro 171:
172: @item
1.25 ! noro 173: \JP @code{t}, @code{s}, @code{u} を項とする時, @code{t} > @code{s} ならば @code{tu} > @code{su}
1.2 noro 174: \EG For all @code{t}, @code{s}, @code{u} @code{t} > @code{s} implies @code{tu} > @code{su}.
1.1 noro 175: @end enumerate
176:
1.2 noro 177: \BJP
1.25 ! noro 178: この性質を満たす全順序を項順序と呼ぶ. この順序は変数順序 (変数のリスト)
! 179: と項順序型 (数, リストまたは行列) により指定される.
1.2 noro 180: \E
181: \BEG
182: Such a total order is called a term ordering. A term ordering is specified
183: by a variable ordering (a list of variables) and a type of term ordering
184: (an integer, a list or a matrix).
185: \E
1.1 noro 186:
1.2 noro 187: \BJP
1.25 ! noro 188: @item 単項式 (monomial)
! 189: 項と係数の積.
1.2 noro 190: \E
191: \BEG
192: @item monomial
193: The product of a term and a coefficient.
194: In an @b{Asir} session, it is displayed in the form like
195: \E
1.1 noro 196:
197: @example
198: 2*<<0,1,2,3,4>>
199: @end example
200:
1.25 ! noro 201: \JP という形で表示され, また, この形で入力可能である.
1.2 noro 202: \EG and also can be input in such a form.
1.1 noro 203:
1.2 noro 204: \BJP
1.25 ! noro 205: @item 頭項 (head term)
! 206: @itemx 頭単項式 (head monomial)
! 207: @itemx 頭係数 (head coefficient)
! 208: 分散表現多項式における各単項式は, 項順序により整列される. この時順
! 209: 序最大の単項式を頭単項式, それに現れる項, 係数をそれぞれ頭項, 頭係数
! 210: と呼ぶ.
1.2 noro 211: \E
212: \BEG
1.19 noro 213: @item head term
1.2 noro 214: @itemx head monomial
215: @itemx head coefficient
216:
217: Monomials in a distributed polynomial is sorted by a total order.
218: In such representation, we call the monomial that is maximum
219: with respect to the order the head monomial, and its term and coefficient
220: the head term and the head coefficient respectively.
221: \E
1.1 noro 222: @end table
223:
1.20 takayama 224: @noindent
225: ChangeLog
226: @itemize @bullet
227: \BJP
1.25 ! noro 228: @item 分散表現多項式は任意のオブジェクトを係数にもてるようになった.
! 229: また加群のk成分の要素を次の形式 <<d0,d1,...:k>> で表現するようになった (2017-08-31).
1.20 takayama 230: \E
231: \BEG
232: @item Distributed polynomials accept objects as coefficients.
233: The k-th element of a free module is expressed as <<d0,d1,...:k>> (2017-08-31).
234: \E
235: @item
236: 1.15 algnum.c,
237: 1.53 ctrl.c,
238: 1.66 dp-supp.c,
239: 1.105 dp.c,
240: 1.73 gr.c,
241: 1.4 reduct.c,
242: 1.16 _distm.c,
243: 1.17 dalg.c,
244: 1.52 dist.c,
245: 1.20 distm.c,
246: 1.8 gmpq.c,
247: 1.238 engine/nd.c,
248: 1.102 ca.h,
249: 1.411 version.h,
250: 1.28 cpexpr.c,
251: 1.42 pexpr.c,
252: 1.20 pexpr_body.c,
253: 1.40 spexpr.c,
254: 1.27 arith.c,
255: 1.77 eval.c,
256: 1.56 parse.h,
257: 1.37 parse.y,
258: 1.8 stdio.c,
259: 1.31 plotf.c
260: @end itemize
261:
1.2 noro 262: \BJP
1.25 ! noro 263: @node 基本的な函数,,, グレブナ基底の計算
! 264: @section 基本的な函数
1.2 noro 265: \E
266: \BEG
1.25 ! noro 267: @node Fundamental functions,,, Groebner basis computation
! 268: @section Fundamental functions
1.2 noro 269: \E
1.1 noro 270:
271: @noindent
1.2 noro 272: \BJP
1.25 ! noro 273: 2003 年以前の版においては, グレブナ基底を計算するための基本的な函数は @code{dp_gr_main()} および
1.5 noro 274: @code{dp_gr_mod_main()}, @code{dp_gr_f_main()}
1.25 ! noro 275: なる 3 つの組み込み函数であった. 通常は, パラメタ
! 276: 設定などを行ったのちこれらを呼び出すユーザ函数を用いるのが便利である.
! 277: これらのユーザ函数は, ファイル @samp{gr} を @code{load()} により読
! 278: み込むことにより使用可能となる. @samp{gr} は, @b{Asir} の標準
! 279: ライブラリディレクトリに置かれている.
! 280: @example
! 281: [0] load("gr")$
! 282: @end example
! 283:
! 284:
! 285: 現在の版においては, @code{nd_gr}, @code{nd_f4} などの新しい関数が実装されており,
! 286: 一般にこちらの方が効率よくグレブナー基底が計算できる
! 287: (@fref{nd_gr nd_gr_trace nd_f4 nd_f4_trace nd_weyl_gr nd_weyl_gr_trace}).
1.2 noro 288: \E
289: \BEG
1.25 ! noro 290: In the vesion before 2003,
! 291: facilities for computing Groebner bases are
1.5 noro 292: @code{dp_gr_main()}, @code{dp_gr_mod_main()}and @code{dp_gr_f_main()}.
293: To call these functions,
294: it is necessary to set several parameters correctly and it is convenient
295: to use a set of interface functions provided in the library file
296: @samp{gr}.
1.2 noro 297: The facilities will be ready to use after you load the package by
298: @code{load()}. The package @samp{gr} is placed in the standard library
1.5 noro 299: directory of @b{Asir}.
1.1 noro 300:
1.25 ! noro 301: In the current vesion, new functions such as @code{nd_gr}, @code{nd_f4} are available
! 302: and these function can compute Groebner bases more efficiently than old functions
! 303: (@fref{nd_gr nd_gr_trace nd_f4 nd_f4_trace nd_weyl_gr nd_weyl_gr_trace}).
1.2 noro 304: \E
1.1 noro 305:
306: @noindent
1.2 noro 307: \BJP
1.25 ! noro 308: 2003 年以前の版において
! 309: グレブナ基底を計算するためのトップレベルは次の 3 つである.
! 310: 以下で, @var{plist} は多項式のリスト, @var{vlist} は変数 (不定元) のリスト,
! 311: @var{order} は変数順序型, @var{p} は @code{2^27} 未満の素数である.
1.2 noro 312: \E
313: \BEG
314: There are many functions and options defined in the package @samp{gr}.
315: Usually not so many of them are used. Top level functions for Groebner
316: basis computation are the following three functions.
317:
318: In the following description, @var{plist}, @var{vlist}, @var{order}
319: and @var{p} stand for a list of polynomials, a list of variables
320: (indeterminates), a type of term ordering and a prime less than
321: @code{2^27} respectively.
322: \E
1.1 noro 323:
324: @table @code
325: @item gr(@var{plist},@var{vlist},@var{order})
326:
1.2 noro 327: \BJP
1.25 ! noro 328: Gebauer-Moeller による useless pair elimination criteria, sugar
! 329: strategy および Traverso による trace-lifting を用いた Buchberger アル
! 330: ゴリズムによる有理数係数グレブナ基底計算函数. 一般にはこの函数を用いる.
1.2 noro 331: \E
332: \BEG
333: Function that computes Groebner bases over the rationals. The
334: algorithm is Buchberger algorithm with useless pair elimination
335: criteria by Gebauer-Moeller, sugar strategy and trace-lifting by
336: Traverso. For ordinary computation, this function is used.
337: \E
1.1 noro 338:
339: @item hgr(@var{plist},@var{vlist},@var{order})
340:
1.2 noro 341: \BJP
1.25 ! noro 342: 入力多項式を斉次化した後 @code{gr()} のグレブナ基底候補生成部により候
! 343: 補生成し, 非斉次化, interreduce したものを @code{gr()} のグレブナ基底
! 344: チェック部でチェックする. 0 次元システム (解の個数が有限個の方程式系)
! 345: の場合, sugar strategy が係数膨張を引き起こす場合がある. このような場
! 346: 合, strategy を斉次化による strategy に置き換えることにより係数膨張を
! 347: 抑制することができる場合が多い.
1.2 noro 348: \E
349: \BEG
350: After homogenizing the input polynomials a candidate of the \gr basis
351: is computed by trace-lifting. Then the candidate is dehomogenized and
352: checked whether it is indeed a Groebner basis of the input. Sugar
353: strategy often causes intermediate coefficient swells. It is
354: empirically known that the combination of homogenization and supresses
355: the swells for such cases.
356: \E
1.1 noro 357:
358: @item gr_mod(@var{plist},@var{vlist},@var{order},@var{p})
359:
1.2 noro 360: \BJP
1.25 ! noro 361: Gebauer-Moeller による useless pair elimination criteria, sugar
! 362: strategy および Buchberger アルゴリズムによる GF(p) 係数グレブナ基底計
! 363: 算函数.
1.2 noro 364: \E
365: \BEG
366: Function that computes Groebner bases over GF(@var{p}). The same
367: algorithm as @code{gr()} is used.
368: \E
1.25 ! noro 369: @end table
1.1 noro 370:
1.25 ! noro 371: \BJP
! 372: 現在の版においては, これらに相当する機能は @code{nd_gr}, @code{nd_gr_trace} にまとめられている.
! 373: 詳しくは @fref{nd_gr nd_gr_trace nd_f4 nd_f4_trace nd_weyl_gr nd_weyl_gr_trace} 参照.
! 374: \E
! 375: \BEG
! 376: In the current version, the functions corresponding to these three interfaces are provided
! 377: by @code{nd_gr}, @code{nd_gr_trace}.
! 378: See @fref{nd_gr nd_gr_trace nd_f4 nd_f4_trace nd_weyl_gr nd_weyl_gr_trace}.
! 379: \E
1.1 noro 380:
1.2 noro 381: \BJP
1.25 ! noro 382: @node 計算および表示の制御,,, グレブナ基底の計算
! 383: @section 計算および表示の制御
1.2 noro 384: \E
385: \BEG
386: @node Controlling Groebner basis computations,,, Groebner basis computation
387: @section Controlling Groebner basis computations
388: \E
1.1 noro 389:
390: @noindent
1.2 noro 391: \BJP
1.25 ! noro 392: グレブナ基底の計算において, さまざまなパラメタ設定を行うことにより計算,
! 393: 表示を制御することができる. これらは, 組み込み函数 @code{dp_gr_flags()}
! 394: により設定参照することができる. 無引数で @code{dp_gr_flags()} を実行する
! 395: と, 現在設定されているパラメタが, 名前と値のリストで返される.
1.2 noro 396: \E
397: \BEG
398: One can cotrol a Groebner basis computation by setting various parameters.
399: These parameters can be set and examined by a built-in function
400: @code{dp_gr_flags()}. Without argument it returns the current settings.
401: \E
1.1 noro 402:
403: @example
404: [100] dp_gr_flags();
1.5 noro 405: [Demand,0,NoSugar,0,NoCriB,0,NoGC,0,NoMC,0,NoRA,0,NoGCD,0,Top,0,
406: ShowMag,1,Print,1,Stat,0,Reverse,0,InterReduce,0,Multiple,0]
1.1 noro 407: [101]
408: @end example
409:
1.2 noro 410: \BJP
1.25 ! noro 411: 以下で, 各パラメタの意味を説明する. on の場合とは, パラメタが 0 でない場合を
! 412: いう. これらのパラメタの初期値は全て 0 (off) である.
1.2 noro 413: \E
414: \BEG
415: The return value is a list which contains the names of parameters and their
416: values. The meaning of the parameters are as follows. `on' means that the
417: parameter is not zero.
418: \E
1.1 noro 419:
420: @table @code
421: @item NoSugar
1.2 noro 422: \BJP
1.25 ! noro 423: on の場合, sugar strategy の代わりに Buchbergerの normal strategy が用
! 424: いられる.
1.2 noro 425: \E
426: \BEG
427: If `on', Buchberger's normal strategy is used instead of sugar strategy.
428: \E
1.1 noro 429:
430: @item NoCriB
1.25 ! noro 431: \JP on の場合, 不必要対検出規準のうち, 規準 B を適用しない.
1.2 noro 432: \EG If `on', criterion B among the Gebauer-Moeller's criteria is not applied.
1.1 noro 433:
434: @item NoGC
1.25 ! noro 435: \JP on の場合, 結果がグレブナ基底になっているかどうかのチェックを行わない.
1.2 noro 436: \BEG
437: If `on', the check that a Groebner basis candidate is indeed a Groebner basis,
438: is not executed.
439: \E
1.1 noro 440:
441: @item NoMC
1.2 noro 442: \BJP
1.25 ! noro 443: on の場合, 結果が入力イデアルと同等のイデアルであるかどうかのチェック
! 444: を行わない.
1.2 noro 445: \E
446: \BEG
447: If `on', the check that the resulting polynomials generates the same ideal as
448: the ideal generated by the input, is not executed.
449: \E
1.1 noro 450:
451: @item NoRA
1.2 noro 452: \BJP
1.25 ! noro 453: on の場合, 結果を reduced グレブナ基底にするための
! 454: interreduce を行わない.
1.2 noro 455: \E
456: \BEG
457: If `on', the interreduction, which makes the Groebner basis reduced, is not
458: executed.
459: \E
1.1 noro 460:
461: @item NoGCD
1.2 noro 462: \BJP
1.25 ! noro 463: on の場合, 有理式係数のグレブナ基底計算において, 生成された多項式の,
! 464: 係数の content をとらない.
1.2 noro 465: \E
466: \BEG
467: If `on', content removals are not executed during a Groebner basis computation
468: over a rational function field.
469: \E
1.1 noro 470:
471: @item Top
1.25 ! noro 472: \JP on の場合, normal form 計算において頭項消去のみを行う.
1.2 noro 473: \EG If `on', Only the head term of the polynomial being reduced is reduced.
1.1 noro 474:
1.2 noro 475: @comment @item Interreduce
476: @comment \BJP
1.25 ! noro 477: @comment on の場合, 多項式を生成する毎に, それまで生成された基底をその多項式に
! 478: @comment よる normal form で置き換える.
1.2 noro 479: @comment \E
480: @comment \BEG
481: @comment If `on', intermediate basis elements are reduced by using a newly generated
482: @comment basis element.
483: @comment \E
1.1 noro 484:
485: @item Reverse
1.2 noro 486: \BJP
1.25 ! noro 487: on の場合, normal form 計算の際の reducer を, 新しく生成されたものを優
! 488: 先して選ぶ.
1.2 noro 489: \E
490: \BEG
491: If `on', the selection strategy of reducer in a normal form computation
492: is such that a newer reducer is used first.
493: \E
1.1 noro 494:
495: @item Print
1.25 ! noro 496: \JP on の場合, グレブナ基底計算の途中におけるさまざまな情報を表示する.
1.2 noro 497: \BEG
498: If `on', various informations during a Groebner basis computation is
499: displayed.
500: \E
1.1 noro 501:
1.7 noro 502: @item PrintShort
1.25 ! noro 503: \JP on で、Print が off の場合, グレブナ基底計算の途中の情報を短縮形で表示する.
1.7 noro 504: \BEG
505: If `on' and Print is `off', short information during a Groebner basis computation is
506: displayed.
507: \E
508:
1.1 noro 509: @item Stat
1.2 noro 510: \BJP
1.25 ! noro 511: on で @code{Print} が off ならば, @code{Print} が on のとき表示さ
! 512: れるデータの内, 集計データのみが表示される.
1.2 noro 513: \E
514: \BEG
515: If `on', a summary of informations is shown after a Groebner basis
516: computation. Note that the summary is always shown if @code{Print} is `on'.
517: \E
1.1 noro 518:
519: @item ShowMag
1.2 noro 520: \BJP
1.25 ! noro 521: on で @code{Print} が on ならば, 生成が生成される毎に, その多項式の
! 522: 係数のビット長の和を表示し, 最後に, それらの和の最大値を表示する.
1.2 noro 523: \E
524: \BEG
525: If `on' and @code{Print} is `on', the sum of bit length of
526: coefficients of a generated basis element, which we call @var{magnitude},
527: is shown after every normal computation. After comleting the
528: computation the maximal value among the sums is shown.
529: \E
1.1 noro 530:
1.7 noro 531: @item Content
532: @itemx Multiple
1.2 noro 533: \BJP
1.25 ! noro 534: 0 でない有理数の時, 有理数上の正規形計算において, 係数のビット長の和が
! 535: @code{Content} 倍になるごとに係数全体の GCD が計算され, その GCD で
! 536: 割った多項式を簡約する. @code{Content} が 1 ならば, 簡約するごとに
! 537: GCD 計算が行われ一般には効率が悪くなるが, @code{Content} を 2 程度
! 538: とすると, 巨大な整数が係数に現れる場合, 効率が良くなる場合がある.
! 539: backward compatibility のため、@code{Multiple} で整数値を指定できる.
1.2 noro 540: \E
541: \BEG
1.7 noro 542: If a non-zero rational number, in a normal form computation
1.2 noro 543: over the rationals, the integer content of the polynomial being
1.7 noro 544: reduced is removed when its magnitude becomes @code{Content} times
1.2 noro 545: larger than a registered value, which is set to the magnitude of the
546: input polynomial. After each content removal the registered value is
1.7 noro 547: set to the magnitude of the resulting polynomial. @code{Content} is
1.2 noro 548: equal to 1, the simiplification is done after every normal form computation.
1.7 noro 549: It is empirically known that it is often efficient to set @code{Content} to 2
1.2 noro 550: for the case where large integers appear during the computation.
1.7 noro 551: An integer value can be set by the keyword @code{Multiple} for
552: backward compatibility.
1.2 noro 553: \E
1.1 noro 554:
555: @item Demand
1.2 noro 556:
557: \BJP
1.25 ! noro 558: 正当なディレクトリ名 (文字列) を値に持つとき, 生成された多項式はメモリ
! 559: 中におかれず, そのディレクトリ中にバイナリデータとして置かれ, その多項
! 560: 式を用いる normal form 計算の際, 自動的にメモリ中にロードされる. 各多
! 561: 項式は, 内部でのインデックスをファイル名に持つファイルに格納される.
! 562: ここで指定されたディレクトリに書かれたファイルは自動的には消去されない
! 563: ため, ユーザが責任を持って消去する必要がある.
1.2 noro 564: \E
565: \BEG
566: If the value (a character string) is a valid directory name, then
567: generated basis elements are put in the directory and are loaded on
568: demand during normal form computations. Each elements is saved in the
569: binary form and its name coincides with the index internally used in
570: the computation. These binary files are not removed automatically
571: and one should remove them by hand.
572: \E
1.1 noro 573: @end table
574:
575: @noindent
1.25 ! noro 576: \JP @code{Print} が 0 でない場合次のようなデータが表示される.
1.2 noro 577: \EG If @code{Print} is `on', the following informations are shown.
1.1 noro 578:
579: @example
580: [93] gr(cyclic(4),[c0,c1,c2,c3],0)$
581: mod= 99999989, eval = []
582: (0)(0)<<0,2,0,0>>(2,3),nb=2,nab=5,rp=2,sugar=2,mag=4
583: (0)(0)<<0,1,2,0>>(1,2),nb=3,nab=6,rp=2,sugar=3,mag=4
584: (0)(0)<<0,1,1,2>>(0,1),nb=4,nab=7,rp=3,sugar=4,mag=6
585: .
586: (0)(0)<<0,0,3,2>>(5,6),nb=5,nab=8,rp=2,sugar=5,mag=4
587: (0)(0)<<0,1,0,4>>(4,6),nb=6,nab=9,rp=3,sugar=5,mag=4
588: (0)(0)<<0,0,2,4>>(6,8),nb=7,nab=10,rp=4,sugar=6,mag=6
589: ....gb done
590: reduceall
591: .......
592: membercheck
593: (0,0)(0,0)(0,0)(0,0)
594: gbcheck total 8 pairs
595: ........
1.5 noro 596: UP=(0,0)SP=(0,0)SPM=(0,0)NF=(0,0)NFM=(0.010002,0)ZNFM=(0.010002,0)
597: PZ=(0,0)NP=(0,0)MP=(0,0)RA=(0,0)MC=(0,0)GC=(0,0)T=40,B=0 M=8 F=6
598: D=12 ZR=5 NZR=6 Max_mag=6
1.1 noro 599: [94]
600: @end example
601:
602: @noindent
1.2 noro 603: \BJP
1.25 ! noro 604: 最初に表示される @code{mod}, @code{eval} は, trace-lifting で用いられる法
! 605: である. @code{mod} は素数, @code{eval} は有理式係数の場合に用いられる
! 606: 数のリストである.
1.2 noro 607: \E
608: \BEG
609: In this example @code{mod} and @code{eval} indicate moduli used in
610: trace-lifting. @code{mod} is a prime and @code{eval} is a list of integers
611: used for evaluation when the ground field is a field of rational functions.
612: \E
1.1 noro 613:
614: @noindent
1.25 ! noro 615: \JP 計算途中で多項式が生成される毎に次の形のデータが表示される.
1.2 noro 616: \EG The following information is shown after every normal form computation.
1.1 noro 617:
618: @example
619: (TNF)(TCONT)HT(INDEX),nb=NB,nab=NAB,rp=RP,sugar=S,mag=M
620: @end example
621:
622: @noindent
1.25 ! noro 623: \JP それらの意味は次の通り.
1.2 noro 624: \EG Meaning of each component is as follows.
1.1 noro 625:
626: @table @code
1.2 noro 627: \BJP
1.1 noro 628: @item TNF
1.2 noro 629:
1.25 ! noro 630: normal form 計算時間 (秒)
1.1 noro 631:
632: @item TCONT
1.2 noro 633:
1.25 ! noro 634: content 計算時間 (秒)
1.1 noro 635:
636: @item HT
1.2 noro 637:
1.25 ! noro 638: 生成された多項式の頭項
1.1 noro 639:
640: @item INDEX
1.2 noro 641:
1.25 ! noro 642: S-多項式を構成する多項式のインデックスのペア
1.1 noro 643:
644: @item NB
1.2 noro 645:
1.25 ! noro 646: 現在の, 冗長性を除いた基底の数
1.1 noro 647:
648: @item NAB
1.2 noro 649:
1.25 ! noro 650: 現在までに生成された基底の数
1.1 noro 651:
652: @item RP
1.2 noro 653:
1.25 ! noro 654: 残りのペアの数
1.1 noro 655:
656: @item S
1.2 noro 657:
1.25 ! noro 658: 生成された多項式の sugar の値
1.1 noro 659:
660: @item M
1.2 noro 661:
1.25 ! noro 662: 生成された多項式の係数のビット長の和 (@code{ShowMag} が on の時に表示される. )
1.2 noro 663: \E
664: \BEG
665: @item TNF
666:
667: CPU time for normal form computation (second)
668:
669: @item TCONT
670:
671: CPU time for content removal(second)
672:
673: @item HT
674:
675: Head term of the generated basis element
676:
677: @item INDEX
678:
679: Pair of indices which corresponds to the reduced S-polynomial
680:
681: @item NB
682:
683: Number of basis elements after removing redundancy
684:
685: @item NAB
686:
687: Number of all the basis elements
688:
689: @item RP
690:
691: Number of remaining pairs
692:
693: @item S
694:
695: Sugar of the generated basis element
696:
697: @item M
698:
699: Magnitude of the genrated basis element (shown if @code{ShowMag} is `on'.)
700: \E
1.1 noro 701: @end table
702:
703: @noindent
1.2 noro 704: \BJP
1.25 ! noro 705: 最後に, 集計データが表示される. 意味は次の通り.
! 706: (時間の表示において, 数字が 2 つあるものは, 計算時間と GC 時間のペアである.)
1.2 noro 707: \E
708: \BEG
709: The summary of the informations shown after a Groebner basis
710: computation is as follows. If a component shows timings and it
711: contains two numbers, they are a pair of time for computation and time
712: for garbage colection.
713: \E
1.1 noro 714:
715: @table @code
1.2 noro 716: \BJP
1.1 noro 717: @item UP
1.2 noro 718:
1.25 ! noro 719: ペアのリストの操作にかかった時間
1.1 noro 720:
721: @item SP
1.2 noro 722:
1.25 ! noro 723: 有理数上の S-多項式計算時間
1.1 noro 724:
725: @item SPM
1.2 noro 726:
1.25 ! noro 727: 有限体上の S-多項式計算時間
1.1 noro 728:
729: @item NF
1.2 noro 730:
1.25 ! noro 731: 有理数上の normal form 計算時間
1.1 noro 732:
733: @item NFM
1.2 noro 734:
1.25 ! noro 735: 有限体上の normal form 計算時間
1.1 noro 736:
737: @item ZNFM
1.2 noro 738:
1.25 ! noro 739: @code{NFM} の内, 0 への reduction にかかった時間
1.1 noro 740:
741: @item PZ
1.2 noro 742:
1.25 ! noro 743: content 計算時間
1.1 noro 744:
745: @item NP
1.2 noro 746:
1.25 ! noro 747: 有理数係数多項式の係数に対する剰余演算の計算時間
1.1 noro 748:
749: @item MP
1.2 noro 750:
1.25 ! noro 751: S-多項式を生成するペアの選択にかかった時間
1.1 noro 752:
753: @item RA
1.2 noro 754:
1.25 ! noro 755: interreduce 計算時間
1.1 noro 756:
757: @item MC
1.2 noro 758:
1.25 ! noro 759: trace-lifting における, 入力多項式のメンバシップ計算時間
1.1 noro 760:
761: @item GC
1.2 noro 762:
1.25 ! noro 763: 結果のグレブナ基底候補のグレブナ基底チェック時間
1.1 noro 764:
765: @item T
1.2 noro 766:
1.25 ! noro 767: 生成されたペアの数
1.1 noro 768:
769: @item B, M, F, D
1.2 noro 770:
1.25 ! noro 771: 各 criterion により除かれたペアの数
1.1 noro 772:
773: @item ZR
1.2 noro 774:
1.25 ! noro 775: 0 に reduce されたペアの数
1.1 noro 776:
777: @item NZR
1.2 noro 778:
1.25 ! noro 779: 0 でない多項式に reduce されたペアの数
1.1 noro 780:
781: @item Max_mag
1.2 noro 782:
1.25 ! noro 783: 生成された多項式の, 係数のビット長の和の最大値
1.2 noro 784: \E
785: \BEG
786: @item UP
787:
788: Time to manipulate the list of critical pairs
789:
790: @item SP
791:
792: Time to compute S-polynomials over the rationals
793:
794: @item SPM
795:
796: Time to compute S-polynomials over a finite field
797:
798: @item NF
799:
800: Time to compute normal forms over the rationals
801:
802: @item NFM
803:
804: Time to compute normal forms over a finite field
805:
806: @item ZNFM
807:
808: Time for zero reductions in @code{NFM}
809:
810: @item PZ
811:
812: Time to remove integer contets
813:
814: @item NP
815:
816: Time to compute remainders for coefficients of polynomials with coeffieints
817: in the rationals
818:
819: @item MP
820:
821: Time to select pairs from which S-polynomials are computed
822:
823: @item RA
824:
825: Time to interreduce the Groebner basis candidate
826:
827: @item MC
1.1 noro 828:
1.2 noro 829: Time to check that each input polynomial is a member of the ideal
830: generated by the Groebner basis candidate.
831:
832: @item GC
833:
834: Time to check that the Groebner basis candidate is a Groebner basis
835:
836: @item T
837:
838: Number of critical pairs generated
839:
840: @item B, M, F, D
841:
842: Number of critical pairs removed by using each criterion
843:
844: @item ZR
845:
846: Number of S-polynomials reduced to 0
847:
848: @item NZR
849:
850: Number of S-polynomials reduced to non-zero results
851:
852: @item Max_mag
853:
854: Maximal magnitude among all the generated polynomials
855: \E
1.1 noro 856: @end table
857:
1.2 noro 858: \BJP
1.25 ! noro 859: @node 項順序の設定,,, グレブナ基底の計算
! 860: @section 項順序の設定
1.2 noro 861: \E
862: \BEG
863: @node Setting term orderings,,, Groebner basis computation
864: @section Setting term orderings
865: \E
1.1 noro 866:
867: @noindent
1.2 noro 868: \BJP
1.25 ! noro 869: 項は内部では, 各変数に関する指数を成分とする整数ベクトルとして表現され
! 870: る. 多項式を分散表現多項式に変換する際, 各変数がどの成分に対応するかを
! 871: 指定するのが, 変数リストである. さらに, それら整数ベクトルの全順序を
! 872: 指定するのが項順序の型である. 項順序型は, 数, 数のリストあるいは
! 873: 行列で表現される.
1.2 noro 874: \E
875: \BEG
876: A term is internally represented as an integer vector whose components
877: are exponents with respect to variables. A variable list specifies the
878: correspondences between variables and components. A type of term ordering
879: specifies a total order for integer vectors. A type of term ordering is
880: represented by an integer, a list of integer or matrices.
881: \E
1.1 noro 882:
883: @noindent
1.25 ! noro 884: \JP 基本的な項順序型として次の 3 つがある.
1.2 noro 885: \EG There are following three fundamental types.
1.1 noro 886:
887: @table @code
1.25 ! noro 888: \JP @item 0 (DegRevLex; @b{全次数逆辞書式順序})
1.2 noro 889: \EG @item 0 (DegRevLex; @b{total degree reverse lexicographic ordering})
1.1 noro 890:
1.2 noro 891: \BJP
1.25 ! noro 892: 一般に, この順序によるグレブナ基底計算が最も高速である. ただし,
! 893: 方程式を解くという目的に用いることは, 一般にはできない. この
! 894: 順序によるグレブナ基底は, 解の個数の計算, イデアルのメンバシップや,
! 895: 他の変数順序への基底変換のためのソースとして用いられる.
1.2 noro 896: \E
897: \BEG
898: In general, computation by this ordering shows the fastest speed
899: in most Groebner basis computations.
900: However, for the purpose to solve polynomial equations, this type
901: of ordering is, in general, not so suitable.
902: The Groebner bases obtained by this ordering is used for computing
903: the number of solutions, solving ideal membership problem and seeds
904: for conversion to other Groebner bases under different ordering.
905: \E
1.1 noro 906:
1.25 ! noro 907: \JP @item 1 (DegLex; @b{全次数辞書式順序})
1.2 noro 908: \EG @item 1 (DegLex; @b{total degree lexicographic ordering})
1.1 noro 909:
1.2 noro 910: \BJP
1.25 ! noro 911: この順序も, 辞書式順序に比べて高速にグレブナ基底を求めることができるが,
! 912: @code{DegRevLex} と同様直接その結果を用いることは困難である. しかし,
! 913: 辞書式順序のグレブナ基底を求める際に, 斉次化後にこの順序でグレブナ基底
! 914: を求めている.
1.2 noro 915: \E
916: \BEG
917: By this type term ordering, Groebner bases are obtained fairly faster
918: than Lex (lexicographic) ordering, too.
919: Alike the @code{DegRevLex} ordering, the result, in general, cannot directly
920: be used for solving polynomial equations.
921: It is used, however, in such a way
922: that a Groebner basis is computed in this ordering after homogenization
923: to obtain the final lexicographic Groebner basis.
924: \E
1.1 noro 925:
1.25 ! noro 926: \JP @item 2 (Lex; @b{辞書式順序})
1.2 noro 927: \EG @item 2 (Lex; @b{lexicographic ordering})
1.1 noro 928:
1.2 noro 929: \BJP
1.25 ! noro 930: この順序によるグレブナ基底は, 方程式を解く場合に最適の形の基底を与えるが
! 931: 計算時間がかかり過ぎるのが難点である. 特に, 解が有限個の場合, 結果の
! 932: 係数が極めて長大な多倍長数になる場合が多い. この場合, @code{gr()},
! 933: @code{hgr()} による計算が極めて有効になる場合が多い.
1.2 noro 934: \E
935: \BEG
936: Groebner bases computed by this ordering give the most convenient
937: Groebner bases for solving the polynomial equations.
938: The only and serious shortcoming is the enormously long computation
939: time.
940: It is often observed that the number coefficients of the result becomes
941: very very long integers, especially if the ideal is 0-dimensional.
942: For such a case, it is empirically true for many cases
943: that i.e., computation by
944: @code{gr()} and/or @code{hgr()} may be quite effective.
945: \E
1.1 noro 946: @end table
947:
948: @noindent
1.2 noro 949: \BJP
1.25 ! noro 950: これらを組み合わせてリストで指定することにより, 様々な消去順序が指定できる.
! 951: これは,
1.2 noro 952: \E
953: \BEG
954: By combining these fundamental orderingl into a list, one can make
955: various term ordering called elimination orderings.
956: \E
1.1 noro 957:
958: @code{[[O1,L1],[O2,L2],...]}
959:
960: @noindent
1.2 noro 961: \BJP
1.25 ! noro 962: で指定される. @code{Oi} は 0, 1, 2 のいずれかで, @code{Li} は変数の個
! 963: 数を表す. この指定は, 変数を先頭から @code{L1}, @code{L2} , ...個
! 964: ずつの組に分け, それぞれの変数に関し, 順に @code{O1}, @code{O2},
! 965: ...の項順序型で大小が決定するまで比較することを意味する. この型の
! 966: 順序は一般に消去順序と呼ばれる.
1.2 noro 967: \E
968: \BEG
969: In this example @code{Oi} indicates 0, 1 or 2 and @code{Li} indicates
970: the number of variables subject to the correspoinding orderings.
971: This specification means the following.
972:
973: The variable list is separated into sub lists from left to right where
974: the @code{i}-th list contains @code{Li} members and it corresponds to
975: the ordering of type @code{Oi}. The result of a comparison is equal
976: to that for the leftmost different sub components. This type of ordering
977: is called an elimination ordering.
978: \E
1.1 noro 979:
980: @noindent
1.2 noro 981: \BJP
1.25 ! noro 982: さらに, 行列により項順序を指定することができる. 一般に, @code{n} 行
! 983: @code{m} 列の実数行列 @code{M} が次の性質を持つとする.
1.2 noro 984: \E
985: \BEG
986: Furthermore one can specify a term ordering by a matix.
987: Suppose that a real @code{n}, @code{m} matrix @code{M} has the
988: following properties.
989: \E
1.1 noro 990:
991: @enumerate
992: @item
1.25 ! noro 993: \JP 長さ @code{m} の整数ベクトル @code{v} に対し @code{Mv=0} と @code{v=0} は同値.
1.2 noro 994: \BEG
995: For all integer verctors @code{v} of length @code{m} @code{Mv=0} is equivalent
996: to @code{v=0}.
997: \E
1.1 noro 998:
999: @item
1.2 noro 1000: \BJP
1.25 ! noro 1001: 非負成分を持つ長さ @code{m} の 0 でない整数ベクトル @code{v} に対し,
! 1002: @code{Mv} の 0 でない最初の成分は非負.
1.2 noro 1003: \E
1004: \BEG
1005: For all non-negative integer vectors @code{v} the first non-zero component
1006: of @code{Mv} is non-negative.
1007: \E
1.1 noro 1008: @end enumerate
1009:
1010: @noindent
1.2 noro 1011: \BJP
1.25 ! noro 1012: この時, 2 つのベクトル @code{t}, @code{s} に対し,
! 1013: @code{t>s} を, @code{M(t-s)} の 0 でない最初の成分が非負,
! 1014: で定義することにより項順序が定義できる.
1.2 noro 1015: \E
1016: \BEG
1017: Then we can define a term ordering such that, for two vectors
1018: @code{t}, @code{s}, @code{t>s} means that the first non-zero component
1019: of @code{M(t-s)} is non-negative.
1020: \E
1.1 noro 1021:
1022: @noindent
1.2 noro 1023: \BJP
1.25 ! noro 1024: 項順序型は, @code{gr()} などの引数として指定される他, 組み込み函数
! 1025: @code{dp_ord()} で指定され, さまざまな函数の実行の際に参照される.
1.2 noro 1026: \E
1027: \BEG
1028: Types of term orderings are used as arguments of functions such as
1029: @code{gr()}. It is also set internally by @code{dp_ord()} and is used
1030: during executions of various functions.
1031: \E
1.1 noro 1032:
1033: @noindent
1.2 noro 1034: \BJP
1.25 ! noro 1035: これらの順序の具体的な定義およびグレブナ基底に関する更に詳しい解説は
! 1036: @code{[Becker,Weispfenning]} などを参照のこと.
1.2 noro 1037: \E
1038: \BEG
1039: For concrete definitions of term ordering and more information
1040: about Groebner basis, refer to, for example, the book
1041: @code{[Becker,Weispfenning]}.
1042: \E
1.1 noro 1043:
1044: @noindent
1.25 ! noro 1045: \JP 項順序型の設定の他に, 変数の順序自体も計算時間に大きな影響を与える.
1.2 noro 1046: \BEG
1047: Note that the variable ordering have strong effects on the computation
1048: time as well as the choice of types of term orderings.
1049: \E
1.1 noro 1050:
1051: @example
1052: [90] B=[x^10-t,x^8-z,x^31-x^6-x-y]$
1053: [91] gr(B,[x,y,z,t],2);
1054: [x^2-2*y^7+(-41*t^2-13*t-1)*y^2+(2*t^17-12*t^14+42*t^12+30*t^11-168*t^9
1055: -40*t^8+70*t^7+252*t^6+30*t^5-140*t^4-168*t^3+2*t^2-12*t+16)*z^2*y
1056: +(-12*t^16+72*t^13-28*t^11-180*t^10+112*t^8+240*t^7+28*t^6-127*t^5
1057: -167*t^4-55*t^3+30*t^2+58*t-15)*z^4,
1.5 noro 1058: (y+t^2*z^2)*x+y^7+(20*t^2+6*t+1)*y^2+(-t^17+6*t^14-21*t^12-15*t^11
1059: +84*t^9+20*t^8-35*t^7-126*t^6-15*t^5+70*t^4+84*t^3-t^2+5*t-9)*z^2*y
1060: +(6*t^16-36*t^13+14*t^11+90*t^10-56*t^8-120*t^7-14*t^6+64*t^5+84*t^4
1061: +27*t^3-16*t^2-30*t+7)*z^4,
1062: (t^3-1)*x-y^6+(-6*t^13+24*t^10-20*t^8-36*t^7+40*t^5+24*t^4-6*t^3-20*t^2
1063: -6*t-1)*y+(t^17-6*t^14+9*t^12+15*t^11-36*t^9-20*t^8-5*t^7+54*t^6+15*t^5
1064: +10*t^4-36*t^3-11*t^2-5*t+9)*z^2,
1.1 noro 1065: -y^8-8*t*y^3+16*z^2*y^2+(-8*t^16+48*t^13-56*t^11-120*t^10+224*t^8+160*t^7
1.5 noro 1066: -56*t^6-336*t^5-112*t^4+112*t^3+224*t^2+24*t-56)*z^4*y+(t^24-8*t^21
1067: +20*t^19+28*t^18-120*t^16-56*t^15+14*t^14+300*t^13+70*t^12-56*t^11
1068: -400*t^10-84*t^9+84*t^8+268*t^7+84*t^6-56*t^5-63*t^4-36*t^3+46*t^2
1069: -12*t+1)*z,2*t*y^5+z*y^2+(-2*t^11+8*t^8-20*t^6-12*t^5+40*t^3+8*t^2
1070: -10*t-20)*z^3*y+8*t^14-32*t^11+48*t^8-t^7-32*t^5-6*t^4+9*t^2-t,
1.1 noro 1071: -z*y^3+(t^7-2*t^4+3*t^2+t)*y+(-2*t^6+4*t^3+2*t-2)*z^2,
1.5 noro 1072: 2*t^2*y^3+z^2*y^2+(-2*t^5+4*t^2-6)*z^4*y
1073: +(4*t^8-t^7-8*t^5+2*t^4-4*t^3+5*t^2-t)*z,
1.1 noro 1074: z^3*y^2+2*t^3*y+(-t^7+2*t^4+t^2-t)*z^2,
1075: -t*z*y^2-2*z^3*y+t^8-2*t^5-t^3+t^2,
1.5 noro 1076: -t^3*y^2-2*t^2*z^2*y+(t^6-2*t^3-t+1)*z^4,z^5-t^4]
1.1 noro 1077: [93] gr(B,[t,z,y,x],2);
1078: [x^10-t,x^8-z,x^31-x^6-x-y]
1079: @end example
1080:
1081: @noindent
1.2 noro 1082: \BJP
1.25 ! noro 1083: 変数順序 @code{[x,y,z,t]} におけるグレブナ基底は, 基底の数も多く, それぞれの
! 1084: 式も大きい. しかし, 順序 @code{[t,z,y,x]} にもとでは, @code{B} がすでに
! 1085: グレブナ基底となっている. 大雑把にいえば, 辞書式順序でグレブナ基底を求める
! 1086: ことは, 左側の (順序の高い) 変数を, 右側の (順序の低い) 変数で書き表す
! 1087: ことであり, この例の場合は, @code{t}, @code{z}, @code{y} が既に
! 1088: @code{x} で表されていることからこのような極端な結果となったわけである.
! 1089: 実際に現れる計算においては, このように選ぶべき変数順序が明らかである
! 1090: ことは少なく, 試行錯誤が必要な場合もある.
1.2 noro 1091: \E
1092: \BEG
1093: As you see in the above example, the Groebner base under variable
1094: ordering @code{[x,y,z,t]} has a lot of bases and each base itself is
1095: large. Under variable ordering @code{[t,z,y,x]}, however, @code{B} itself
1096: is already the Groebner basis.
1097: Roughly speaking, to obtain a Groebner base under the lexicographic
1098: ordering is to express the variables on the left (having higher order)
1099: in terms of variables on the right (having lower order).
1100: In the example, variables @code{t}, @code{z}, and @code{y} are already
1101: expressed by variable @code{x}, and the above explanation justifies
1102: such a drastic experimental results.
1103: In practice, however, optimum ordering for variables may not known
1104: beforehand, and some heuristic trial may be inevitable.
1.13 noro 1105: \E
1106:
1107: \BJP
1.25 ! noro 1108: @node Weight ,,, グレブナ基底の計算
1.13 noro 1109: @section Weight
1110: \E
1111: \BEG
1112: @node Weight,,, Groebner basis computation
1113: @section Weight
1114: \E
1115: \BJP
1.25 ! noro 1116: 前節で紹介した項順序は, 各変数に weight (重み) を設定することで
! 1117: より一般的なものとなる.
1.13 noro 1118: \E
1119: \BEG
1.14 noro 1120: Term orderings introduced in the previous section can be generalized
1.13 noro 1121: by setting a weight for each variable.
1122: \E
1123: @example
1124: [0] dp_td(<<1,1,1>>);
1125: 3
1126: [1] dp_set_weight([1,2,3])$
1127: [2] dp_td(<<1,1,1>>);
1128: 6
1129: @end example
1130: \BJP
1.25 ! noro 1131: 単項式の全次数を計算する際, デフォルトでは
! 1132: 各変数の指数の和を全次数とする. これは各変数の weight を 1 と
! 1133: 考えていることに相当する. この例では, 第一, 第二, 第三変数の
! 1134: weight をそれぞれ 1,2,3 と指定している. このため, @code{<<1,1,1>>}
! 1135: の全次数 (以下ではこれを単項式の weight と呼ぶ) が @code{1*1+1*2+1*3=6} となる.
! 1136: weight を設定することで, 同じ項順序型のもとで異なる項順序が定義できる.
! 1137: 例えば, weight をうまく設定することで, 多項式を weighted homogeneous
! 1138: にすることができる場合がある.
1.13 noro 1139: \E
1140: \BEG
1141: By default, the total degree of a monomial is equal to
1142: the sum of all exponents. This means that the weight for each variable
1143: is set to 1.
1144: In this example, the weights for the first, the second and the third
1145: variable are set to 1, 2 and 3 respectively.
1146: Therefore the total degree of @code{<<1,1,1>>} under this weight,
1147: which is called the weight of the monomial, is @code{1*1+1*2+1*3=6}.
1.14 noro 1148: By setting weights, different term orderings can be set under a type of
1149: term ordeing. In some case a polynomial can
1150: be made weighted homogeneous by setting an appropriate weight.
1.13 noro 1151: \E
1152:
1153: \BJP
1.25 ! noro 1154: 各変数に対する weight をまとめたものを weight vector と呼ぶ.
! 1155: すべての成分が正であり, グレブナ基底計算において, 全次数の
! 1156: 代わりに用いられるものを特に sugar weight と呼ぶことにする.
! 1157: sugar strategy において, 全次数の代わりに使われるからである.
! 1158: 一方で, 各成分が必ずしも正とは限らない weight vector は,
! 1159: sugar weight として設定することはできないが, 項順序の一般化には
! 1160: 有用である. これらは, 行列による項順序の設定にすでに現れて
! 1161: いる. すなわち, 項順序を定義する行列の各行が, 一つの weight vector
! 1162: と見なされる. また, ブロック順序は, 各ブロックの
! 1163: 変数に対応する成分のみ 1 で他は 0 の weight vector による比較を
! 1164: 最初に行ってから, 各ブロック毎の tie breaking を行うことに相当する.
1.13 noro 1165: \E
1166:
1167: \BEG
1168: A list of weights for all variables is called a weight vector.
1169: A weight vector is called a sugar weight vector if
1170: its elements are all positive and it is used for computing
1171: a weighted total degree of a monomial, because such a weight
1172: is used instead of total degree in sugar strategy.
1173: On the other hand, a weight vector whose elements are not necessarily
1174: positive cannot be set as a sugar weight, but it is useful for
1175: generalizing term order. In fact, such a weight vector already
1176: appeared in a matrix order. That is, each row of a matrix defining
1177: a term order is regarded as a weight vector. A block order
1178: is also considered as a refinement of comparison by weight vectors.
1179: It compares two terms by using a weight vector whose elements
1180: corresponding to variables in a block is 1 and 0 otherwise,
1181: then it applies a tie breaker.
1.14 noro 1182: \E
1183:
1184: \BJP
1.25 ! noro 1185: weight vector の設定は @code{dp_set_weight()} で行うことができる
! 1186: が, 項順序を指定する際の他のパラメタ (項順序型, 変数順序) と
! 1187: まとめて設定できることが望ましい. このため, 次のような形でも
! 1188: 項順序が指定できる.
1.14 noro 1189: \E
1190: \BEG
1191: A weight vector can be set by using @code{dp_set_weight()}.
1192: However it is more preferable if a weight vector can be set
1193: together with other parapmeters such as a type of term ordering
1194: and a variable order. This is realized as follows.
1195: \E
1.13 noro 1196:
1.14 noro 1197: @example
1198: [64] B=[x+y+z-6,x*y+y*z+z*x-11,x*y*z-6]$
1199: [65] dp_gr_main(B|v=[x,y,z],sugarweight=[3,2,1],order=0);
1200: [z^3-6*z^2+11*z-6,x+y+z-6,-y^2+(-z+6)*y-z^2+6*z-11]
1201: [66] dp_gr_main(B|v=[y,z,x],order=[[1,1,0],[0,1,0],[0,0,1]]);
1202: [x^3-6*x^2+11*x-6,x+y+z-6,-x^2+(-y+6)*x-y^2+6*y-11]
1203: [67] dp_gr_main(B|v=[y,z,x],order=[[x,1,y,2,z,3]]);
1204: [x+y+z-6,x^3-6*x^2+11*x-6,-x^2+(-y+6)*x-y^2+6*y-11]
1205: @end example
1206:
1207: \BJP
1.25 ! noro 1208: いずれの例においても, 項順序は option として指定されている.
! 1209: 最初の例では @code{v} により変数順序を, @code{sugarweight} により
! 1210: sugar weight vector を, @code{order}により項順序型を指定している.
! 1211: 二つ目の例における @code{order} の指定は matrix order と同様である.
! 1212: すなわち, 指定された weight vector を左から順に使って weight の比較
! 1213: を行う. 三つ目の例も同様であるが, ここでは weight vector の要素を
! 1214: 変数毎に指定している. 指定がないものは 0 となる. 三つ目の例では,
! 1215: @code{order} による指定では項順序が決定しない. この場合には,
! 1216: tie breaker として全次数逆辞書式順序が自動的に設定される.
! 1217: この指定方法は, @code{dp_gr_main}, @code{dp_gr_mod_main} など
! 1218: の組み込み関数でのみ可能であり, @code{gr} などのユーザ定義関数
! 1219: では未対応である.
1.14 noro 1220: \E
1221: \BEG
1222: In each example, a term ordering is specified as options.
1223: In the first example, a variable order, a sugar weight vector
1224: and a type of term ordering are specified by options @code{v},
1225: @code{sugarweight} and @code{order} respectively.
1226: In the second example, an option @code{order} is used
1227: to set a matrix ordering. That is, the specified weight vectors
1228: are used from left to right for comparing terms.
1229: The third example shows a variant of specifying a weight vector,
1230: where each component of a weight vector is specified variable by variable,
1231: and unspecified components are set to zero. In this example,
1232: a term order is not determined only by the specified weight vector.
1233: In such a case a tie breaker by the graded reverse lexicographic ordering
1234: is set automatically.
1235: This type of a term ordering specification can be applied only to builtin
1236: functions such as @code{dp_gr_main()}, @code{dp_gr_mod_main()}, not to
1237: user defined functions such as @code{gr()}.
1.2 noro 1238: \E
1.1 noro 1239:
1.2 noro 1240: \BJP
1.25 ! noro 1241: @node 有理式を係数とするグレブナ基底計算,,, グレブナ基底の計算
! 1242: @section 有理式を係数とするグレブナ基底計算
1.2 noro 1243: \E
1244: \BEG
1245: @node Groebner basis computation with rational function coefficients,,, Groebner basis computation
1246: @section Groebner basis computation with rational function coefficients
1247: \E
1.1 noro 1248:
1249: @noindent
1.2 noro 1250: \BJP
1.25 ! noro 1251: @code{gr()} などのトップレベル函数は, いずれも, 入力多項式リストに
! 1252: 現れる変数 (不定元) と, 変数リストに現れる変数を比較して, 変数リストに
! 1253: ない変数が入力多項式に現れている場合には, 自動的に, その変数を, 係数
! 1254: 体の元として扱う.
1.2 noro 1255: \E
1256: \BEG
1257: Such variables that appear within the input polynomials but
1258: not appearing in the input variable list are automatically treated
1259: as elements in the coefficient field
1260: by top level functions, such as @code{gr()}.
1261: \E
1.1 noro 1262:
1263: @example
1264: [64] gr([a*x+b*y-c,d*x+e*y-f],[x,y],2);
1265: [(-e*a+d*b)*x-f*b+e*c,(-e*a+d*b)*y+f*a-d*c]
1266: @end example
1267:
1268: @noindent
1.2 noro 1269: \BJP
1.25 ! noro 1270: この例では, @code{a}, @code{b}, @code{c}, @code{d} が係数体の元として
! 1271: 扱われる. すなわち, 有理函数体
! 1272: @b{F} = @b{Q}(@code{a},@code{b},@code{c},@code{d}) 上の 2 変数多項式環
! 1273: @b{F}[@code{x},@code{y}] におけるグレブナ基底を求めることになる.
! 1274: 注意すべきことは,
! 1275: 係数が体として扱われていることである. すなわち, 係数の間に多項式
! 1276: としての共通因子があった場合には, 結果からその因子は除かれている
! 1277: ため, 有理数体上の多項式環上の問題として考えた場合の結果とは一般
! 1278: には異なる. また, 主として計算効率上の問題のため, 分散表現多項式
! 1279: の係数として実際に許されるのは多項式までである. すなわち, 分母を
! 1280: 持つ有理式は分散表現多項式の係数としては許されない.
1.2 noro 1281: \E
1282: \BEG
1283: In this example, variables @code{a}, @code{b}, @code{c}, and @code{d}
1284: are treated as elements in the coefficient field.
1285: In this case, a Groebner basis is computed
1286: on a bi-variate polynomial ring
1287: @b{F}[@code{x},@code{y}]
1288: over rational function field
1289: @b{F} = @b{Q}(@code{a},@code{b},@code{c},@code{d}).
1290: Notice that coefficients are considered as a member in a field.
1291: As a consequence, polynomial factors common to the coefficients
1292: are removed so that the result, in general, is different from
1293: the result that would be obtained when the problem is considered
1294: as a computation of Groebner basis over a polynomial ring
1295: with rational function coefficients.
1296: And note that coefficients of a distributed polynomial are limited
1297: to numbers and polynomials because of efficiency.
1298: \E
1.1 noro 1299:
1.2 noro 1300: \BJP
1.25 ! noro 1301: @node 基底変換,,, グレブナ基底の計算
! 1302: @section 基底変換
1.2 noro 1303: \E
1304: \BEG
1305: @node Change of ordering,,, Groebner basis computation
1306: @section Change of orderng
1307: \E
1.1 noro 1308:
1309: @noindent
1.2 noro 1310: \BJP
1.25 ! noro 1311: 辞書式順序のグレブナ基底を求める場合, 直接 @code{gr()} などを起動する
! 1312: より, 一旦他の順序 (例えば全次数逆辞書式順序) のグレブナ基底を計算して,
! 1313: それを入力として辞書式順序のグレブナ基底を計算する方が効率がよい場合
! 1314: がある. また, 入力が何らかの順序でのグレブナ基底になっている場合, 基底
! 1315: 変換と呼ばれる方法により, Buchberger アルゴリズムによらずに効率良く
! 1316: 辞書式順序のグレブナ基底が計算できる場合がある. このような目的のための
! 1317: 函数が, ユーザ定義函数として @samp{gr} にいくつか定義されている.
! 1318: 以下の 2 つの函数は, 変数順序 @var{vlist1}, 項順序型 @var{order} で
! 1319: 既にグレブナ基底となっている多項式リスト @var{gbase} を, 変数順序
! 1320: @var{vlist2} における辞書式順序のグレブナ基底に変換する函数である.
1.2 noro 1321: \E
1322: \BEG
1323: When we compute a lex order Groebner basis, it is often efficient to
1324: compute it via Groebner basis with respect to another order such as
1325: degree reverse lex order, rather than to compute it directory by
1326: @code{gr()} etc. If we know that an input is a Groebner basis with
1327: respect to an order, we can apply special methods called change of
1328: ordering for a Groebner basis computation with respect to another
1329: order, without using Buchberger algorithm. The following two functions
1330: are ones for change of ordering such that they convert a Groebner
1331: basis @var{gbase} with respect to the variable order @var{vlist1} and
1332: the order type @var{order} into a lex Groebner basis with respect
1333: to the variable order @var{vlist2}.
1334: \E
1.1 noro 1335:
1336: @table @code
1337: @item tolex(@var{gbase},@var{vlist1},@var{order},@var{vlist2})
1338:
1.2 noro 1339: \BJP
1.25 ! noro 1340: この函数は, @var{gbase} が有理数体上のシステムの場合にのみ使用可能である.
! 1341: この函数は, 辞書式順序のグレブナ基底を, 有限体上で計算されたグレブナ基底
! 1342: を雛型として, 未定係数法および Hensel 構成により求めるものである.
1.2 noro 1343: \E
1344: \BEG
1345: This function can be used only when @var{gbase} is an ideal over the
1346: rationals. The input @var{gbase} must be a Groebner basis with respect
1347: to the variable order @var{vlist1} and the order type @var{order}. Moreover
1348: the ideal generated by @var{gbase} must be zero-dimensional.
1349: This computes the lex Groebner basis of @var{gbase}
1350: by using the modular change of ordering algorithm. The algorithm first
1351: computes the lex Groebner basis over a finite field. Then each element
1352: in the lex Groebner basis over the rationals is computed with undetermined
1353: coefficient method and linear equation solving by Hensel lifting.
1354: \E
1.1 noro 1355:
1356: @item tolex_tl(@var{gbase},@var{vlist1},@var{order},@var{vlist2},@var{homo})
1357:
1.2 noro 1358: \BJP
1.25 ! noro 1359: この函数は, 辞書式順序のグレブナ基底を Buchberger アルゴリズムにより求
! 1360: めるものであるが, 入力がある順序におけるグレブナ基底である場合の
! 1361: trace-liftingにおけるグレブナ基底候補の頭項, 頭係数の性質を利用して,
! 1362: 最終的なグレブナ基底チェック, イデアルメンバシップチェックを省略してい
! 1363: るため, 単にBuchberger アルゴリズムを繰り返すより効率よく計算できる.
! 1364: 更に, 入力が 0 次元システムの場合, 自動的にもう 1 つの中間的な項順序を
! 1365: 経由して辞書式順序のグレブナ基底を計算する. 多くの場合, この方法は,
! 1366: 直接辞書式順序の計算を行うより効率がよい. (もちろん例外あり. )
! 1367: 引数 @var{homo} が 0 でない時, @code{hgr()} と同様に斉次化を経由して
! 1368: 計算を行う.
1.2 noro 1369: \E
1370: \BEG
1371: This function computes the lex Groebner basis of @var{gbase}. The
1372: input @var{gbase} must be a Groebner basis with respect to the
1373: variable order @var{vlist1} and the order type @var{order}.
1374: Buchberger algorithm with trace lifting is used to compute the lex
1375: Groebner basis, however the Groebner basis check and the ideal
1376: membership check can be omitted by using several properties derived
1377: from the fact that the input is a Groebner basis. So it is more
1378: efficient than simple repetition of Buchberger algorithm. If the input
1379: is zero-dimensional, this function inserts automatically a computation
1380: of Groebner basis with respect to an elimination order, which makes
1381: the whole computation more efficient for many cases. If @var{homo} is
1382: not equal to 0, homogenization is used in each step.
1383: \E
1.1 noro 1384: @end table
1385:
1386: @noindent
1.2 noro 1387: \BJP
1.25 ! noro 1388: その他, 0 次元システムに対し, 与えられた多項式の最小多項式を求める
! 1389: 函数, 0 次元システムの解を, よりコンパクトに表現するための函数などが
! 1390: @samp{gr} で定義されている. これらについては個々の函数の説明を参照のこと.
1.2 noro 1391: \E
1392: \BEG
1393: For zero-dimensional systems, there are several fuctions to
1394: compute the minimal polynomial of a polynomial and or a more compact
1395: representation for zeros of the system. They are all defined in @samp{gr}.
1396: Refer to the sections for each functions.
1397: \E
1.1 noro 1398:
1.2 noro 1399: \BJP
1.25 ! noro 1400: @node Weyl 代数,,, グレブナ基底の計算
! 1401: @section Weyl 代数
1.6 noro 1402: \E
1403: \BEG
1404: @node Weyl algebra,,, Groebner basis computation
1405: @section Weyl algebra
1406: \E
1407:
1408: @noindent
1409:
1410: \BJP
1.25 ! noro 1411: これまでは, 通常の可換な多項式環におけるグレブナ基底計算について
! 1412: 述べてきたが, グレブナ基底の理論は, ある条件を満たす非可換な
! 1413: 環にも拡張できる. このような環の中で, 応用上も重要な,
! 1414: Weyl 代数, すなわち多項式環上の微分作用素環の演算および
! 1415: グレブナ基底計算が Risa/Asir に実装されている.
1.6 noro 1416:
1.25 ! noro 1417: 体 @code{K} 上の @code{n} 次元 Weyl 代数
! 1418: @code{D=K<x1,@dots{},xn,D1,@dots{},Dn>} は
1.6 noro 1419: \E
1420:
1421: \BEG
1422: So far we have explained Groebner basis computation in
1423: commutative polynomial rings. However Groebner basis can be
1424: considered in more general non-commutative rings.
1425: Weyl algebra is one of such rings and
1426: Risa/Asir implements fundamental operations
1427: in Weyl algebra and Groebner basis computation in Weyl algebra.
1428:
1429: The @code{n} dimensional Weyl algebra over a field @code{K},
1430: @code{D=K<x1,@dots{},xn,D1,@dots{},Dn>} is a non-commutative
1431: algebra which has the following fundamental relations:
1432: \E
1433:
1434: @code{xi*xj-xj*xi=0}, @code{Di*Dj-Dj*Di=0}, @code{Di*xj-xj*Di=0} (@code{i!=j}),
1435: @code{Di*xi-xi*Di=1}
1436:
1437: \BJP
1.25 ! noro 1438: という基本関係を持つ環である. @code{D} は 多項式環 @code{K[x1,@dots{},xn]} を係数
! 1439: とする微分作用素環で, @code{Di} は @code{xi} による微分を表す. 交換関係により,
! 1440: @code{D} の元は, @code{x1^i1*@dots{}*xn^in*D1^j1*@dots{}*Dn^jn} なる単項
! 1441: 式の @code{K} 線形結合として書き表すことができる.
! 1442: Risa/Asir においては, この単項式を, 可換な多項式と同様に
! 1443: @code{<<i1,@dots{},in,j1,@dots{},jn>>} で表す. すなわち, @code{D} の元も
! 1444: 分散表現多項式として表される. 加減算は, 可換の場合と同様に, @code{+}, @code{-}
! 1445: により
! 1446: 実行できるが, 乗算は, 非可換性を考慮して @code{dp_weyl_mul()} という関数
! 1447: により実行する.
1.6 noro 1448: \E
1449:
1450: \BEG
1451: @code{D} is the ring of differential operators whose coefficients
1452: are polynomials in @code{K[x1,@dots{},xn]} and
1453: @code{Di} denotes the differentiation with respect to @code{xi}.
1454: According to the commutation relation,
1455: elements of @code{D} can be represented as a @code{K}-linear combination
1456: of monomials @code{x1^i1*@dots{}*xn^in*D1^j1*@dots{}*Dn^jn}.
1457: In Risa/Asir, this type of monomial is represented
1458: by @code{<<i1,@dots{},in,j1,@dots{},jn>>} as in the case of commutative
1459: polynomial.
1460: That is, elements of @code{D} are represented by distributed polynomials.
1461: Addition and subtraction can be done by @code{+}, @code{-},
1462: but multiplication is done by calling @code{dp_weyl_mul()} because of
1463: the non-commutativity of @code{D}.
1464: \E
1465:
1466: @example
1467: [0] A=<<1,2,2,1>>;
1468: (1)*<<1,2,2,1>>
1469: [1] B=<<2,1,1,2>>;
1470: (1)*<<2,1,1,2>>
1471: [2] A*B;
1472: (1)*<<3,3,3,3>>
1473: [3] dp_weyl_mul(A,B);
1474: (1)*<<3,3,3,3>>+(1)*<<3,2,3,2>>+(4)*<<2,3,2,3>>+(4)*<<2,2,2,2>>
1475: +(2)*<<1,3,1,3>>+(2)*<<1,2,1,2>>
1476: @end example
1477:
1478: \BJP
1.25 ! noro 1479: グレブナ基底計算についても, Weyl 代数専用の関数として,
! 1480: 次の関数が用意してある.
1.6 noro 1481: \E
1482: \BEG
1483: The following functions are avilable for Groebner basis computation
1484: in Weyl algebra:
1485: \E
1486: @code{dp_weyl_gr_main()},
1487: @code{dp_weyl_gr_mod_main()},
1488: @code{dp_weyl_gr_f_main()},
1489: @code{dp_weyl_f4_main()},
1490: @code{dp_weyl_f4_mod_main()}.
1491: \BJP
1.25 ! noro 1492: また, 応用として, global b 関数の計算が実装されている.
1.6 noro 1493: \E
1494: \BEG
1495: Computation of the global b function is implemented as an application.
1496: \E
1497:
1498: \BJP
1.25 ! noro 1499: @node 多項式環上の加群,,, グレブナ基底の計算
! 1500: @section 多項式環上の加群
1.23 noro 1501: \E
1502: \BEG
1503: @node Module over a polynomial ring,,, Groebner basis computation
1504: @section Module over a polynomial ring
1505: \E
1506:
1507: @noindent
1508:
1509: \BJP
1.25 ! noro 1510: 多項式環上の自由加群の元は, 加群単項式 te_i の線型和として内部表現される.
! 1511: ここで t は多項式環の単項式, e_i は自由加群の標準基底である. 加群単項式は, 多項式環の単項式
! 1512: に位置 i を追加した @code{<<a,b,...,c:i>>} で表す. 加群多項式, すなわち加群単項式の線型和は,
! 1513: 設定されている加群項順序にしたがって降順に整列される. 加群項順序には以下の3種類がある.
1.23 noro 1514:
1515: @table @code
1.25 ! noro 1516: @item TOP 順序
1.23 noro 1517:
1.25 ! noro 1518: これは, te_i > se_j となるのは t>s または (t=s かつ i<j) となるような項順序である. ここで,
! 1519: t, s の比較は多項式環に設定されている順序で行う.
! 1520: この型の順序は, @code{dp_ord([0,Ord])} に
! 1521: より設定する. ここで, @code{Ord} は多項式環の順序型である.
! 1522:
! 1523: @item POT 順序
! 1524:
! 1525: これは, te_i > se_j となるのは i<j または (i=j かつ t>s) となるような項順序である. ここで,
! 1526: t, s の比較は多項式環に設定されている順序で行う.
! 1527: この型の順序は, @code{dp_ord([1,Ord])} に
! 1528: より設定する. ここで, @code{Ord} は多項式環の順序型である.
! 1529:
! 1530: @item Schreyer 型順序
! 1531:
! 1532: 各標準基底 e_i に対し, 別の自由加群の加群単項式 T_i が与えられていて, te_i > se_j となるのは
! 1533: tT_i > sT_j または (tT_i=sT_j かつ i<j) となるような項順序である. ここで tT_i, sT_j の
! 1534: 比較は, これらが所属する自由加群に設定されている順序で行う.
! 1535: この型の順序は, 通常再帰的に設定される. すなわち, T_i が所属する自由加群の順序も Schreyer 型
! 1536: であるか, またはボトムとなる TOP, POT などの項順序となる.
! 1537: この型の順序は @code{dpm_set_schreyer([H_1,H_2,...])} により指定する. ここで,
! 1538: @code{H_i=[T_1,T_2,...]} は加群単項式のリストで, @code{[H_2,...]} で定義される Schreyer 型項順序を
! 1539: @code{tT_i} らに適用するという意味である.
1.23 noro 1540: @end table
1541:
1.25 ! noro 1542: 加群多項式を入力する方法としては, @code{<<a,b,...:i>>} なる形式で直接入力する他に,
! 1543: 多項式リストを作り, @code{dpm_ltod()} により変換する方法もある.
1.23 noro 1544: \E
1545: \BEG
1546: not yet
1547: \E
1548:
1549: \BJP
1.25 ! noro 1550: @node グレブナ基底に関する函数,,, グレブナ基底の計算
! 1551: @section グレブナ基底に関する函数
1.2 noro 1552: \E
1553: \BEG
1554: @node Functions for Groebner basis computation,,, Groebner basis computation
1555: @section Functions for Groebner basis computation
1556: \E
1.1 noro 1557:
1558: @menu
1559: * gr hgr gr_mod::
1560: * lex_hensel lex_tl tolex tolex_d tolex_tl::
1561: * lex_hensel_gsl tolex_gsl tolex_gsl_d::
1562: * gr_minipoly minipoly::
1563: * tolexm minipolym::
1.6 noro 1564: * dp_gr_main dp_gr_mod_main dp_gr_f_main dp_weyl_gr_main dp_weyl_gr_mod_main dp_weyl_gr_f_main::
1565: * dp_f4_main dp_f4_mod_main dp_weyl_f4_main dp_weyl_f4_mod_main::
1.17 noro 1566: * nd_gr nd_gr_trace nd_f4 nd_f4_trace nd_weyl_gr nd_weyl_gr_trace::
1.22 noro 1567: * nd_gr_postproc nd_weyl_gr_postproc::
1.1 noro 1568: * dp_gr_flags dp_gr_print::
1569: * dp_ord::
1.18 noro 1570: * dp_set_weight dp_set_top_weight dp_weyl_set_weight::
1.1 noro 1571: * dp_ptod::
1572: * dp_dtop::
1573: * dp_mod dp_rat::
1574: * dp_homo dp_dehomo::
1575: * dp_ptozp dp_prim::
1.18 noro 1576: * dp_nf dp_nf_mod dp_true_nf dp_true_nf_mod dp_weyl_nf dp_weyl_nf_mod::
1.1 noro 1577: * dp_hm dp_ht dp_hc dp_rest::
1.23 noro 1578: * dpm_hm dpm_ht dpm_hc dpm_hp dpm_rest::
1.24 noro 1579: * dpm_sp::
1580: * dpm_redble::
1581: * dpm_nf dpm_nf_and_quotient::
1582: * dpm_dtol::
1583: * dpm_ltod::
1584: * dpm_dptodpm::
1.25 ! noro 1585: * dpm_schreyer_base::
! 1586: * dpm_schreyer_frame::
! 1587: * dpm_set_schreyer_level::
! 1588: * dpm_sp_nf::
1.1 noro 1589: * dp_td dp_sugar::
1590: * dp_lcm::
1591: * dp_redble::
1592: * dp_subd::
1593: * dp_mbase::
1594: * dp_mag::
1595: * dp_red dp_red_mod::
1596: * dp_sp dp_sp_mod::
1597: * p_nf p_nf_mod p_true_nf p_true_nf_mod ::
1598: * p_terms::
1599: * gb_comp::
1600: * katsura hkatsura cyclic hcyclic::
1601: * dp_vtoe dp_etov::
1602: * lex_hensel_gsl tolex_gsl tolex_gsl_d::
1.3 noro 1603: * primadec primedec::
1.5 noro 1604: * primedec_mod::
1.10 noro 1605: * bfunction bfct generic_bfct ann ann0::
1.1 noro 1606: @end menu
1607:
1.25 ! noro 1608: \JP @node gr hgr gr_mod,,, グレブナ基底に関する函数
1.2 noro 1609: \EG @node gr hgr gr_mod,,, Functions for Groebner basis computation
1.1 noro 1610: @subsection @code{gr}, @code{hgr}, @code{gr_mod}, @code{dgr}
1611: @findex gr
1612: @findex hgr
1613: @findex gr_mod
1614: @findex dgr
1615:
1616: @table @t
1617: @item gr(@var{plist},@var{vlist},@var{order})
1618: @itemx hgr(@var{plist},@var{vlist},@var{order})
1619: @itemx gr_mod(@var{plist},@var{vlist},@var{order},@var{p})
1620: @itemx dgr(@var{plist},@var{vlist},@var{order},@var{procs})
1.25 ! noro 1621: \JP :: グレブナ基底の計算
1.2 noro 1622: \EG :: Groebner basis computation
1.1 noro 1623: @end table
1624:
1625: @table @var
1626: @item return
1.25 ! noro 1627: \JP リスト
1.2 noro 1628: \EG list
1.4 noro 1629: @item plist vlist procs
1.25 ! noro 1630: \JP リスト
1.2 noro 1631: \EG list
1.1 noro 1632: @item order
1.25 ! noro 1633: \JP 数, リストまたは行列
1.2 noro 1634: \EG number, list or matrix
1.1 noro 1635: @item p
1.25 ! noro 1636: \JP 2^27 未満の素数
1.2 noro 1637: \EG prime less than 2^27
1.1 noro 1638: @end table
1639:
1640: @itemize @bullet
1.2 noro 1641: \BJP
1.1 noro 1642: @item
1.25 ! noro 1643: 標準ライブラリの @samp{gr} で定義されている.
1.1 noro 1644: @item
1.25 ! noro 1645: gr を名前に含む関数は現在メンテされていない. @code{nd_gr}系の関数を代わりに利用すべきである(@fref{nd_gr nd_gr_trace nd_f4 nd_f4_trace nd_weyl_gr nd_weyl_gr_trace}).
1.21 takayama 1646: @item
1.25 ! noro 1647: いずれも, 多項式リスト @var{plist} の, 変数順序 @var{vlist}, 項順序型
! 1648: @var{order} に関するグレブナ基底を求める. @code{gr()}, @code{hgr()}
! 1649: は 有理数係数, @code{gr_mod()} は GF(@var{p}) 係数として計算する.
! 1650: @item
! 1651: @var{vlist} は不定元のリスト. @var{vlist} に現れない不定元は,
! 1652: 係数体に属すると見なされる.
! 1653: @item
! 1654: @code{gr()}, trace-lifting (モジュラ演算を用いた高速化) および sugar
! 1655: strategy による計算, @code{hgr()} は trace-lifting および
! 1656: 斉次化による 矯正された sugar strategy による計算を行う.
! 1657: @item
! 1658: @code{dgr()} は, @code{gr()}, @code{hgr()} を
! 1659: 子プロセスリスト @var{procs} の 2 つのプロセスにより同時に計算させ,
! 1660: 先に結果を返した方の結果を返す. 結果は同一であるが, どちらの方法が
! 1661: 高速か一般には不明のため, 実際の経過時間を短縮するのに有効である.
! 1662: @item
! 1663: @code{dgr()} で表示される時間は, この函数が実行されているプロセスでの
! 1664: CPU 時間であり, この函数の場合はほとんど通信のための時間である.
! 1665: @item
! 1666: 多項式リスト @var{plist} の要素が分散表現多項式の場合は
! 1667: 結果も分散表現多項式のリストである.
! 1668: この場合, 引数の分散多項式は与えられた順序に従い @code{dp_sort} で
! 1669: ソートされてから計算される.
! 1670: 多項式リストの要素が分散表現多項式の場合も
! 1671: 変数の数分の不定元のリストを @var{vlist} 引数として与えないといけない
! 1672: (ダミー).
1.2 noro 1673: \E
1674: \BEG
1675: @item
1676: These functions are defined in @samp{gr} in the standard library
1677: directory.
1.21 takayama 1678: @item
1679: Functions of which names contains gr are obsolted.
1680: Functions of @code{nd_gr} families should be used (@fref{nd_gr nd_gr_trace nd_f4 nd_f4_trace nd_weyl_gr nd_weyl_gr_trace}).
1.2 noro 1681: @item
1682: They compute a Groebner basis of a polynomial list @var{plist} with
1683: respect to the variable order @var{vlist} and the order type @var{order}.
1684: @code{gr()} and @code{hgr()} compute a Groebner basis over the rationals
1685: and @code{gr_mod} computes over GF(@var{p}).
1686: @item
1687: Variables not included in @var{vlist} are regarded as
1688: included in the ground field.
1689: @item
1690: @code{gr()} uses trace-lifting (an improvement by modular computation)
1691: and sugar strategy.
1692: @code{hgr()} uses trace-lifting and a cured sugar strategy
1693: by using homogenization.
1694: @item
1695: @code{dgr()} executes @code{gr()}, @code{dgr()} simultaneously on
1696: two process in a child process list @var{procs} and returns
1697: the result obtained first. The results returned from both the process
1698: should be equal, but it is not known in advance which method is faster.
1699: Therefore this function is useful to reduce the actual elapsed time.
1700: @item
1701: The CPU time shown after an exection of @code{dgr()} indicates
1702: that of the master process, and most of the time corresponds to the time
1703: for communication.
1.12 takayama 1704: @item
1705: When the elements of @var{plist} are distributed polynomials,
1706: the result is also a list of distributed polynomials.
1707: In this case, firstly the elements of @var{plist} is sorted by @code{dp_sort}
1708: and the Grobner basis computation is started.
1709: Variables must be given in @var{vlist} even in this case
1710: (these variables are dummy).
1.2 noro 1711: \E
1.1 noro 1712: @end itemize
1713:
1714: @example
1715: [0] load("gr")$
1716: [64] load("cyclic")$
1717: [74] G=gr(cyclic(5),[c0,c1,c2,c3,c4],2);
1718: [c4^15+122*c4^10-122*c4^5-1,...]
1719: [75] GM=gr_mod(cyclic(5),[c0,c1,c2,c3,c4],2,31991)$
1720: 24628*c4^15+29453*c4^10+2538*c4^5+7363
1721: [76] (G[0]*24628-GM[0])%31991;
1722: 0
1723: @end example
1724:
1725: @table @t
1.25 ! noro 1726: \JP @item 参照
1.2 noro 1727: \EG @item References
1.6 noro 1728: @fref{dp_gr_main dp_gr_mod_main dp_gr_f_main dp_weyl_gr_main dp_weyl_gr_mod_main dp_weyl_gr_f_main},
1.1 noro 1729: @fref{dp_ord}.
1730: @end table
1731:
1.25 ! noro 1732: \JP @node lex_hensel lex_tl tolex tolex_d tolex_tl,,, グレブナ基底に関する函数
1.2 noro 1733: \EG @node lex_hensel lex_tl tolex tolex_d tolex_tl,,, Functions for Groebner basis computation
1.1 noro 1734: @subsection @code{lex_hensel}, @code{lex_tl}, @code{tolex}, @code{tolex_d}, @code{tolex_tl}
1735: @findex lex_hensel
1736: @findex lex_tl
1737: @findex tolex
1738: @findex tolex_d
1739: @findex tolex_tl
1740:
1741: @table @t
1742: @item lex_hensel(@var{plist},@var{vlist1},@var{order},@var{vlist2},@var{homo})
1743: @itemx lex_tl(@var{plist},@var{vlist1},@var{order},@var{vlist2},@var{homo})
1.25 ! noro 1744: \JP :: 基底変換による辞書式順序グレブナ基底の計算
1.2 noro 1745: \EG:: Groebner basis computation with respect to a lex order by change of ordering
1.1 noro 1746: @item tolex(@var{plist},@var{vlist1},@var{order},@var{vlist2})
1747: @itemx tolex_d(@var{plist},@var{vlist1},@var{order},@var{vlist2},@var{procs})
1748: @itemx tolex_tl(@var{plist},@var{vlist1},@var{order},@var{vlist2},@var{homo})
1.25 ! noro 1749: \JP :: グレブナ基底を入力とする, 基底変換による辞書式順序グレブナ基底の計算
1.2 noro 1750: \EG :: Groebner basis computation with respect to a lex order by change of ordering, starting from a Groebner basis
1.1 noro 1751: @end table
1752:
1753: @table @var
1754: @item return
1.25 ! noro 1755: \JP リスト
1.2 noro 1756: \EG list
1.4 noro 1757: @item plist vlist1 vlist2 procs
1.25 ! noro 1758: \JP リスト
1.2 noro 1759: \EG list
1.1 noro 1760: @item order
1.25 ! noro 1761: \JP 数, リストまたは行列
1.2 noro 1762: \EG number, list or matrix
1.1 noro 1763: @item homo
1.25 ! noro 1764: \JP フラグ
1.2 noro 1765: \EG flag
1.1 noro 1766: @end table
1767:
1768: @itemize @bullet
1.2 noro 1769: \BJP
1.1 noro 1770: @item
1.25 ! noro 1771: 標準ライブラリの @samp{gr} で定義されている.
1.1 noro 1772: @item
1.25 ! noro 1773: @code{lex_hensel()}, @code{lex_tl()} は,
! 1774: 多項式リスト @var{plist} の, 変数順序 @var{vlist1}, 項順序型
! 1775: @var{order} に関するグレブナ基底を求め, それを, 変数順序 @var{vlist2}
! 1776: の辞書式順序グレブナ基底に変換する.
! 1777: @item
! 1778: @code{tolex()}, @code{tolex_tl()} は,
! 1779: 変数順序 @var{vlist1}, 項順序型 @var{order} に関するグレブナ基底である
! 1780: 多項式リスト @var{plist} を変数順序 @var{vlist2} の辞書式順序グレブナ
! 1781: 基底に変換する.
! 1782: @code{tolex_d()} は, @code{tolex()} における, 各基底の計算を, 子プロセス
! 1783: リスト @var{procs} の各プロセスに分散計算させる.
1.1 noro 1784: @item
1.25 ! noro 1785: @code{lex_hensel()}, @code{lex_tl()} においては, 辞書式順序グレブナ基底の
! 1786: 計算は次のように行われる. (@code{[Noro,Yokoyama]} 参照.)
1.1 noro 1787: @enumerate
1788: @item
1.25 ! noro 1789: @var{vlist1}, @var{order} に関するグレブナ基底 @var{G0} を計算する.
! 1790: (@code{lex_hensel()} のみ. )
1.1 noro 1791: @item
1.25 ! noro 1792: @var{G0} の各元の @var{vlist2} に関する辞書式順序における頭係数を割らない
! 1793: ような素数 @var{p} を選び, GF(@var{p}) 上での辞書式順序グレブナ基底
! 1794: @var{Gp} を計算する.
1.1 noro 1795: @item
1.25 ! noro 1796: @var{Gp} に現れるすべての項の, @var{G0} に関する正規形 @var{NF} を計算する.
1.1 noro 1797: @item
1.25 ! noro 1798: @var{Gp} の各元 @var{f} につき, @var{f} の係数を未定係数で,
! 1799: @var{f} の各項を対応する @var{NF} の元で置き換え, 各項の係数を 0 と置いた,
! 1800: 未定係数に関する線形方程式系 @var{Lf} を作る.
1.1 noro 1801: @item
1.25 ! noro 1802: @var{Lf} が, 法 @var{p} で一意解を持つことを用いて @var{Lf} の解を
! 1803: 法 @var{p}の解から Hensel 構成により求める.
1.1 noro 1804: @item
1.25 ! noro 1805: すべての @var{Gp} の元につき線形方程式が解けたらその解全体が求める
! 1806: 辞書式順序でのグレブナ基底. もしどれかの線形方程式の求解に失敗したら,
! 1807: @var{p} をとり直してやり直す.
1.1 noro 1808: @end enumerate
1809:
1810: @item
1.25 ! noro 1811: @code{lex_tl()}, @code{tolex_tl()} においては, 辞書式順序グレブナ基底の
! 1812: 計算は次のように行われる.
1.1 noro 1813:
1814: @enumerate
1815: @item
1.25 ! noro 1816: @var{vlist1}, @var{order} に関するグレブナ基底 @var{G0} を計算する.
! 1817: (@code{lex_hensel()} のみ. )
1.1 noro 1818: @item
1.25 ! noro 1819: @var{G0} が 0 次元システムでないとき, @var{G0} を入力として,
! 1820: @var{G0} の各元の @var{vlist2} に関する辞書式順序における頭係数を割らない
! 1821: ような素数 @var{p} を選び, @var{p} を用いた trace-lifting により辞書式
! 1822: 順序のグレブナ基底候補を求め, もし求まったならチェックなしにそれが求める
! 1823: グレブナ基底となる. もし失敗したら, @var{p} をとり直してやり直す.
! 1824: @item
! 1825: @var{G0} が 0 次元システムのとき, @var{G0} を入力として,
! 1826: まず, @var{vlist2} の最後の変数以外を消去する消去順序により
! 1827: グレブナ基底 @var{G1} を計算し, それから辞書式順序のグレブナ基底を
! 1828: 計算する. その際, 各ステップでは, 入力の各元の, 求める順序における
! 1829: 頭係数を割らない素数を用いた trace-lifting でグレブナ基底候補を求め,
! 1830: もし求まったらチェックなしにそれがその順序でのグレブナ基底となる.
1.1 noro 1831: @end enumerate
1832:
1833: @item
1.25 ! noro 1834: 有理式係数の計算は, @code{lex_tl()}, @code{tolex_tl()} のみ受け付ける.
1.1 noro 1835: @item
1.25 ! noro 1836: @code{homo} が 0 でない場合, 内部で起動される Buchberger アルゴリズムに
! 1837: おいて, 斉次化が行われる.
1.1 noro 1838: @item
1.25 ! noro 1839: @code{tolex_d()} で表示される時間は, この函数が実行されているプロセスに
! 1840: おいて行われた計算に対応していて, 子プロセスにおける時間は含まれない.
1.2 noro 1841: \E
1842: \BEG
1843: @item
1844: These functions are defined in @samp{gr} in the standard library
1845: directory.
1846: @item
1847: @code{lex_hensel()} and @code{lex_tl()} first compute a Groebner basis
1848: with respect to the variable order @var{vlist1} and the order type @var{order}.
1849: Then the Groebner basis is converted into a lex order Groebner basis
1850: with respect to the varable order @var{vlist2}.
1851: @item
1852: @code{tolex()} and @code{tolex_tl()} convert a Groebner basis @var{plist}
1853: with respect to the variable order @var{vlist1} and the order type @var{order}
1854: into a lex order Groebner basis
1855: with respect to the varable order @var{vlist2}.
1856: @code{tolex_d()} does computations of basis elements in @code{tolex()}
1857: in parallel on the processes in a child process list @var{procs}.
1858: @item
1859: In @code{lex_hensel()} and @code{tolex_hensel()} a lex order Groebner basis
1860: is computed as follows.(Refer to @code{[Noro,Yokoyama]}.)
1861: @enumerate
1862: @item
1863: Compute a Groebner basis @var{G0} with respect to @var{vlist1} and @var{order}.
1864: (Only in @code{lex_hensel()}. )
1865: @item
1866: Choose a prime which does not divide head coefficients of elements in @var{G0}
1867: with respect to @var{vlist1} and @var{order}. Then compute a lex order
1868: Groebner basis @var{Gp} over GF(@var{p}) with respect to @var{vlist2}.
1869: @item
1870: Compute @var{NF}, the set of all the normal forms with respect to
1871: @var{G0} of terms appearing in @var{Gp}.
1872: @item
1873: For each element @var{f} in @var{Gp}, replace coefficients and terms in @var{f}
1874: with undetermined coefficients and the corresponding polynomials in @var{NF}
1875: respectively, and generate a system of liear equation @var{Lf} by equating
1876: the coefficients of terms in the replaced polynomial with 0.
1877: @item
1878: Solve @var{Lf} by Hensel lifting, starting from the unique mod @var{p}
1879: solution.
1880: @item
1881: If all the linear equations generated from the elements in @var{Gp}
1882: could be solved, then the set of solutions corresponds to a lex order
1883: Groebner basis. Otherwise redo the whole process with another @var{p}.
1884: @end enumerate
1885:
1886: @item
1887: In @code{lex_tl()} and @code{tolex_tl()} a lex order Groebner basis
1888: is computed as follows.(Refer to @code{[Noro,Yokoyama]}.)
1889:
1890: @enumerate
1891: @item
1892: Compute a Groebner basis @var{G0} with respect to @var{vlist1} and @var{order}.
1893: (Only in @code{lex_tl()}. )
1894: @item
1895: If @var{G0} is not zero-dimensional, choose a prime which does not divide
1896: head coefficients of elements in @var{G0} with respect to @var{vlist1} and
1897: @var{order}. Then compute a candidate of a lex order Groebner basis
1898: via trace lifting with @var{p}. If it succeeds the candidate is indeed
1899: a lex order Groebner basis without any check. Otherwise redo the whole
1900: process with another @var{p}.
1901: @item
1902:
1903: If @var{G0} is zero-dimensional, starting from @var{G0},
1904: compute a Groebner basis @var{G1} with respect to an elimination order
1905: to eliminate variables other than the last varibale in @var{vlist2}.
1906: Then compute a lex order Groebner basis stating from @var{G1}. These
1907: computations are done by trace lifting and the selection of a mudulus
1908: @var{p} is the same as in non zero-dimensional cases.
1909: @end enumerate
1910:
1911: @item
1912: Computations with rational function coefficients can be done only by
1913: @code{lex_tl()} and @code{tolex_tl()}.
1914: @item
1915: If @code{homo} is not equal to 0, homogenization is used in Buchberger
1916: algorithm.
1917: @item
1918: The CPU time shown after an execution of @code{tolex_d()} indicates
1919: that of the master process, and it does not include the time in child
1920: processes.
1921: \E
1.1 noro 1922: @end itemize
1923:
1924: @example
1925: [78] K=katsura(5)$
1926: 30msec + gc : 20msec
1927: [79] V=[u5,u4,u3,u2,u1,u0]$
1928: 0msec
1929: [80] G0=hgr(K,V,2)$
1930: 91.558sec + gc : 15.583sec
1931: [81] G1=lex_hensel(K,V,0,V,0)$
1932: 49.049sec + gc : 9.961sec
1933: [82] G2=lex_tl(K,V,0,V,1)$
1934: 31.186sec + gc : 3.500sec
1935: [83] gb_comp(G0,G1);
1936: 1
1937: 10msec
1938: [84] gb_comp(G0,G2);
1939: 1
1940: @end example
1941:
1942: @table @t
1.25 ! noro 1943: \JP @item 参照
1.2 noro 1944: \EG @item References
1.6 noro 1945: @fref{dp_gr_main dp_gr_mod_main dp_gr_f_main dp_weyl_gr_main dp_weyl_gr_mod_main dp_weyl_gr_f_main},
1.25 ! noro 1946: \JP @fref{dp_ord}, @fref{分散計算}
1.2 noro 1947: \EG @fref{dp_ord}, @fref{Distributed computation}
1.1 noro 1948: @end table
1949:
1.25 ! noro 1950: \JP @node lex_hensel_gsl tolex_gsl tolex_gsl_d,,, グレブナ基底に関する函数
1.2 noro 1951: \EG @node lex_hensel_gsl tolex_gsl tolex_gsl_d,,, Functions for Groebner basis computation
1.1 noro 1952: @subsection @code{lex_hensel_gsl}, @code{tolex_gsl}, @code{tolex_gsl_d}
1953: @findex lex_hensel_gsl
1954: @findex tolex_gsl
1955: @findex tolex_gsl_d
1956:
1957: @table @t
1958: @item lex_hensel_gsl(@var{plist},@var{vlist1},@var{order},@var{vlist2},@var{homo})
1.25 ! noro 1959: \JP :: GSL 形式のイデアル基底の計算
1.2 noro 1960: \EG ::Computation of an GSL form ideal basis
1.8 noro 1961: @item tolex_gsl(@var{plist},@var{vlist1},@var{order},@var{vlist2})
1962: @itemx tolex_gsl_d(@var{plist},@var{vlist1},@var{order},@var{vlist2},@var{procs})
1.25 ! noro 1963: \JP :: グレブナ基底を入力とする, GSL 形式のイデアル基底の計算
1.2 noro 1964: \EG :: Computation of an GSL form ideal basis stating from a Groebner basis
1.1 noro 1965: @end table
1966:
1967: @table @var
1968: @item return
1.25 ! noro 1969: \JP リスト
1.2 noro 1970: \EG list
1.4 noro 1971: @item plist vlist1 vlist2 procs
1.25 ! noro 1972: \JP リスト
1.2 noro 1973: \EG list
1.1 noro 1974: @item order
1.25 ! noro 1975: \JP 数, リストまたは行列
1.2 noro 1976: \EG number, list or matrix
1.1 noro 1977: @item homo
1.25 ! noro 1978: \JP フラグ
1.2 noro 1979: \EG flag
1.1 noro 1980: @end table
1981:
1982: @itemize @bullet
1.2 noro 1983: \BJP
1.1 noro 1984: @item
1.25 ! noro 1985: @code{lex_hensel_gsl()} は @code{lex_hensel()} の, @code{tolex_gsl()} は
! 1986: @code{tolex()} の変種で, 結果のみが異なる.
! 1987: @code{tolex_gsl_d()} は, 基底計算を, @code{procs} で指定される子プロセスに
! 1988: 分散計算させる.
! 1989: @item
! 1990: 入力が 0 次元システムで, その辞書式順序グレブナ基底が
! 1991: @code{[f0,x1-f1,...,xn-fn]} (@code{f0},...,@code{fn} は
! 1992: @code{x0} の 1 変数多項式) なる形 (これを SL 形式と呼ぶ) を持つ場合,
! 1993: @code{[[x1,g1,d1],...,[xn,gn,dn],[x0,f0,f0']]} なるリスト (これを GSL 形式と呼ぶ)
! 1994: を返す.
! 1995: ここで, @code{gi} は, @code{di*f0'*fi-gi} が @code{f0} で割り切れるような
! 1996: @code{x0} の1 変数多項式で,
! 1997: 解は @code{f0(x0)=0} なる @code{x0} に対し, @code{[x1=g1/(d1*f0'),...,xn=gn/(dn*f0')]}
! 1998: となる. 辞書式順序グレブナ基底が上のような形でない場合, @code{tolex()} に
! 1999: よる通常のグレブナ基底を返す.
! 2000: @item
! 2001: GSL 形式により表される基底はグレブナ基底ではないが, 一般に係数が SL 形式
! 2002: のグレブナ基底より非常に小さいため計算も速く, 解も求めやすい.
! 2003: @code{tolex_gsl_d()} で表示される時間は, この函数が実行されているプロセスに
! 2004: おいて行われた計算に対応していて, 子プロセスにおける時間は含まれない.
1.2 noro 2005: \E
2006: \BEG
2007: @item
2008: @code{lex_hensel_gsl()} and @code{lex_hensel()} are variants of
2009: @code{tolex_gsl()} and @code{tolex()} respectively. The results are
2010: Groebner basis or a kind of ideal basis, called GSL form.
2011: @code{tolex_gsl_d()} does basis computations in parallel on child
2012: processes specified in @code{procs}.
2013:
2014: @item
2015: If the input is zero-dimensional and a lex order Groebner basis has
2016: the form @code{[f0,x1-f1,...,xn-fn]} (@code{f0},...,@code{fn} are
2017: univariate polynomials of @code{x0}; SL form), then this these
2018: functions return a list such as
2019: @code{[[x1,g1,d1],...,[xn,gn,dn],[x0,f0,f0']]} (GSL form). In this list
2020: @code{gi} is a univariate polynomial of @code{x0} such that
2021: @code{di*f0'*fi-gi} divides @code{f0} and the roots of the input ideal is
2022: @code{[x1=g1/(d1*f0'),...,xn=gn/(dn*f0')]} for @code{x0}
2023: such that @code{f0(x0)=0}.
2024: If the lex order Groebner basis does not have the above form,
2025: these functions return
2026: a lex order Groebner basis computed by @code{tolex()}.
2027: @item
2028: Though an ideal basis represented as GSL form is not a Groebner basis
2029: we can expect that the coefficients are much smaller than those in a Groebner
2030: basis and that the computation is efficient.
2031: The CPU time shown after an execution of @code{tolex_gsl_d()} indicates
2032: that of the master process, and it does not include the time in child
2033: processes.
2034: \E
1.1 noro 2035: @end itemize
2036:
2037: @example
2038: [103] K=katsura(5)$
2039: [104] V=[u5,u4,u3,u2,u1,u0]$
2040: [105] G0=gr(K,V,0)$
2041: [106] GSL=tolex_gsl(G0,V,0,V)$
2042: [107] GSL[0];
2043: [u1,8635837421130477667200000000*u0^31-...]
2044: [108] GSL[1];
2045: [u2,10352277157007342793600000000*u0^31-...]
2046: [109] GSL[5];
1.5 noro 2047: [u0,11771021876193064124640000000*u0^32-...,
2048: 376672700038178051988480000000*u0^31-...]
1.1 noro 2049: @end example
2050:
2051: @table @t
1.25 ! noro 2052: \JP @item 参照
1.2 noro 2053: \EG @item References
1.1 noro 2054: @fref{lex_hensel lex_tl tolex tolex_d tolex_tl},
1.25 ! noro 2055: \JP @fref{分散計算}
1.2 noro 2056: \EG @fref{Distributed computation}
1.1 noro 2057: @end table
2058:
1.25 ! noro 2059: \JP @node gr_minipoly minipoly,,, グレブナ基底に関する函数
1.2 noro 2060: \EG @node gr_minipoly minipoly,,, Functions for Groebner basis computation
1.1 noro 2061: @subsection @code{gr_minipoly}, @code{minipoly}
2062: @findex gr_minipoly
2063: @findex minipoly
2064:
2065: @table @t
2066: @item gr_minipoly(@var{plist},@var{vlist},@var{order},@var{poly},@var{v},@var{homo})
1.25 ! noro 2067: \JP :: 多項式の, イデアルを法とした最小多項式の計算
1.2 noro 2068: \EG :: Computation of the minimal polynomial of a polynomial modulo an ideal
1.1 noro 2069: @item minipoly(@var{plist},@var{vlist},@var{order},@var{poly},@var{v})
1.25 ! noro 2070: \JP :: グレブナ基底を入力とする, 多項式の最小多項式の計算
1.2 noro 2071: \EG :: Computation of the minimal polynomial of a polynomial modulo an ideal
1.1 noro 2072: @end table
2073:
2074: @table @var
2075: @item return
1.25 ! noro 2076: \JP 多項式
1.2 noro 2077: \EG polynomial
1.4 noro 2078: @item plist vlist
1.25 ! noro 2079: \JP リスト
1.2 noro 2080: \EG list
1.1 noro 2081: @item order
1.25 ! noro 2082: \JP 数, リストまたは行列
1.2 noro 2083: \EG number, list or matrix
1.1 noro 2084: @item poly
1.25 ! noro 2085: \JP 多項式
1.2 noro 2086: \EG polynomial
1.1 noro 2087: @item v
1.25 ! noro 2088: \JP 不定元
1.2 noro 2089: \EG indeterminate
1.1 noro 2090: @item homo
1.25 ! noro 2091: \JP フラグ
1.2 noro 2092: \EG flag
1.1 noro 2093: @end table
2094:
2095: @itemize @bullet
1.2 noro 2096: \BJP
1.1 noro 2097: @item
1.25 ! noro 2098: @code{gr_minipoly()} はグレブナ基底の計算から行い, @code{minipoly()} は
! 2099: 入力をグレブナ基底とみなす.
1.1 noro 2100: @item
1.25 ! noro 2101: イデアル I が体 K 上の多項式環 K[X] の 0 次元イデアルの時,
! 2102: K[@var{v}] の元 f(@var{v}) に f(@var{p}) mod I を対応させる
! 2103: 環準同型の核は 0 でない多項式により生成される. この生成元を @var{p}
! 2104: の, 法 @var{I} での最小多項式と呼ぶ.
! 2105: @item
! 2106: @code{gr_minipoly()}, @code{minipoly()} は, 多項式 @var{p} の最小多項式
! 2107: を求め, @var{v} を変数とする多項式として返す.
! 2108: @item
! 2109: 最小多項式は, グレブナ基底の 1 つの元として計算することもできるが,
! 2110: 最小多項式のみを求めたい場合, @code{minipoly()}, @code{gr_minipoly()} は
! 2111: グレブナ基底を用いる方法に比べて効率がよい.
1.1 noro 2112: @item
1.25 ! noro 2113: @code{gr_minipoly()} に指定する項順序としては, 通常全次数逆辞書式順序を
! 2114: 用いる.
1.2 noro 2115: \E
2116: \BEG
2117: @item
2118: @code{gr_minipoly()} begins by computing a Groebner basis.
2119: @code{minipoly()} regards an input as a Groebner basis with respect to
2120: the variable order @var{vlist} and the order type @var{order}.
2121: @item
2122: Let K be a field. If an ideal @var{I} in K[X] is zero-dimensional, then, for
2123: a polynomial @var{p} in K[X], the kernel of a homomorphism from
2124: K[@var{v}] to K[X]/@var{I} which maps f(@var{v}) to f(@var{p}) mod @var{I}
2125: is generated by a polynomial. The generator is called the minimal polynomial
2126: of @var{p} modulo @var{I}.
2127: @item
2128: @code{gr_minipoly()} and @code{minipoly()} computes the minimal polynomial
2129: of a polynomial @var{p} and returns it as a polynomial of @var{v}.
2130: @item
2131: The minimal polynomial can be computed as an element of a Groebner basis.
2132: But if we are only interested in the minimal polynomial,
2133: @code{minipoly()} and @code{gr_minipoly()} can compute it more efficiently
2134: than methods using Groebner basis computation.
2135: @item
2136: It is recommended to use a degree reverse lex order as a term order
2137: for @code{gr_minipoly()}.
2138: \E
1.1 noro 2139: @end itemize
2140:
2141: @example
2142: [117] G=tolex(G0,V,0,V)$
2143: 43.818sec + gc : 11.202sec
2144: [118] GSL=tolex_gsl(G0,V,0,V)$
2145: 17.123sec + gc : 2.590sec
2146: [119] MP=minipoly(G0,V,0,u0,z)$
2147: 4.370sec + gc : 780msec
2148: @end example
2149:
2150: @table @t
1.25 ! noro 2151: \JP @item 参照
1.2 noro 2152: \EG @item References
1.1 noro 2153: @fref{lex_hensel lex_tl tolex tolex_d tolex_tl}.
2154: @end table
2155:
1.25 ! noro 2156: \JP @node tolexm minipolym,,, グレブナ基底に関する函数
1.2 noro 2157: \EG @node tolexm minipolym,,, Functions for Groebner basis computation
1.1 noro 2158: @subsection @code{tolexm}, @code{minipolym}
2159: @findex tolexm
2160: @findex minipolym
2161:
2162: @table @t
2163: @item tolexm(@var{plist},@var{vlist1},@var{order},@var{vlist2},@var{mod})
1.25 ! noro 2164: \JP :: 法 @var{mod} での基底変換によるグレブナ基底計算
1.2 noro 2165: \EG :: Groebner basis computation modulo @var{mod} by change of ordering.
1.1 noro 2166: @item minipolym(@var{plist},@var{vlist1},@var{order},@var{poly},@var{v},@var{mod})
1.25 ! noro 2167: \JP :: 法 @var{mod} でのグレブナ基底による多項式の最小多項式の計算
1.2 noro 2168: \EG :: Minimal polynomial computation modulo @var{mod} the same method as
1.1 noro 2169: @end table
2170:
2171: @table @var
2172: @item return
1.25 ! noro 2173: \JP @code{tolexm()} : リスト, @code{minipolym()} : 多項式
1.2 noro 2174: \EG @code{tolexm()} : list, @code{minipolym()} : polynomial
1.4 noro 2175: @item plist vlist1 vlist2
1.25 ! noro 2176: \JP リスト
1.2 noro 2177: \EG list
1.1 noro 2178: @item order
1.25 ! noro 2179: \JP 数, リストまたは行列
1.2 noro 2180: \EG number, list or matrix
1.1 noro 2181: @item mod
1.25 ! noro 2182: \JP 素数
1.2 noro 2183: \EG prime
1.1 noro 2184: @end table
2185:
2186: @itemize @bullet
1.2 noro 2187: \BJP
1.1 noro 2188: @item
1.25 ! noro 2189: 入力 @var{plist} はいずれも 変数順序 @var{vlist1}, 項順序型 @var{order},
! 2190: 法 @var{mod} におけるグレブナ基底でなければならない.
1.1 noro 2191: @item
1.25 ! noro 2192: @code{minipolym()} は @code{minipoly} に対応する計算を法 @var{mod}で行う.
1.1 noro 2193: @item
1.25 ! noro 2194: @code{tolexm()} は FGLM 法による基底変換により @var{vlist2},
! 2195: 辞書式順序によるグレブナ基底を計算する.
1.2 noro 2196: \E
2197: \BEG
2198: @item
2199: An input @var{plist} must be a Groebner basis modulo @var{mod}
2200: with respect to the variable order @var{vlist1} and the order type @var{order}.
2201: @item
2202: @code{minipolym()} executes the same computation as in @code{minipoly}.
2203: @item
2204: @code{tolexm()} computes a lex order Groebner basis modulo @var{mod}
2205: with respect to the variable order @var{vlist2}, by using FGLM algorithm.
2206: \E
1.1 noro 2207: @end itemize
2208:
2209: @example
2210: [197] tolexm(G0,V,0,V,31991);
2211: [8271*u0^31+10435*u0^30+816*u0^29+26809*u0^28+...,...]
2212: [198] minipolym(G0,V,0,u0,z,31991);
2213: z^32+11405*z^31+20868*z^30+21602*z^29+...
2214: @end example
2215:
2216: @table @t
1.25 ! noro 2217: \JP @item 参照
1.2 noro 2218: \EG @item References
1.1 noro 2219: @fref{lex_hensel lex_tl tolex tolex_d tolex_tl},
2220: @fref{gr_minipoly minipoly}.
2221: @end table
2222:
1.25 ! noro 2223: \JP @node dp_gr_main dp_gr_mod_main dp_gr_f_main dp_weyl_gr_main dp_weyl_gr_mod_main dp_weyl_gr_f_main,,, グレブナ基底に関する函数
1.6 noro 2224: \EG @node dp_gr_main dp_gr_mod_main dp_gr_f_main dp_weyl_gr_main dp_weyl_gr_mod_main dp_weyl_gr_f_main,,, Functions for Groebner basis computation
2225: @subsection @code{dp_gr_main}, @code{dp_gr_mod_main}, @code{dp_gr_f_main}, @code{dp_weyl_gr_main}, @code{dp_weyl_gr_mod_main}, @code{dp_weyl_gr_f_main}
1.1 noro 2226: @findex dp_gr_main
2227: @findex dp_gr_mod_main
1.5 noro 2228: @findex dp_gr_f_main
1.6 noro 2229: @findex dp_weyl_gr_main
2230: @findex dp_weyl_gr_mod_main
2231: @findex dp_weyl_gr_f_main
1.1 noro 2232:
2233: @table @t
2234: @item dp_gr_main(@var{plist},@var{vlist},@var{homo},@var{modular},@var{order})
2235: @itemx dp_gr_mod_main(@var{plist},@var{vlist},@var{homo},@var{modular},@var{order})
1.5 noro 2236: @itemx dp_gr_f_main(@var{plist},@var{vlist},@var{homo},@var{order})
1.6 noro 2237: @itemx dp_weyl_gr_main(@var{plist},@var{vlist},@var{homo},@var{modular},@var{order})
2238: @itemx dp_weyl_gr_mod_main(@var{plist},@var{vlist},@var{homo},@var{modular},@var{order})
2239: @itemx dp_weyl_gr_f_main(@var{plist},@var{vlist},@var{homo},@var{order})
1.25 ! noro 2240: \JP :: グレブナ基底の計算 (組み込み函数)
1.2 noro 2241: \EG :: Groebner basis computation (built-in functions)
1.1 noro 2242: @end table
2243:
2244: @table @var
2245: @item return
1.25 ! noro 2246: \JP リスト
1.2 noro 2247: \EG list
1.4 noro 2248: @item plist vlist
1.25 ! noro 2249: \JP リスト
1.2 noro 2250: \EG list
1.1 noro 2251: @item order
1.25 ! noro 2252: \JP 数, リストまたは行列
1.2 noro 2253: \EG number, list or matrix
1.1 noro 2254: @item homo
1.25 ! noro 2255: \JP フラグ
1.2 noro 2256: \EG flag
1.1 noro 2257: @item modular
1.25 ! noro 2258: \JP フラグまたは素数
1.2 noro 2259: \EG flag or prime
1.1 noro 2260: @end table
2261:
2262: @itemize @bullet
1.2 noro 2263: \BJP
1.1 noro 2264: @item
1.25 ! noro 2265: これらの函数は, グレブナ基底計算の基本的組み込み函数であり, @code{gr()},
! 2266: @code{hgr()}, @code{gr_mod()} などはすべてこれらの函数を呼び出して計算
! 2267: を行っている. 関数名に weyl が入っているものは, Weyl 代数上の計算
! 2268: のための関数である.
! 2269: @item
! 2270: @code{dp_gr_f_main()}, @code{dp_weyl_f_main()} は, 種々の有限体上のグレブナ基底を計算する
! 2271: 場合に用いる. 入力は, あらかじめ, @code{simp_ff()} などで,
! 2272: 考える有限体上に射影されている必要がある.
! 2273: @item
! 2274: フラグ @var{homo} が 0 でない時, 入力を斉次化してから Buchberger アルゴリズム
! 2275: を実行する.
! 2276: @item
! 2277: @code{dp_gr_mod_main()} に対しては, @var{modular} は, GF(@var{modular}) 上
! 2278: での計算を意味する.
! 2279: @code{dp_gr_main()} に対しては, @var{modular} は次のような意味を持つ.
1.1 noro 2280: @enumerate
2281: @item
1.25 ! noro 2282: @var{modular} が 1 の時, trace-lifting による計算を行う. 素数は
! 2283: @code{lprime(0)} から順に成功するまで @code{lprime()} を呼び出して生成する.
1.1 noro 2284: @item
1.25 ! noro 2285: @var{modular} が 2 以上の自然数の時, その値を素数とみなして trace-lifting
! 2286: を行う. その素数で失敗した場合, 0 を返す.
1.1 noro 2287: @item
1.25 ! noro 2288: @var{modular} が負の場合,
! 2289: @var{-modular} に対して上述の規則が適用されるが, trace-lifting の最終
! 2290: 段階のグレブナ基底チェックとイデアルメンバシップチェックが省略される.
1.1 noro 2291: @end enumerate
2292:
2293: @item
1.25 ! noro 2294: @code{gr(P,V,O)} は @code{dp_gr_main(P,V,0,1,O)}, @code{hgr(P,V,O)} は
! 2295: @code{dp_gr_main(P,V,1,1,O)}, @code{gr_mod(P,V,O,M)} は
! 2296: @code{dp_gr_mod_main(P,V,0,M,O)} をそれぞれ実行する.
1.1 noro 2297: @item
1.25 ! noro 2298: @var{homo}, @var{modular} の他に, @code{dp_gr_flags()} で設定される
! 2299: さまざまなフラグにより計算が制御される.
1.2 noro 2300: \E
2301: \BEG
2302: @item
2303: These functions are fundamental built-in functions for Groebner basis
2304: computation and @code{gr()},@code{hgr()} and @code{gr_mod()}
1.6 noro 2305: are all interfaces to these functions. Functions whose names
2306: contain weyl are those for computation in Weyl algebra.
1.2 noro 2307: @item
1.6 noro 2308: @code{dp_gr_f_main()} and @code{dp_weyl_gr_f_main()}
2309: are functions for Groebner basis computation
1.5 noro 2310: over various finite fields. Coefficients of input polynomials
2311: must be converted to elements of a finite field
2312: currently specified by @code{setmod_ff()}.
2313: @item
1.2 noro 2314: If @var{homo} is not equal to 0, homogenization is applied before entering
2315: Buchberger algorithm
2316: @item
2317: For @code{dp_gr_mod_main()}, @var{modular} means a computation over
2318: GF(@var{modular}).
2319: For @code{dp_gr_main()}, @var{modular} has the following mean.
2320: @enumerate
2321: @item
2322: If @var{modular} is 1 , trace lifting is used. Primes for trace lifting
2323: are generated by @code{lprime()}, starting from @code{lprime(0)}, until
2324: the computation succeeds.
2325: @item
2326: If @var{modular} is an integer greater than 1, the integer is regarded as a
2327: prime and trace lifting is executed by using the prime. If the computation
2328: fails then 0 is returned.
2329: @item
2330: If @var{modular} is negative, the above rule is applied for @var{-modular}
2331: but the Groebner basis check and ideal-membership check are omitted in
2332: the last stage of trace lifting.
2333: @end enumerate
2334:
2335: @item
2336: @code{gr(P,V,O)}, @code{hgr(P,V,O)} and @code{gr_mod(P,V,O,M)} execute
2337: @code{dp_gr_main(P,V,0,1,O)}, @code{dp_gr_main(P,V,1,1,O)}
2338: and @code{dp_gr_mod_main(P,V,0,M,O)} respectively.
2339: @item
2340: Actual computation is controlled by various parameters set by
2341: @code{dp_gr_flags()}, other then by @var{homo} and @var{modular}.
2342: \E
1.1 noro 2343: @end itemize
2344:
2345: @table @t
1.25 ! noro 2346: \JP @item 参照
1.2 noro 2347: \EG @item References
1.1 noro 2348: @fref{dp_ord},
2349: @fref{dp_gr_flags dp_gr_print},
2350: @fref{gr hgr gr_mod},
1.5 noro 2351: @fref{setmod_ff},
1.25 ! noro 2352: \JP @fref{計算および表示の制御}.
1.2 noro 2353: \EG @fref{Controlling Groebner basis computations}
1.1 noro 2354: @end table
2355:
1.25 ! noro 2356: \JP @node dp_f4_main dp_f4_mod_main dp_weyl_f4_main dp_weyl_f4_mod_main,,, グレブナ基底に関する函数
1.6 noro 2357: \EG @node dp_f4_main dp_f4_mod_main dp_weyl_f4_main dp_weyl_f4_mod_main,,, Functions for Groebner basis computation
2358: @subsection @code{dp_f4_main}, @code{dp_f4_mod_main}, @code{dp_weyl_f4_main}, @code{dp_weyl_f4_mod_main}
1.1 noro 2359: @findex dp_f4_main
2360: @findex dp_f4_mod_main
1.6 noro 2361: @findex dp_weyl_f4_main
2362: @findex dp_weyl_f4_mod_main
1.1 noro 2363:
2364: @table @t
2365: @item dp_f4_main(@var{plist},@var{vlist},@var{order})
2366: @itemx dp_f4_mod_main(@var{plist},@var{vlist},@var{order})
1.6 noro 2367: @itemx dp_weyl_f4_main(@var{plist},@var{vlist},@var{order})
2368: @itemx dp_weyl_f4_mod_main(@var{plist},@var{vlist},@var{order})
1.25 ! noro 2369: \JP :: F4 アルゴリズムによるグレブナ基底の計算 (組み込み函数)
1.2 noro 2370: \EG :: Groebner basis computation by F4 algorithm (built-in functions)
1.1 noro 2371: @end table
2372:
2373: @table @var
2374: @item return
1.25 ! noro 2375: \JP リスト
1.2 noro 2376: \EG list
1.4 noro 2377: @item plist vlist
1.25 ! noro 2378: \JP リスト
1.2 noro 2379: \EG list
1.1 noro 2380: @item order
1.25 ! noro 2381: \JP 数, リストまたは行列
1.2 noro 2382: \EG number, list or matrix
1.1 noro 2383: @end table
2384:
2385: @itemize @bullet
1.2 noro 2386: \BJP
1.1 noro 2387: @item
1.25 ! noro 2388: F4 アルゴリズムによりグレブナ基底の計算を行う.
1.1 noro 2389: @item
1.25 ! noro 2390: F4 アルゴリズムは, J.C. Faugere により提唱された新世代グレブナ基底
! 2391: 算法であり, 本実装は, 中国剰余定理による線形方程式求解を用いた
! 2392: 試験的な実装である.
1.1 noro 2393: @item
1.25 ! noro 2394: 斉次化の引数がないことを除けば, 引数および動作はそれぞれ
1.6 noro 2395: @code{dp_gr_main()}, @code{dp_gr_mod_main()},
2396: @code{dp_weyl_gr_main()}, @code{dp_weyl_gr_mod_main()}
1.25 ! noro 2397: と同様である.
1.2 noro 2398: \E
2399: \BEG
2400: @item
2401: These functions compute Groebner bases by F4 algorithm.
2402: @item
2403: F4 is a new generation algorithm for Groebner basis computation
2404: invented by J.C. Faugere. The current implementation of @code{dp_f4_main()}
2405: uses Chinese Remainder theorem and not highly optimized.
2406: @item
2407: Arguments and actions are the same as those of
1.6 noro 2408: @code{dp_gr_main()}, @code{dp_gr_mod_main()},
2409: @code{dp_weyl_gr_main()}, @code{dp_weyl_gr_mod_main()},
2410: except for lack of the argument for controlling homogenization.
1.2 noro 2411: \E
1.1 noro 2412: @end itemize
2413:
2414: @table @t
1.25 ! noro 2415: \JP @item 参照
1.2 noro 2416: \EG @item References
1.1 noro 2417: @fref{dp_ord},
2418: @fref{dp_gr_flags dp_gr_print},
2419: @fref{gr hgr gr_mod},
1.25 ! noro 2420: \JP @fref{計算および表示の制御}.
1.15 noro 2421: \EG @fref{Controlling Groebner basis computations}
2422: @end table
2423:
1.25 ! noro 2424: \JP @node nd_gr nd_gr_trace nd_f4 nd_f4_trace nd_weyl_gr nd_weyl_gr_trace,,, グレブナ基底に関する函数
1.17 noro 2425: \EG @node nd_gr nd_gr_trace nd_f4 nd_f4_trace nd_weyl_gr nd_weyl_gr_trace,,, Functions for Groebner basis computation
2426: @subsection @code{nd_gr}, @code{nd_gr_trace}, @code{nd_f4}, @code{nd_f4_trace}, @code{nd_weyl_gr}, @code{nd_weyl_gr_trace}
1.15 noro 2427: @findex nd_gr
2428: @findex nd_gr_trace
2429: @findex nd_f4
1.17 noro 2430: @findex nd_f4_trace
1.15 noro 2431: @findex nd_weyl_gr
2432: @findex nd_weyl_gr_trace
2433:
2434: @table @t
1.23 noro 2435: @item nd_gr(@var{plist},@var{vlist},@var{p},@var{order}[|@var{option=value,...}])
2436: @itemx nd_gr_trace(@var{plist},@var{vlist},@var{homo},@var{p},@var{order}[|@var{option=value,...}])
2437: @itemx nd_f4(@var{plist},@var{vlist},@var{modular},@var{order}[|@var{option=value,...}])
2438: @itemx nd_f4_trace(@var{plist},@var{vlist},@var{homo},@var{p},@var{order}[|@var{option=value,...}])
2439: @itemx nd_weyl_gr(@var{plist},@var{vlist},@var{p},@var{order}[|@var{option=value,...}])
2440: @itemx nd_weyl_gr_trace(@var{plist},@var{vlist},@var{homo},@var{p},@var{order}[|@var{option=value,...}])
1.25 ! noro 2441: \JP :: グレブナ基底の計算 (組み込み函数)
1.15 noro 2442: \EG :: Groebner basis computation (built-in functions)
2443: @end table
2444:
2445: @table @var
2446: @item return
1.25 ! noro 2447: \JP リスト
1.15 noro 2448: \EG list
2449: @item plist vlist
1.25 ! noro 2450: \JP リスト
1.15 noro 2451: \EG list
2452: @item order
1.25 ! noro 2453: \JP 数, リストまたは行列
1.15 noro 2454: \EG number, list or matrix
2455: @item homo
1.25 ! noro 2456: \JP フラグ
1.15 noro 2457: \EG flag
2458: @item modular
1.25 ! noro 2459: \JP フラグまたは素数
1.15 noro 2460: \EG flag or prime
2461: @end table
2462:
2463: \BJP
2464: @itemize @bullet
2465: @item
1.25 ! noro 2466: これらの函数は, グレブナ基底計算組み込み関数の新実装である.
! 2467: @item @code{nd_gr} は, @code{p} が 0 のとき有理数体上の Buchberger
! 2468: アルゴリズムを実行する. @code{p} が 2 以上の自然数のとき, GF(p) 上の
! 2469: Buchberger アルゴリズムを実行する.
! 2470: @item @code{nd_gr_trace} および @code{nd_f4_trace}
! 2471: は有理数体上で trace アルゴリズムを実行する.
! 2472: @var{p} が 0 または 1 のとき, 自動的に選ばれた素数を用いて, 成功する
! 2473: まで trace アルゴリズムを実行する.
! 2474: @var{p} が 2 以上のとき, trace はGF(p) 上で計算される. trace アルゴリズム
! 2475: が失敗した場合 0 が返される. @var{p} が負の場合, グレブナ基底チェックは
! 2476: 行わない. この場合, @var{p} が -1 ならば自動的に選ばれた素数が,
! 2477: それ以外は指定された素数を用いてグレブナ基底候補の計算が行われる.
! 2478: @code{nd_f4_trace} は, 各全次数について, ある有限体上で F4 アルゴリズム
! 2479: で行った結果をもとに, その有限体上で 0 でない基底を与える S-多項式のみを
! 2480: 用いて行列生成を行い, その全次数における基底を生成する方法である. 得られる
! 2481: 多項式集合はやはりグレブナ基底候補であり, @code{nd_gr_trace} と同様の
! 2482: チェックが行われる.
! 2483: @item
! 2484: @code{nd_f4} は @code{modular} が 0 のとき有理数体上の, @code{modular} が
! 2485: マシンサイズ素数のとき有限体上の F4 アルゴリズムを実行する.
! 2486: @item
! 2487: @var{plist} が多項式リストの場合, @var{plist}で生成されるイデアルのグレブナー基底が
! 2488: 計算される. @var{plist} が多項式リストのリストの場合, 各要素は多項式環上の自由加群の元と見なされ,
! 2489: これらが生成する部分加群のグレブナー基底が計算される. 後者の場合, 項順序は加群に対する項順序を
! 2490: 指定する必要がある. これは @var{[s,ord]} の形で指定する. @var{s} が 0 ならば TOP (Term Over Position),
! 2491: 1 ならば POT (Position Over Term) を意味し, @var{ord} は多項式環の単項式に対する項順序である.
1.18 noro 2492: @item
1.25 ! noro 2493: @code{nd_weyl_gr}, @code{nd_weyl_gr_trace} は Weyl 代数用である.
1.15 noro 2494: @item
1.25 ! noro 2495: @code{f4} 系関数以外はすべて有理関数係数の計算が可能である.
1.15 noro 2496: @item
1.25 ! noro 2497: 一般に @code{dp_gr_main}, @code{dp_gr_mod_main} より高速であるが,
! 2498: 特に有限体上の場合顕著である.
1.23 noro 2499: @item
1.25 ! noro 2500: 以下のオプションが指定できる.
1.23 noro 2501: @table @code
2502: @item homo
1.25 ! noro 2503: 1 のとき, 斉次化を経由して計算する. (@code{nd_gr}, @code{nd_f4} のみ)
1.23 noro 2504: @item dp
1.25 ! noro 2505: 1 のとき, 分散表現多項式 (加群の場合には加群多項式) を結果として返す.
1.23 noro 2506: @item nora
1.25 ! noro 2507: 1 のとき, 結果の相互簡約を行わない.
1.23 noro 2508: @end table
1.15 noro 2509: @end itemize
2510: \E
2511:
2512: \BEG
2513: @itemize @bullet
2514: @item
2515: These functions are new implementations for computing Groebner bases.
2516: @item @code{nd_gr} executes Buchberger algorithm over the rationals
2517: if @code{p} is 0, and that over GF(p) if @code{p} is a prime.
2518: @item @code{nd_gr_trace} executes the trace algorithm over the rationals.
2519: If @code{p} is 0 or 1, the trace algorithm is executed until it succeeds
2520: by using automatically chosen primes.
2521: If @code{p} a positive prime,
2522: the trace is comuted over GF(p).
2523: If the trace algorithm fails 0 is returned.
2524: If @code{p} is negative,
2525: the Groebner basis check and ideal-membership check are omitted.
2526: In this case, an automatically chosen prime if @code{p} is 1,
2527: otherwise the specified prime is used to compute a Groebner basis
2528: candidate.
1.17 noro 2529: Execution of @code{nd_f4_trace} is done as follows:
2530: For each total degree, an F4-reduction of S-polynomials over a finite field
2531: is done, and S-polynomials which give non-zero basis elements are gathered.
2532: Then F4-reduction over Q is done for the gathered S-polynomials.
2533: The obtained polynomial set is a Groebner basis candidate and the same
2534: check procedure as in the case of @code{nd_gr_trace} is done.
2535: @item
2536: @code{nd_f4} executes F4 algorithm over Q if @code{modular} is equal to 0,
2537: or over a finite field GF(@code{modular})
2538: if @code{modular} is a prime number of machine size (<2^29).
1.18 noro 2539: If @var{plist} is a list of polynomials, then a Groebner basis of the ideal generated by @var{plist}
2540: is computed. If @var{plist} is a list of lists of polynomials, then each list of polynomials are regarded
2541: as an element of a free module over a polynomial ring and a Groebner basis of the sub-module generated by @var{plist}
2542: in the free module. In the latter case a term order in the free module should be specified.
2543: This is specified by @var{[s,ord]}. If @var{s} is 0 then it means TOP (Term Over Position).
2544: If @var{s} is 1 then it means POT 1 (Position Over Term). @var{ord} is a term order in the base polynomial ring.
1.15 noro 2545: @item
2546: @code{nd_weyl_gr}, @code{nd_weyl_gr_trace} are for Weyl algebra computation.
2547: @item
1.18 noro 2548: Functions except for F4 related ones can handle rational coeffient cases.
1.15 noro 2549: @item
2550: In general these functions are more efficient than
2551: @code{dp_gr_main}, @code{dp_gr_mod_main}, especially over finite fields.
1.23 noro 2552: @item
2553: The fallowing options can be specified.
2554: @table @code
2555: @item homo
2556: If set to 1, the computation is done via homogenization. (only for @code{nd_gr} and @code{nd_f4})
2557: @item dp
2558: If set to 1, the functions return a list of distributed polynomials (a list of
2559: module polynomials when the input is a sub-module).
2560: @item nora
2561: If set to 1, the inter-reduction is not performed.
2562: @end table
1.15 noro 2563: @end itemize
2564: \E
2565:
2566: @example
2567: [38] load("cyclic")$
2568: [49] C=cyclic(7)$
2569: [50] V=vars(C)$
2570: [51] cputime(1)$
2571: [52] dp_gr_mod_main(C,V,0,31991,0)$
2572: 26.06sec + gc : 0.313sec(26.4sec)
2573: [53] nd_gr(C,V,31991,0)$
2574: ndv_alloc=1477188
2575: 5.737sec + gc : 0.1837sec(5.921sec)
2576: [54] dp_f4_mod_main(C,V,31991,0)$
2577: 3.51sec + gc : 0.7109sec(4.221sec)
2578: [55] nd_f4(C,V,31991,0)$
2579: 1.906sec + gc : 0.126sec(2.032sec)
2580: @end example
2581:
2582: @table @t
1.25 ! noro 2583: \JP @item 参照
1.15 noro 2584: \EG @item References
2585: @fref{dp_ord},
2586: @fref{dp_gr_flags dp_gr_print},
1.25 ! noro 2587: \JP @fref{計算および表示の制御}.
1.2 noro 2588: \EG @fref{Controlling Groebner basis computations}
1.1 noro 2589: @end table
2590:
1.25 ! noro 2591: \JP @node nd_gr_postproc nd_weyl_gr_postproc,,, グレブナ基底に関する函数
1.22 noro 2592: \EG @node nd_gr_postproc nd_weyl_gr_postproc,,, Functions for Groebner basis computation
2593: @subsection @code{nd_gr_postproc}, @code{nd_weyl_gr_postproc}
2594: @findex nd_gr_postproc
2595: @findex nd_weyl_gr_postproc
2596:
2597: @table @t
2598: @item nd_gr_postproc(@var{plist},@var{vlist},@var{p},@var{order},@var{check})
2599: @itemx nd_weyl_gr_postproc(@var{plist},@var{vlist},@var{p},@var{order},@var{check})
1.25 ! noro 2600: \JP :: グレブナ基底候補のチェックおよび相互簡約
1.22 noro 2601: \EG :: Check of Groebner basis candidate and inter-reduction
2602: @end table
2603:
2604: @table @var
2605: @item return
1.25 ! noro 2606: \JP リスト または 0
1.22 noro 2607: \EG list or 0
2608: @item plist vlist
1.25 ! noro 2609: \JP リスト
1.22 noro 2610: \EG list
2611: @item p
1.25 ! noro 2612: \JP 素数または 0
1.22 noro 2613: \EG prime or 0
2614: @item order
1.25 ! noro 2615: \JP 数, リストまたは行列
1.22 noro 2616: \EG number, list or matrix
2617: @item check
1.25 ! noro 2618: \JP 0 または 1
1.22 noro 2619: \EG 0 or 1
2620: @end table
2621:
2622: @itemize @bullet
2623: \BJP
2624: @item
1.25 ! noro 2625: グレブナ基底(候補)の相互簡約を行う.
1.22 noro 2626: @item
1.25 ! noro 2627: @code{nd_weyl_gr_postproc} は Weyl 代数用である.
1.22 noro 2628: @item
1.25 ! noro 2629: @var{check=1} の場合, @var{plist} が, @var{vlist}, @var{p}, @var{order} で指定される多項式環, 項順序でグレブナー基底になっているか
! 2630: のチェックも行う.
1.22 noro 2631: @item
1.25 ! noro 2632: 斉次化して計算したグレブナー基底を非斉次化したものを相互簡約を行う, CRT で計算したグレブナー基底候補のチェックを行うなどの場合に用いる.
1.22 noro 2633: \E
2634: \BEG
2635: @item
2636: Perform the inter-reduction for a Groebner basis (candidate).
2637: @item
2638: @code{nd_weyl_gr_postproc} is for Weyl algebra.
2639: @item
2640: If @var{check=1} then the check whether @var{plist} is a Groebner basis with respect to a term order in a polynomial ring
2641: or Weyl algebra specified by @var{vlist}, @var{p} and @var{order}.
2642: @item
2643: This function is used for inter-reduction of a non-reduced Groebner basis that is obtained by dehomogenizing a Groebner basis
2644: computed via homogenization, or Groebner basis check of a Groebner basis candidate computed by CRT.
2645: \E
2646: @end itemize
2647:
2648: @example
2649: afo
2650: @end example
2651:
1.25 ! noro 2652: \JP @node dp_gr_flags dp_gr_print,,, グレブナ基底に関する函数
1.2 noro 2653: \EG @node dp_gr_flags dp_gr_print,,, Functions for Groebner basis computation
1.1 noro 2654: @subsection @code{dp_gr_flags}, @code{dp_gr_print}
2655: @findex dp_gr_flags
2656: @findex dp_gr_print
2657:
2658: @table @t
2659: @item dp_gr_flags([@var{list}])
1.7 noro 2660: @itemx dp_gr_print([@var{i}])
1.25 ! noro 2661: \JP :: 計算および表示用パラメタの設定, 参照
1.2 noro 2662: \BEG :: Set and show various parameters for cotrolling computations
2663: and showing informations.
2664: \E
1.1 noro 2665: @end table
2666:
2667: @table @var
2668: @item return
1.25 ! noro 2669: \JP 設定値
1.2 noro 2670: \EG value currently set
1.1 noro 2671: @item list
1.25 ! noro 2672: \JP リスト
1.2 noro 2673: \EG list
1.7 noro 2674: @item i
1.25 ! noro 2675: \JP 整数
1.7 noro 2676: \EG integer
1.1 noro 2677: @end table
2678:
2679: @itemize @bullet
1.2 noro 2680: \BJP
1.1 noro 2681: @item
1.25 ! noro 2682: @code{dp_gr_main()}, @code{dp_gr_mod_main()}, @code{dp_gr_f_main()} 実行時におけるさまざま
! 2683: なパラメタを設定, 参照する.
1.1 noro 2684: @item
1.25 ! noro 2685: 引数がない場合, 現在の設定が返される.
1.1 noro 2686: @item
1.25 ! noro 2687: 引数は, @code{["Print",1,"NoSugar",1,...]} なる形のリストで, 左から順に
! 2688: 設定される. パラメタ名は文字列で与える必要がある.
1.1 noro 2689: @item
1.25 ! noro 2690: @code{dp_gr_print()} は, 特にパラメタ @code{Print}, @code{PrintShort} の値を直接設定, 参照
! 2691: できる. 設定される値は次の通りである。
1.7 noro 2692: @table @var
2693: @item i=0
2694: @code{Print=0}, @code{PrintShort=0}
2695: @item i=1
2696: @code{Print=1}, @code{PrintShort=0}
2697: @item i=2
2698: @code{Print=0}, @code{PrintShort=1}
2699: @end table
1.25 ! noro 2700: これは, @code{dp_gr_main()} などをサブルーチンとして用いるユーザ
! 2701: 函数において, そのサブルーチンが中間情報の表示
! 2702: を行う際に, 迅速にフラグを見ることができるように用意されている.
1.2 noro 2703: \E
2704: \BEG
2705: @item
2706: @code{dp_gr_flags()} sets and shows various parameters for Groebner basis
2707: computation.
2708: @item
2709: If no argument is specified the current settings are returned.
2710: @item
2711: Arguments must be specified as a list such as
2712: @code{["Print",1,"NoSugar",1,...]}. Names of parameters must be character
2713: strings.
2714: @item
2715: @code{dp_gr_print()} is used to set and show the value of a parameter
1.7 noro 2716: @code{Print} and @code{PrintShort}.
2717: @table @var
2718: @item i=0
2719: @code{Print=0}, @code{PrintShort=0}
2720: @item i=1
2721: @code{Print=1}, @code{PrintShort=0}
2722: @item i=2
2723: @code{Print=0}, @code{PrintShort=1}
2724: @end table
2725: This functions is prepared to get quickly the value
2726: when a user defined function calling @code{dp_gr_main()} etc.
1.2 noro 2727: uses the value as a flag for showing intermediate informations.
2728: \E
1.1 noro 2729: @end itemize
2730:
2731: @table @t
1.25 ! noro 2732: \JP @item 参照
1.2 noro 2733: \EG @item References
1.25 ! noro 2734: \JP @fref{計算および表示の制御}
1.2 noro 2735: \EG @fref{Controlling Groebner basis computations}
1.1 noro 2736: @end table
2737:
1.25 ! noro 2738: \JP @node dp_ord,,, グレブナ基底に関する函数
1.2 noro 2739: \EG @node dp_ord,,, Functions for Groebner basis computation
1.1 noro 2740: @subsection @code{dp_ord}
2741: @findex dp_ord
2742:
2743: @table @t
2744: @item dp_ord([@var{order}])
1.25 ! noro 2745: \JP :: 変数順序型の設定, 参照
1.2 noro 2746: \EG :: Set and show the ordering type.
1.1 noro 2747: @end table
2748:
2749: @table @var
2750: @item return
1.25 ! noro 2751: \JP 変数順序型 (数, リストまたは行列)
1.2 noro 2752: \EG ordering type (number, list or matrix)
1.1 noro 2753: @item order
1.25 ! noro 2754: \JP 数, リストまたは行列
1.2 noro 2755: \EG number, list or matrix
1.1 noro 2756: @end table
2757:
2758: @itemize @bullet
1.2 noro 2759: \BJP
1.1 noro 2760: @item
1.25 ! noro 2761: 引数がある時, 変数順序型を @var{order} に設定する. 引数がない時,
! 2762: 現在設定されている変数順序型を返す.
1.1 noro 2763:
2764: @item
1.25 ! noro 2765: 分散表現多項式に関する函数, 演算は引数として変数順序型をとるものととらないもの
! 2766: があり, とらないものに関しては, その時点で設定されている値を用いて計算が
! 2767: 行われる.
1.1 noro 2768:
2769: @item
1.25 ! noro 2770: @code{gr()} など, 引数として変数順序型をとるものは, 内部で @code{dp_ord()}
! 2771: を呼び出し, 変数順序型を設定する. この設定は, 計算終了後も生き残る.
1.1 noro 2772:
2773: @item
1.25 ! noro 2774: 分散表現多項式の四則演算も, 設定されている値を用いて計算される. 従って,
! 2775: その多項式が生成された時点における変数順序型が, 四則演算時に正しく設定
! 2776: されていなければならない. また, 演算対象となる多項式は, 同一の変数順序
! 2777: 型に基づいて生成されたものでなければならない.
1.1 noro 2778:
2779: @item
1.25 ! noro 2780: トップレベル函数以外の函数を直接呼び出す場合には, この函数により
! 2781: 変数順序型を正しく設定しなければならない.
1.23 noro 2782:
2783: @item
1.25 ! noro 2784: 引数がリストの場合, 自由加群における項順序型を設定する. 引数が@code{[0,Ord]} の場合,
! 2785: 多項式環上で @code{Ord} で指定される項順序に基づく TOP 順序, 引数が @code{[1,Ord]} の場合
! 2786: OPT 順序を設定する.
1.23 noro 2787:
1.2 noro 2788: \E
2789: \BEG
2790: @item
2791: If an argument is specified, the function
2792: sets the current ordering type to @var{order}.
2793: If no argument is specified, the function returns the ordering
2794: type currently set.
2795:
2796: @item
2797: There are two types of functions concerning distributed polynomial,
2798: functions which take a ordering type and those which don't take it.
2799: The latter ones use the current setting.
2800:
2801: @item
2802: Functions such as @code{gr()}, which need a ordering type as an argument,
2803: call @code{dp_ord()} internally during the execution.
2804: The setting remains after the execution.
2805:
2806: Fundamental arithmetics for distributed polynomial also use the current
2807: setting. Therefore, when such arithmetics for distributed polynomials
2808: are done, the current setting must coincide with the ordering type
2809: which was used upon the creation of the polynomials. It is assumed
2810: that such polynomials were generated under the same ordering type.
2811:
2812: @item
2813: Type of term ordering must be correctly set by this function
2814: when functions other than top level functions are called directly.
1.23 noro 2815:
2816: @item
2817: If the argument is a list, then an ordering type in a free module is set.
2818: If the argument is @code{[0,Ord]} then a TOP ordering based on the ordering type specified
2819: by @code{Ord} is set.
2820: If the argument is @code{[1,Ord]} then a POT ordering is set.
1.2 noro 2821: \E
1.1 noro 2822: @end itemize
2823:
2824: @example
2825: [19] dp_ord(0)$
2826: [20] <<1,2,3>>+<<3,1,1>>;
2827: (1)*<<1,2,3>>+(1)*<<3,1,1>>
2828: [21] dp_ord(2)$
2829: [22] <<1,2,3>>+<<3,1,1>>;
2830: (1)*<<3,1,1>>+(1)*<<1,2,3>>
2831: @end example
2832:
2833: @table @t
1.25 ! noro 2834: \JP @item 参照
1.2 noro 2835: \EG @item References
1.25 ! noro 2836: \JP @fref{項順序の設定}
1.2 noro 2837: \EG @fref{Setting term orderings}
1.1 noro 2838: @end table
2839:
1.25 ! noro 2840: \JP @node dp_set_weight dp_set_top_weight dp_weyl_set_weight,,, グレブナ基底に関する函数
1.18 noro 2841: \EG @node dp_set_weight dp_set_top_weight dp_weyl_set_weight,,, Functions for Groebner basis computation
2842: @subsection @code{dp_set_weight}, @code{dp_set_top_weight}, @code{dp_weyl_set_weight}
2843: @findex dp_set_weight
2844: @findex dp_set_top_weight
2845: @findex dp_weyl_set_weight
2846:
2847: @table @t
2848: @item dp_set_weight([@var{weight}])
1.25 ! noro 2849: \JP :: sugar weight の設定, 参照
1.18 noro 2850: \EG :: Set and show the sugar weight.
2851: @item dp_set_top_weight([@var{weight}])
1.25 ! noro 2852: \JP :: top weight の設定, 参照
1.18 noro 2853: \EG :: Set and show the top weight.
2854: @item dp_weyl_set_weight([@var{weight}])
1.25 ! noro 2855: \JP :: weyl weight の設定, 参照
1.18 noro 2856: \EG :: Set and show the weyl weight.
2857: @end table
2858:
2859: @table @var
2860: @item return
1.25 ! noro 2861: \JP ベクトル
1.18 noro 2862: \EG a vector
2863: @item weight
1.25 ! noro 2864: \JP 整数のリストまたはベクトル
1.18 noro 2865: \EG a list or vector of integers
2866: @end table
2867:
2868: @itemize @bullet
2869: \BJP
2870: @item
1.25 ! noro 2871: @code{dp_set_weight} は sugar weight を @var{weight} に設定する. 引数がない時,
! 2872: 現在設定されている sugar weight を返す. sugar weight は正整数を成分とするベクトルで,
! 2873: 各変数の重みを表す. 次数つき順序において, 単項式の次数を計算する際に用いられる.
! 2874: 斉次化変数用に, 末尾に 1 を付け加えておくと安全である.
! 2875: @item
! 2876: @code{dp_set_top_weight} は top weight を @var{weight} に設定する. 引数がない時,
! 2877: 現在設定されている top weight を返す. top weight が設定されているとき,
! 2878: まず top weight による単項式比較を先に行う. tie breaker として現在設定されている
! 2879: 項順序が用いられるが, この比較には top weight は用いられない.
1.18 noro 2880:
2881: @item
1.25 ! noro 2882: @code{dp_weyl_set_weight} は weyl weight を @var{weight} に設定する. 引数がない時,
! 2883: 現在設定されている weyl weight を返す. weyl weight w を設定すると,
! 2884: 項順序型 11 での計算において, (-w,w) を top weight, tie breaker を graded reverse lex
! 2885: とした項順序が設定される.
1.18 noro 2886: \E
2887: \BEG
2888: @item
2889: @code{dp_set_weight} sets the sugar weight=@var{weight}. It returns the current sugar weight.
2890: A sugar weight is a vector with positive integer components and it represents the weights of variables.
2891: It is used for computing the weight of a monomial in a graded ordering.
2892: It is recommended to append a component 1 at the end of the weight vector for a homogenizing variable.
2893: @item
2894: @code{dp_set_top_weight} sets the top weight=@var{weight}. It returns the current top weight.
2895: It a top weight is set, the weights of monomials under the top weight are firstly compared.
2896: If the the weights are equal then the current term ordering is applied as a tie breaker, but
2897: the top weight is not used in the tie breaker.
2898:
2899: @item
2900: @code{dp_weyl_set_weight} sets the weyl weigh=@var{weight}. It returns the current weyl weight.
2901: If a weyl weight w is set, in the comparsion by the term order type 11, a term order with
2902: the top weight=(-w,w) and the tie breaker=graded reverse lex is applied.
2903: \E
2904: @end itemize
2905:
2906: @table @t
1.25 ! noro 2907: \JP @item 参照
1.18 noro 2908: \EG @item References
2909: @fref{Weight}
2910: @end table
2911:
2912:
1.25 ! noro 2913: \JP @node dp_ptod,,, グレブナ基底に関する函数
1.2 noro 2914: \EG @node dp_ptod,,, Functions for Groebner basis computation
1.1 noro 2915: @subsection @code{dp_ptod}
2916: @findex dp_ptod
2917:
2918: @table @t
2919: @item dp_ptod(@var{poly},@var{vlist})
1.25 ! noro 2920: \JP :: 多項式を分散表現多項式に変換する.
1.2 noro 2921: \EG :: Converts an ordinary polynomial into a distributed polynomial.
1.1 noro 2922: @end table
2923:
2924: @table @var
2925: @item return
1.25 ! noro 2926: \JP 分散表現多項式
1.2 noro 2927: \EG distributed polynomial
1.1 noro 2928: @item poly
1.25 ! noro 2929: \JP 多項式
1.2 noro 2930: \EG polynomial
1.1 noro 2931: @item vlist
1.25 ! noro 2932: \JP リスト
1.2 noro 2933: \EG list
1.1 noro 2934: @end table
2935:
2936: @itemize @bullet
1.2 noro 2937: \BJP
1.1 noro 2938: @item
1.25 ! noro 2939: 変数順序 @var{vlist} および現在の変数順序型に従って分散表現多項式に変換する.
1.1 noro 2940: @item
1.25 ! noro 2941: @var{vlist} に含まれない不定元は, 係数体に属するとして変換される.
1.2 noro 2942: \E
2943: \BEG
2944: @item
2945: According to the variable ordering @var{vlist} and current
2946: type of term ordering, this function converts an ordinary
2947: polynomial into a distributed polynomial.
2948: @item
2949: Indeterminates not included in @var{vlist} are regarded to belong to
2950: the coefficient field.
2951: \E
1.1 noro 2952: @end itemize
2953:
2954: @example
2955: [50] dp_ord(0);
2956: 1
2957: [51] dp_ptod((x+y+z)^2,[x,y,z]);
2958: (1)*<<2,0,0>>+(2)*<<1,1,0>>+(1)*<<0,2,0>>+(2)*<<1,0,1>>+(2)*<<0,1,1>>
2959: +(1)*<<0,0,2>>
2960: [52] dp_ptod((x+y+z)^2,[x,y]);
1.5 noro 2961: (1)*<<2,0>>+(2)*<<1,1>>+(1)*<<0,2>>+(2*z)*<<1,0>>+(2*z)*<<0,1>>
2962: +(z^2)*<<0,0>>
1.1 noro 2963: @end example
2964:
2965: @table @t
1.25 ! noro 2966: \JP @item 参照
1.2 noro 2967: \EG @item References
1.1 noro 2968: @fref{dp_dtop},
2969: @fref{dp_ord}.
2970: @end table
2971:
1.25 ! noro 2972: \JP @node dpm_dptodpm,,, グレブナ基底に関する函数
1.23 noro 2973: \EG @node dpm_dptodpm,,, Functions for Groebner basis computation
2974: @subsection @code{dpm_dptodpm}
2975: @findex dpm_dptodpm
2976:
2977: @table @t
2978: @item dpm_dptodpm(@var{dpoly},@var{pos})
1.25 ! noro 2979: \JP :: 分散表現多項式を加群多項式に変換する.
1.23 noro 2980: \EG :: Converts a distributed polynomial into a module polynomial.
2981: @end table
2982:
2983: @table @var
2984: @item return
1.25 ! noro 2985: \JP 加群多項式
1.23 noro 2986: \EG module polynomial
2987: @item dpoly
1.25 ! noro 2988: \JP 分散表現多項式
1.23 noro 2989: \EG distributed polynomial
2990: @item pos
1.25 ! noro 2991: \JP 正整数
1.23 noro 2992: \EG positive integer
2993: @end table
2994:
2995: @itemize @bullet
2996: \BJP
2997: @item
1.25 ! noro 2998: 分散表現多項式を加群多項式に変換する.
1.23 noro 2999: @item
1.25 ! noro 3000: 出力は加群多項式 @code{dpoly e_pos} である.
1.23 noro 3001: \E
3002: \BEG
3003: @item
3004: This function converts a distributed polynomial into a module polynomial.
3005: @item
3006: The output is @code{dpoly e_pos}.
3007: \E
3008: @end itemize
3009:
3010: @example
3011: [50] dp_ord([0,0])$
3012: [51] D=dp_ptod((x+y+z)^2,[x,y,z]);
3013: (1)*<<2,0,0>>+(2)*<<1,1,0>>+(1)*<<0,2,0>>+(2)*<<1,0,1>>+(2)*<<0,1,1>>
3014: +(1)*<<0,0,2>>
3015: [52] dp_dptodpm(D,2);
3016: (1)*<<2,0,0:2>>+(2)*<<1,1,0:2>>+(1)*<<0,2,0:2>>+(2)*<<1,0,1:2>>
3017: +(2)*<<0,1,1:2>>+(1)*<<0,0,2:2>>
3018: @end example
3019:
3020: @table @t
1.25 ! noro 3021: \JP @item 参照
1.23 noro 3022: \EG @item References
3023: @fref{dp_ptod},
3024: @fref{dp_ord}.
3025: @end table
3026:
1.25 ! noro 3027: \JP @node dpm_ltod,,, グレブナ基底に関する函数
1.23 noro 3028: \EG @node dpm_ltod,,, Functions for Groebner basis computation
3029: @subsection @code{dpm_ltod}
3030: @findex dpm_ltod
3031:
3032: @table @t
3033: @item dpm_dptodpm(@var{plist},@var{vlist})
1.25 ! noro 3034: \JP :: 多項式リストを加群多項式に変換する.
1.23 noro 3035: \EG :: Converts a list of polynomials into a module polynomial.
3036: @end table
3037:
3038: @table @var
3039: @item return
1.25 ! noro 3040: \JP 加群多項式
1.23 noro 3041: \EG module polynomial
3042: @item plist
1.25 ! noro 3043: \JP 多項式リスト
1.23 noro 3044: \EG list of polynomials
3045: @item vlist
1.25 ! noro 3046: \JP 変数リスト
1.23 noro 3047: \EG list of variables
3048: @end table
3049:
3050: @itemize @bullet
3051: \BJP
3052: @item
1.25 ! noro 3053: 多項式リストを加群多項式に変換する.
1.23 noro 3054: @item
1.25 ! noro 3055: @code{[p1,...,pm]} は @code{p1 e1+...+pm em} に変換される.
1.23 noro 3056: \E
3057: \BEG
3058: @item
3059: This function converts a list of polynomials into a module polynomial.
3060: @item
3061: @code{[p1,...,pm]} is converted into @code{p1 e1+...+pm em}.
3062: \E
3063: @end itemize
3064:
3065: @example
3066: [2126] dp_ord([0,0])$
3067: [2127] dpm_ltod([x^2+y^2,x,y-z],[x,y,z]);
3068: (1)*<<2,0,0:1>>+(1)*<<0,2,0:1>>+(1)*<<1,0,0:2>>+(1)*<<0,1,0:3>>
3069: +(-1)*<<0,0,1:3>>
3070: @end example
3071:
3072: @table @t
1.25 ! noro 3073: \JP @item 参照
1.23 noro 3074: \EG @item References
3075: @fref{dpm_dtol},
3076: @fref{dp_ord}.
3077: @end table
3078:
1.25 ! noro 3079: \JP @node dpm_dtol,,, グレブナ基底に関する函数
1.23 noro 3080: \EG @node dpm_dtol,,, Functions for Groebner basis computation
3081: @subsection @code{dpm_dtol}
3082: @findex dpm_dtol
3083:
3084: @table @t
3085: @item dpm_dptodpm(@var{poly},@var{vlist})
1.25 ! noro 3086: \JP :: 加群多項式を多項式リストに変換する.
1.23 noro 3087: \EG :: Converts a module polynomial into a list of polynomials.
3088: @end table
3089:
3090: @table @var
3091: @item return
1.25 ! noro 3092: \JP 多項式リスト
1.23 noro 3093: \EG list of polynomials
3094: @item poly
1.25 ! noro 3095: \JP 加群多項式
1.23 noro 3096: \EG module polynomial
3097: @item vlist
1.25 ! noro 3098: \JP 変数リスト
1.23 noro 3099: \EG list of variables
3100: @end table
3101:
3102: @itemize @bullet
3103: \BJP
3104: @item
1.25 ! noro 3105: 加群多項式を多項式リストに変換する.
1.23 noro 3106: @item
1.25 ! noro 3107: @code{p1 e1+...+pm em} は @code{[p1,...,pm]} に変換される.
1.23 noro 3108: @item
1.25 ! noro 3109: 出力リストの長さは, @code{poly} に含まれる標準基底の最大インデックスとなる.
1.23 noro 3110: \E
3111: \BEG
3112: @item
3113: This function converts a module polynomial into a list of polynomials.
3114: @item
3115: @code{p1 e1+...+pm em} is converted into @code{[p1,...,pm]}.
3116: @item
3117: The length of the output list is equal to the largest index among those of the standard bases
3118: containd in @code{poly}.
3119: \E
3120: @end itemize
3121:
3122: @example
3123: [2126] dp_ord([0,0])$
3124: [2127] D=(1)*<<2,0,0:1>>+(1)*<<0,2,0:1>>+(1)*<<1,0,0:2>>+(1)*<<0,1,0:3>>
3125: +(-1)*<<0,0,1:3>>$
3126: [2128] dpm_dtol(D,[x,y,z]);
3127: [x^2+y^2,x,y-z]
3128: @end example
3129:
3130: @table @t
1.25 ! noro 3131: \JP @item 参照
1.23 noro 3132: \EG @item References
3133: @fref{dpm_ltod},
3134: @fref{dp_ord}.
3135: @end table
3136:
1.25 ! noro 3137: \JP @node dp_dtop,,, グレブナ基底に関する函数
1.2 noro 3138: \EG @node dp_dtop,,, Functions for Groebner basis computation
1.1 noro 3139: @subsection @code{dp_dtop}
3140: @findex dp_dtop
3141:
3142: @table @t
3143: @item dp_dtop(@var{dpoly},@var{vlist})
1.25 ! noro 3144: \JP :: 分散表現多項式を多項式に変換する.
1.2 noro 3145: \EG :: Converts a distributed polynomial into an ordinary polynomial.
1.1 noro 3146: @end table
3147:
3148: @table @var
3149: @item return
1.25 ! noro 3150: \JP 多項式
1.2 noro 3151: \EG polynomial
1.1 noro 3152: @item dpoly
1.25 ! noro 3153: \JP 分散表現多項式
1.2 noro 3154: \EG distributed polynomial
1.1 noro 3155: @item vlist
1.25 ! noro 3156: \JP リスト
1.2 noro 3157: \EG list
1.1 noro 3158: @end table
3159:
3160: @itemize @bullet
1.2 noro 3161: \BJP
1.1 noro 3162: @item
1.25 ! noro 3163: 分散表現多項式を, 与えられた不定元リストを用いて多項式に変換する.
1.1 noro 3164: @item
1.25 ! noro 3165: 不定元リストは, 長さ分散表現多項式の変数の個数と一致していれば何でもよい.
1.2 noro 3166: \E
3167: \BEG
3168: @item
3169: This function converts a distributed polynomial into an ordinary polynomial
3170: according to a list of indeterminates @var{vlist}.
3171: @item
3172: @var{vlist} is such a list that its length coincides with the number of
3173: variables of @var{dpoly}.
3174: \E
1.1 noro 3175: @end itemize
3176:
3177: @example
3178: [53] T=dp_ptod((x+y+z)^2,[x,y]);
1.5 noro 3179: (1)*<<2,0>>+(2)*<<1,1>>+(1)*<<0,2>>+(2*z)*<<1,0>>+(2*z)*<<0,1>>
3180: +(z^2)*<<0,0>>
1.1 noro 3181: [54] P=dp_dtop(T,[a,b]);
3182: z^2+(2*a+2*b)*z+a^2+2*b*a+b^2
3183: @end example
3184:
1.25 ! noro 3185: \JP @node dp_mod dp_rat,,, グレブナ基底に関する函数
1.2 noro 3186: \EG @node dp_mod dp_rat,,, Functions for Groebner basis computation
1.1 noro 3187: @subsection @code{dp_mod}, @code{dp_rat}
3188: @findex dp_mod
3189: @findex dp_rat
3190:
3191: @table @t
3192: @item dp_mod(@var{p},@var{mod},@var{subst})
1.25 ! noro 3193: \JP :: 有理数係数分散表現多項式の有限体係数への変換
1.2 noro 3194: \EG :: Converts a disributed polynomial into one with coefficients in a finite field.
1.1 noro 3195: @item dp_rat(@var{p})
1.25 ! noro 3196: \JP :: 有限体係数分散表現多項式の有理数係数への変換
1.2 noro 3197: \BEG
3198: :: Converts a distributed polynomial with coefficients in a finite field into
3199: one with coefficients in the rationals.
3200: \E
1.1 noro 3201: @end table
3202:
3203: @table @var
3204: @item return
1.25 ! noro 3205: \JP 分散表現多項式
1.2 noro 3206: \EG distributed polynomial
1.1 noro 3207: @item p
1.25 ! noro 3208: \JP 分散表現多項式
1.2 noro 3209: \EG distributed polynomial
1.1 noro 3210: @item mod
1.25 ! noro 3211: \JP 素数
1.2 noro 3212: \EG prime
1.1 noro 3213: @item subst
1.25 ! noro 3214: \JP リスト
1.2 noro 3215: \EG list
1.1 noro 3216: @end table
3217:
3218: @itemize @bullet
1.2 noro 3219: \BJP
1.1 noro 3220: @item
1.25 ! noro 3221: @code{dp_nf_mod()}, @code{dp_true_nf_mod()} は, 入力として有限体係数の
! 3222: 分散表現多項式を必要とする. このような場合, @code{dp_mod()} により
! 3223: 有理数係数分散表現多項式を変換して用いることができる. また, 得られた
! 3224: 結果は, 有限体係数多項式とは演算できるが, 有理数係数多項式とは演算できない
! 3225: ため, @code{dp_rat()} により変換する必要がある.
! 3226: @item
! 3227: 有限体係数の演算においては, あらかじめ @code{setmod()} により有限体の元の
! 3228: 個数を指定しておく必要がある.
! 3229: @item
! 3230: @var{subst} は, 係数が有理式の場合, その有理式の変数にあらかじめ数を代入
! 3231: した後有限体係数に変換するという操作を行う際の, 代入値を指定するもので,
! 3232: @code{[[@var{var},@var{value}],...]} の形のリストである.
1.2 noro 3233: \E
3234: \BEG
3235: @item
3236: @code{dp_nf_mod()} and @code{dp_true_nf_mod()} require
3237: distributed polynomials with coefficients in a finite field as arguments.
3238: @code{dp_mod()} is used to convert distributed polynomials with rational
3239: number coefficients into appropriate ones.
3240: Polynomials with coefficients in a finite field
3241: cannot be used as inputs of operations with polynomials
3242: with rational number coefficients. @code{dp_rat()} is used for such cases.
3243: @item
3244: The ground finite field must be set in advance by using @code{setmod()}.
3245: @item
3246: @var{subst} is such a list as @code{[[@var{var},@var{value}],...]}.
3247: This is valid when the ground field of the input polynomial is a
3248: rational function field. @var{var}'s are variables in the ground field and
3249: the list means that @var{value} is substituted for @var{var} before
3250: converting the coefficients into elements of a finite field.
3251: \E
1.1 noro 3252: @end itemize
3253:
3254: @example
3255: @end example
3256:
3257: @table @t
1.25 ! noro 3258: \JP @item 参照
1.2 noro 3259: \EG @item References
1.18 noro 3260: @fref{dp_nf dp_nf_mod dp_true_nf dp_true_nf_mod dp_weyl_nf dp_weyl_nf_mod},
1.1 noro 3261: @fref{subst psubst},
3262: @fref{setmod}.
3263: @end table
3264:
1.25 ! noro 3265: \JP @node dp_homo dp_dehomo,,, グレブナ基底に関する函数
1.2 noro 3266: \EG @node dp_homo dp_dehomo,,, Functions for Groebner basis computation
1.1 noro 3267: @subsection @code{dp_homo}, @code{dp_dehomo}
3268: @findex dp_homo
3269: @findex dp_dehomo
3270:
3271: @table @t
3272: @item dp_homo(@var{dpoly})
1.25 ! noro 3273: \JP :: 分散表現多項式の斉次化
1.2 noro 3274: \EG :: Homogenize a distributed polynomial
1.1 noro 3275: @item dp_dehomo(@var{dpoly})
1.25 ! noro 3276: \JP :: 斉次分散表現多項式の非斉次化
1.2 noro 3277: \EG :: Dehomogenize a homogenious distributed polynomial
1.1 noro 3278: @end table
3279:
3280: @table @var
3281: @item return
1.25 ! noro 3282: \JP 分散表現多項式
1.2 noro 3283: \EG distributed polynomial
1.1 noro 3284: @item dpoly
1.25 ! noro 3285: \JP 分散表現多項式
1.2 noro 3286: \EG distributed polynomial
1.1 noro 3287: @end table
3288:
3289: @itemize @bullet
1.2 noro 3290: \BJP
1.1 noro 3291: @item
1.25 ! noro 3292: @code{dp_homo()} は, @var{dpoly} の 各項 @var{t} について, 指数ベクトルの長さを
! 3293: 1 伸ばし, 最後の成分の値を @var{d}-@code{deg(@var{t})}
! 3294: (@var{d} は @var{dpoly} の全次数) とした分散表現多項式を返す.
1.1 noro 3295: @item
1.25 ! noro 3296: @code{dp_dehomo()} は, @var{dpoly} の各項について, 指数ベクトルの最後の成分
! 3297: を取り除いた分散多項式を返す.
1.1 noro 3298: @item
1.25 ! noro 3299: いずれも, 生成された多項式を用いた演算を行う場合, それらに適合する項順序を
! 3300: 正しく設定する必要がある.
1.1 noro 3301: @item
1.25 ! noro 3302: @code{hgr()} などにおいて, 内部的に用いられている.
1.2 noro 3303: \E
3304: \BEG
3305: @item
3306: @code{dp_homo()} makes a copy of @var{dpoly}, extends
3307: the length of the exponent vector of each term @var{t} in the copy by 1,
3308: and sets the value of the newly appended
3309: component to @var{d}-@code{deg(@var{t})}, where @var{d} is the total
3310: degree of @var{dpoly}.
3311: @item
3312: @code{dp_dehomo()} make a copy of @var{dpoly} and removes the last component
3313: of each terms in the copy.
3314: @item
3315: Appropriate term orderings must be set when the results are used as inputs
3316: of some operations.
3317: @item
3318: These are used internally in @code{hgr()} etc.
3319: \E
1.1 noro 3320: @end itemize
3321:
3322: @example
3323: [202] X=<<1,2,3>>+3*<<1,2,1>>;
3324: (1)*<<1,2,3>>+(3)*<<1,2,1>>
3325: [203] dp_homo(X);
3326: (1)*<<1,2,3,0>>+(3)*<<1,2,1,2>>
3327: [204] dp_dehomo(@@);
3328: (1)*<<1,2,3>>+(3)*<<1,2,1>>
3329: @end example
3330:
3331: @table @t
1.25 ! noro 3332: \JP @item 参照
1.2 noro 3333: \EG @item References
1.1 noro 3334: @fref{gr hgr gr_mod}.
3335: @end table
3336:
1.25 ! noro 3337: \JP @node dp_ptozp dp_prim,,, グレブナ基底に関する函数
1.2 noro 3338: \EG @node dp_ptozp dp_prim,,, Functions for Groebner basis computation
1.1 noro 3339: @subsection @code{dp_ptozp}, @code{dp_prim}
3340: @findex dp_ptozp
3341: @findex dp_prim
3342:
3343: @table @t
3344: @item dp_ptozp(@var{dpoly})
1.25 ! noro 3345: \JP :: 定数倍して係数を整数係数かつ係数の整数 GCD を 1 にする.
1.2 noro 3346: \BEG
3347: :: Converts a distributed polynomial @var{poly} with rational coefficients
3348: into an integral distributed polynomial such that GCD of all its coefficients
3349: is 1.
3350: \E
1.19 noro 3351: @item dp_prim(@var{dpoly})
1.25 ! noro 3352: \JP :: 有理式倍して係数を整数係数多項式係数かつ係数の多項式 GCD を 1 にする.
1.2 noro 3353: \BEG
3354: :: Converts a distributed polynomial @var{poly} with rational function
3355: coefficients into an integral distributed polynomial such that polynomial
3356: GCD of all its coefficients is 1.
3357: \E
1.1 noro 3358: @end table
3359:
3360: @table @var
3361: @item return
1.25 ! noro 3362: \JP 分散表現多項式
1.2 noro 3363: \EG distributed polynomial
1.1 noro 3364: @item dpoly
1.25 ! noro 3365: \JP 分散表現多項式
1.2 noro 3366: \EG distributed polynomial
1.1 noro 3367: @end table
3368:
3369: @itemize @bullet
1.2 noro 3370: \BJP
1.1 noro 3371: @item
1.25 ! noro 3372: @code{dp_ptozp()} は, @code{ptozp()} に相当する操作を分散表現多項式に
! 3373: 対して行う. 係数が多項式を含む場合, 係数に含まれる多項式共通因子は
! 3374: 取り除かない.
1.1 noro 3375: @item
1.25 ! noro 3376: @code{dp_prim()} は, 係数が多項式を含む場合, 係数に含まれる多項式共通因子
! 3377: を取り除く.
1.2 noro 3378: \E
3379: \BEG
3380: @item
3381: @code{dp_ptozp()} executes the same operation as @code{ptozp()} for
3382: a distributed polynomial. If the coefficients include polynomials,
3383: polynomial contents included in the coefficients are not removed.
3384: @item
3385: @code{dp_prim()} removes polynomial contents.
3386: \E
1.1 noro 3387: @end itemize
3388:
3389: @example
3390: [208] X=dp_ptod(3*(x-y)*(y-z)*(z-x),[x]);
3391: (-3*y+3*z)*<<2>>+(3*y^2-3*z^2)*<<1>>+(-3*z*y^2+3*z^2*y)*<<0>>
3392: [209] dp_ptozp(X);
3393: (-y+z)*<<2>>+(y^2-z^2)*<<1>>+(-z*y^2+z^2*y)*<<0>>
3394: [210] dp_prim(X);
3395: (1)*<<2>>+(-y-z)*<<1>>+(z*y)*<<0>>
3396: @end example
3397:
3398: @table @t
1.25 ! noro 3399: \JP @item 参照
1.2 noro 3400: \EG @item References
1.1 noro 3401: @fref{ptozp}.
3402: @end table
3403:
1.25 ! noro 3404: \JP @node dp_nf dp_nf_mod dp_true_nf dp_true_nf_mod dp_weyl_nf dp_weyl_nf_mod,,, グレブナ基底に関する函数
1.18 noro 3405: \EG @node dp_nf dp_nf_mod dp_true_nf dp_true_nf_mod dp_weyl_nf dp_weyl_nf_mod,,, Functions for Groebner basis computation
1.1 noro 3406: @subsection @code{dp_nf}, @code{dp_nf_mod}, @code{dp_true_nf}, @code{dp_true_nf_mod}
3407: @findex dp_nf
3408: @findex dp_true_nf
3409: @findex dp_nf_mod
3410: @findex dp_true_nf_mod
1.18 noro 3411: @findex dp_weyl_nf
3412: @findex dp_weyl_nf_mod
1.1 noro 3413:
3414: @table @t
3415: @item dp_nf(@var{indexlist},@var{dpoly},@var{dpolyarray},@var{fullreduce})
1.18 noro 3416: @item dp_weyl_nf(@var{indexlist},@var{dpoly},@var{dpolyarray},@var{fullreduce})
1.1 noro 3417: @item dp_nf_mod(@var{indexlist},@var{dpoly},@var{dpolyarray},@var{fullreduce},@var{mod})
1.18 noro 3418: @item dp_weyl_nf_mod(@var{indexlist},@var{dpoly},@var{dpolyarray},@var{fullreduce},@var{mod})
1.25 ! noro 3419: \JP :: 分散表現多項式の正規形を求める. (結果は定数倍されている可能性あり)
1.1 noro 3420:
1.2 noro 3421: \BEG
3422: :: Computes the normal form of a distributed polynomial.
3423: (The result may be multiplied by a constant in the ground field.)
3424: \E
1.1 noro 3425: @item dp_true_nf(@var{indexlist},@var{dpoly},@var{dpolyarray},@var{fullreduce})
3426: @item dp_true_nf_mod(@var{indexlist},@var{dpoly},@var{dpolyarray},@var{fullreduce},@var{mod})
1.25 ! noro 3427: \JP :: 分散表現多項式の正規形を求める. (真の結果を @code{[分子, 分母]} の形で返す)
1.2 noro 3428: \BEG
3429: :: Computes the normal form of a distributed polynomial. (The true result
3430: is returned in such a list as @code{[numerator, denominator]})
3431: \E
1.1 noro 3432: @end table
3433:
3434: @table @var
3435: @item return
1.25 ! noro 3436: \JP @code{dp_nf()} : 分散表現多項式, @code{dp_true_nf()} : リスト
1.2 noro 3437: \EG @code{dp_nf()} : distributed polynomial, @code{dp_true_nf()} : list
1.1 noro 3438: @item indexlist
1.25 ! noro 3439: \JP リスト
1.2 noro 3440: \EG list
1.1 noro 3441: @item dpoly
1.25 ! noro 3442: \JP 分散表現多項式
1.2 noro 3443: \EG distributed polynomial
1.1 noro 3444: @item dpolyarray
1.25 ! noro 3445: \JP 配列
1.2 noro 3446: \EG array of distributed polynomial
1.1 noro 3447: @item fullreduce
1.25 ! noro 3448: \JP フラグ
1.2 noro 3449: \EG flag
1.1 noro 3450: @item mod
1.25 ! noro 3451: \JP 素数
1.2 noro 3452: \EG prime
1.1 noro 3453: @end table
3454:
3455: @itemize @bullet
1.2 noro 3456: \BJP
1.1 noro 3457: @item
1.25 ! noro 3458: 分散表現多項式 @var{dpoly} の正規形を求める.
1.1 noro 3459: @item
1.25 ! noro 3460: 名前に weyl を含む関数はワイル代数における正規形計算を行う. 以下の説明は weyl を含むものに対しても同様に成立する.
1.18 noro 3461: @item
1.25 ! noro 3462: @code{dp_nf_mod()}, @code{dp_true_nf_mod()} の入力は, @code{dp_mod()} など
! 3463: により, 有限体上の分散表現多項式になっていなければならない.
1.1 noro 3464: @item
1.25 ! noro 3465: 結果に有理数, 有理式が含まれるのを避けるため, @code{dp_nf()} は
! 3466: 真の値の定数倍の値を返す. 有理式係数の場合の @code{dp_nf_mod()} も同様
! 3467: であるが, 係数体が有限体の場合 @code{dp_nf_mod()} は真の値を返す.
1.1 noro 3468: @item
1.25 ! noro 3469: @code{dp_true_nf()}, @code{dp_true_nf_mod()} は,
! 3470: @code{[@var{nm},@var{dn}]} なる形のリストを返す.
! 3471: ただし, @var{nm} は係数に分数, 有理式を含まない分散表現多項式, @var{dn} は
! 3472: 数または多項式で @var{nm}/@var{dn} が真の値となる.
1.1 noro 3473: @item
1.25 ! noro 3474: @var{dpolyarray} は分散表現多項式を要素とするベクトル,
! 3475: @var{indexlist} は正規化計算に用いる @var{dpolyarray} の要素のインデックス
! 3476: のリスト.
1.1 noro 3477: @item
1.25 ! noro 3478: @var{fullreduce} が 0 でないとき全ての項に対して簡約を行う. @var{fullreduce}
! 3479: が 0 のとき頭項のみに対して簡約を行う.
1.1 noro 3480: @item
1.25 ! noro 3481: @var{indexlist} で指定された多項式は, 前の方のものが優先的に使われる.
1.1 noro 3482: @item
1.25 ! noro 3483: 一般には @var{indexlist} の与え方により函数の値は異なる可能性があるが,
! 3484: グレブナ基底に対しては一意的に定まる.
1.1 noro 3485: @item
1.25 ! noro 3486: 分散表現でない固定された多項式集合による正規形を多数求める必要がある場合
! 3487: に便利である. 単一の演算に関しては, @code{p_nf}, @code{p_true_nf} を
! 3488: 用いるとよい.
1.2 noro 3489: \E
3490: \BEG
3491: @item
3492: Computes the normal form of a distributed polynomial.
3493: @item
1.18 noro 3494: Functions whose name contain @code{weyl} compute normal forms in Weyl algebra. The description below also applies to
3495: the functions for Weyl algebra.
3496: @item
1.2 noro 3497: @code{dp_nf_mod()} and @code{dp_true_nf_mod()} require
3498: distributed polynomials with coefficients in a finite field as arguments.
3499: @item
3500: The result of @code{dp_nf()} may be multiplied by a constant in the
3501: ground field in order to make the result integral. The same is true
3502: for @code{dp_nf_mod()}, but it returns the true normal form if
3503: the ground field is a finite field.
3504: @item
3505: @code{dp_true_nf()} and @code{dp_true_nf_mod()} return
3506: such a list as @code{[@var{nm},@var{dn}]}.
3507: Here @var{nm} is a distributed polynomial whose coefficients are integral
3508: in the ground field, @var{dn} is an integral element in the ground
3509: field and @var{nm}/@var{dn} is the true normal form.
3510: @item
3511: @var{dpolyarray} is a vector whose components are distributed polynomials
3512: and @var{indexlist} is a list of indices which is used for the normal form
3513: computation.
3514: @item
3515: When argument @var{fullreduce} has non-zero value,
3516: all terms are reduced. When it has value 0,
3517: only the head term is reduced.
3518: @item
3519: As for the polynomials specified by @var{indexlist}, one specified by
3520: an index placed at the preceding position has priority to be selected.
3521: @item
3522: In general, the result of the function may be different depending on
3523: @var{indexlist}. However, the result is unique for Groebner bases.
3524: @item
3525: These functions are useful when a fixed non-distributed polynomial set
3526: is used as a set of reducers to compute normal forms of many polynomials.
3527: For single computation @code{p_nf} and @code{p_true_nf} are sufficient.
3528: \E
1.1 noro 3529: @end itemize
3530:
3531: @example
3532: [0] load("gr")$
3533: [64] load("katsura")$
3534: [69] K=katsura(4)$
3535: [70] dp_ord(2)$
3536: [71] V=[u0,u1,u2,u3,u4]$
3537: [72] DP1=newvect(length(K),map(dp_ptod,K,V))$
3538: [73] G=gr(K,V,2)$
3539: [74] DP2=newvect(length(G),map(dp_ptod,G,V))$
3540: [75] T=dp_ptod((u0-u1+u2-u3+u4)^2,V)$
3541: [76] dp_dtop(dp_nf([0,1,2,3,4],T,DP1,1),V);
1.5 noro 3542: u4^2+(6*u3+2*u2+6*u1-2)*u4+9*u3^2+(6*u2+18*u1-6)*u3+u2^2
3543: +(6*u1-2)*u2+9*u1^2-6*u1+1
1.1 noro 3544: [77] dp_dtop(dp_nf([4,3,2,1,0],T,DP1,1),V);
3545: -5*u4^2+(-4*u3-4*u2-4*u1)*u4-u3^2-3*u3-u2^2+(2*u1-1)*u2-2*u1^2-3*u1+1
3546: [78] dp_dtop(dp_nf([0,1,2,3,4],T,DP2,1),V);
1.5 noro 3547: -11380879768451657780886122972730785203470970010204714556333530492210
3548: 456775930005716505560062087150928400876150217079820311439477560587583
3549: 488*u4^15+...
1.1 noro 3550: [79] dp_dtop(dp_nf([4,3,2,1,0],T,DP2,1),V);
1.5 noro 3551: -11380879768451657780886122972730785203470970010204714556333530492210
3552: 456775930005716505560062087150928400876150217079820311439477560587583
3553: 488*u4^15+...
1.1 noro 3554: [80] @@78==@@79;
3555: 1
3556: @end example
3557:
3558: @table @t
1.25 ! noro 3559: \JP @item 参照
1.2 noro 3560: \EG @item References
1.1 noro 3561: @fref{dp_dtop},
3562: @fref{dp_ord},
3563: @fref{dp_mod dp_rat},
3564: @fref{p_nf p_nf_mod p_true_nf p_true_nf_mod}.
3565: @end table
3566:
1.25 ! noro 3567: \JP @node dpm_nf dpm_nf_and_quotient,,, グレブナ基底に関する函数
1.23 noro 3568: \EG @node dpm_nf dpm_nf_and_quotient,,, Functions for Groebner basis computation
3569: @subsection @code{dpm_nf}, @code{dpm_nf_and_quotient}
3570: @findex dpm_nf
3571: @findex dpm_nf_and_quotient
3572:
3573: @table @t
3574: @item dpm_nf([@var{indexlist},]@var{dpoly},@var{dpolyarray},@var{fullreduce})
1.25 ! noro 3575: \JP :: 加群多項式の正規形を求める. (結果は定数倍されている可能性あり)
1.23 noro 3576:
3577: \BEG
3578: :: Computes the normal form of a module polynomial.
3579: (The result may be multiplied by a constant in the ground field.)
3580: \E
3581: @item dpm_nf_and_quotient([@var{indexlist},]@var{dpoly},@var{dpolyarray})
1.25 ! noro 3582: \JP :: 加群多項式の正規形と商を求める.
1.23 noro 3583: \BEG
3584: :: Computes the normal form of a module polynomial and the quotient.
3585: \E
3586: @end table
3587:
3588: @table @var
3589: @item return
1.25 ! noro 3590: \JP @code{dpm_nf()} : 加群多項式, @code{dpm_nf_and_quotient()} : リスト
1.23 noro 3591: \EG @code{dpm_nf()} : module polynomial, @code{dpm_nf_and_quotient()} : list
3592: @item indexlist
1.25 ! noro 3593: \JP リスト
1.23 noro 3594: \EG list
3595: @item dpoly
1.25 ! noro 3596: \JP 加群多項式
1.23 noro 3597: \EG module polynomial
3598: @item dpolyarray
1.25 ! noro 3599: \JP 配列
1.23 noro 3600: \EG array of module polynomial
3601: @end table
3602:
3603: @itemize @bullet
3604: \BJP
3605: @item
1.25 ! noro 3606: 加群多項式 @var{dpoly} の正規形を求める.
1.23 noro 3607: @item
1.25 ! noro 3608: 結果に有理数, 有理式が含まれるのを避けるため, @code{dpm_nf()} は
! 3609: 真の値の定数倍の値を返す.
1.23 noro 3610: @item
1.25 ! noro 3611: @var{dpolyarray} は加群多項式を要素とするベクトル,
! 3612: @var{indexlist} は正規化計算に用いる @var{dpolyarray} の要素のインデックス
1.23 noro 3613: @item
1.25 ! noro 3614: @var{indexlist} が与えられている場合, @var{dpolyarray} の中で, @var{indexlist} で指定されたもののみが, 前の方から優先的に使われる.
! 3615: @var{indexlist} が与えられていない場合には, @var{dpolyarray} の中の全ての多項式が前の方から優先的に使われる.
! 3616: @item
! 3617: @code{dpm_nf_and_quotient()} は,
! 3618: @code{[@var{nm},@var{dn},@var{quo}]} なる形のリストを返す.
! 3619: ただし, @var{nm} は係数に分数を含まない加群多項式, @var{dn} は
! 3620: 数または多項式で @var{nm}/@var{dn} が真の値となる.
! 3621: @var{quo} は除算の商を表す配列で, @var{dn}@var{dpoly}=@var{nm}+@var{quo[0]dpolyarray[0]+...} が成り立つ.
! 3622: のリスト.
1.23 noro 3623: @item
1.25 ! noro 3624: @var{fullreduce} が 0 でないとき全ての項に対して簡約を行う. @var{fullreduce}
! 3625: が 0 のとき頭項のみに対して簡約を行う.
1.23 noro 3626: \E
3627: \BEG
3628: @item
3629: Computes the normal form of a module polynomial.
3630: @item
3631: The result of @code{dpm_nf()} may be multiplied by a constant in the
3632: ground field in order to make the result integral.
3633: @item
3634: @var{dpolyarray} is a vector whose components are module polynomials
3635: and @var{indexlist} is a list of indices which is used for the normal form
3636: computation.
3637: @item
3638: If @var{indexlist} is given, only the polynomials in @var{dpolyarray} specified in @var{indexlist}
3639: is used in the division. An index placed at the preceding position has priority to be selected.
3640: If @var{indexlist} is not given, all the polynomials in @var{dpolyarray} are used.
3641: @item
3642: @code{dpm_nf_and_quotient()} returns
3643: such a list as @code{[@var{nm},@var{dn},@var{quo}]}.
3644: Here @var{nm} is a module polynomial whose coefficients are integral
3645: in the ground field, @var{dn} is an integral element in the ground
3646: field and @var{nm}/@var{dn} is the true normal form.
3647: @var{quo} is an array containing the quotients of the division satisfying
3648: @var{dn}@var{dpoly}=@var{nm}+@var{quo[0]dpolyarray[0]+...}.
3649: @item
3650: When argument @var{fullreduce} has non-zero value,
3651: all terms are reduced. When it has value 0,
3652: only the head term is reduced.
3653: \E
3654: @end itemize
3655:
3656: @example
3657: [2126] dp_ord([1,0])$
3658: [2127] S=ltov([(1)*<<0,0,2,0:1>>+(1)*<<0,0,1,1:1>>+(1)*<<0,0,0,2:1>>
3659: +(-1)*<<3,0,0,0:2>>+(-1)*<<0,0,2,1:2>>+(-1)*<<0,0,1,2:2>>
3660: +(1)*<<3,0,1,0:3>>+(1)*<<3,0,0,1:3>>+(1)*<<0,0,2,2:3>>,
3661: (-1)*<<0,1,0,0:1>>+(-1)*<<0,0,1,0:1>>+(-1)*<<0,0,0,1:1>>
3662: +(-1)*<<3,0,0,0:3>>+(1)*<<0,1,1,1:3>>,(1)*<<0,1,0,0:2>>
3663: +(1)*<<0,0,1,0:2>>+(1)*<<0,0,0,1:2>>+(-1)*<<0,1,1,0:3>>
3664: +(-1)*<<0,1,0,1:3>>+(-1)*<<0,0,1,1:3>>])$
3665: [2128] U=dpm_sp(S[0],S[1]);
3666: (1)*<<0,0,3,0:1>>+(-1)*<<0,1,1,1:1>>+(1)*<<0,0,2,1:1>>
3667: +(-1)*<<0,1,0,2:1>>+(1)*<<3,1,0,0:2>>+(1)*<<0,1,2,1:2>>
3668: +(1)*<<0,1,1,2:2>>+(-1)*<<3,1,1,0:3>>+(1)*<<3,0,2,0:3>>
3669: +(-1)*<<3,1,0,1:3>>+(-1)*<<0,1,3,1:3>>+(-1)*<<0,1,2,2:3>>
3670: [2129] dpm_nf(U,S,1);
3671: 0
3672: [2130] L=dpm_nf_and_quotient(U,S)$
3673: [2131] Q=L[2]$
3674: [2132] D=L[1]$
3675: [2133] D*U-(Q[1]*S[1]+Q[2]*S[2]);
3676: 0
3677: @end example
3678:
3679: @table @t
1.25 ! noro 3680: \JP @item 参照
1.23 noro 3681: \EG @item References
3682: @fref{dpm_sp},
3683: @fref{dp_ord}.
3684: @end table
3685:
3686:
1.25 ! noro 3687: \JP @node dp_hm dp_ht dp_hc dp_rest,,, グレブナ基底に関する函数
1.2 noro 3688: \EG @node dp_hm dp_ht dp_hc dp_rest,,, Functions for Groebner basis computation
1.1 noro 3689: @subsection @code{dp_hm}, @code{dp_ht}, @code{dp_hc}, @code{dp_rest}
3690: @findex dp_hm
3691: @findex dp_ht
3692: @findex dp_hc
3693: @findex dp_rest
3694:
3695: @table @t
3696: @item dp_hm(@var{dpoly})
1.25 ! noro 3697: \JP :: 頭単項式を取り出す.
1.2 noro 3698: \EG :: Gets the head monomial.
1.1 noro 3699: @item dp_ht(@var{dpoly})
1.25 ! noro 3700: \JP :: 頭項を取り出す.
1.2 noro 3701: \EG :: Gets the head term.
1.1 noro 3702: @item dp_hc(@var{dpoly})
1.25 ! noro 3703: \JP :: 頭係数を取り出す.
1.2 noro 3704: \EG :: Gets the head coefficient.
1.1 noro 3705: @item dp_rest(@var{dpoly})
1.25 ! noro 3706: \JP :: 頭単項式を取り除いた残りを返す.
1.2 noro 3707: \EG :: Gets the remainder of the polynomial where the head monomial is removed.
1.1 noro 3708: @end table
3709:
3710: @table @var
1.2 noro 3711: \BJP
1.1 noro 3712: @item return
1.25 ! noro 3713: @code{dp_hm()}, @code{dp_ht()}, @code{dp_rest()} : 分散表現多項式,
! 3714: @code{dp_hc()} : 数または多項式
1.1 noro 3715: @item dpoly
1.25 ! noro 3716: 分散表現多項式
1.2 noro 3717: \E
3718: \BEG
3719: @item return
3720: @code{dp_hm()}, @code{dp_ht()}, @code{dp_rest()} : distributed polynomial
3721: @code{dp_hc()} : number or polynomial
3722: @item dpoly
3723: distributed polynomial
3724: \E
1.1 noro 3725: @end table
3726:
3727: @itemize @bullet
1.2 noro 3728: \BJP
1.1 noro 3729: @item
1.25 ! noro 3730: これらは, 分散表現多項式の各部分を取り出すための函数である.
1.1 noro 3731: @item
1.25 ! noro 3732: 分散表現多項式 @var{p} に対し次が成り立つ.
1.2 noro 3733: \E
3734: \BEG
3735: @item
3736: These are used to get various parts of a distributed polynomial.
3737: @item
3738: The next equations hold for a distributed polynomial @var{p}.
3739: \E
1.1 noro 3740: @table @code
3741: @item @var{p} = dp_hm(@var{p}) + dp_rest(@var{p})
3742: @item dp_hm(@var{p}) = dp_hc(@var{p}) dp_ht(@var{p})
3743: @end table
3744: @end itemize
3745:
3746: @example
3747: [87] dp_ord(0)$
3748: [88] X=ptozp((a46^2+7/10*a46+7/48)*u3^4-50/27*a46^2-35/27*a46-49/216)$
3749: [89] T=dp_ptod(X,[u3,u4,a46])$
3750: [90] dp_hm(T);
3751: (2160)*<<4,0,2>>
3752: [91] dp_ht(T);
3753: (1)*<<4,0,2>>
3754: [92] dp_hc(T);
3755: 2160
3756: [93] dp_rest(T);
3757: (1512)*<<4,0,1>>+(315)*<<4,0,0>>+(-4000)*<<0,0,2>>+(-2800)*<<0,0,1>>
3758: +(-490)*<<0,0,0>>
3759: @end example
3760:
1.25 ! noro 3761: \JP @node dpm_hm dpm_ht dpm_hc dpm_hp dpm_rest,,, グレブナ基底に関する函数
1.23 noro 3762: \EG @node dpm_hm dpm_ht dpm_hc dpm_hp dpm_rest,,, Functions for Groebner basis computation
3763: @subsection @code{dpm_hm}, @code{dpm_ht}, @code{dpm_hc}, @code{dpm_hp}, @code{dpm_rest}
3764: @findex dpm_hm
3765: @findex dpm_ht
3766: @findex dpm_hc
3767: @findex dpm_hp
3768: @findex dpm_rest
3769:
3770: @table @t
3771: @item dpm_hm(@var{dpoly})
1.25 ! noro 3772: \JP :: 加群多項式の頭単項式を取り出す.
1.23 noro 3773: \EG :: Gets the head monomial of a module polynomial.
3774: @item dpm_ht(@var{dpoly})
1.25 ! noro 3775: \JP :: 加群多項式の頭項を取り出す.
1.23 noro 3776: \EG :: Gets the head term of a module polynomial.
3777: @item dpm_hc(@var{dpoly})
1.25 ! noro 3778: \JP :: 加群多項式の頭係数を取り出す.
1.23 noro 3779: \EG :: Gets the head coefficient of a module polynomial.
3780: @item dpm_hp(@var{dpoly})
1.25 ! noro 3781: \JP :: 加群多項式の頭位置を取り出す.
1.23 noro 3782: \EG :: Gets the head position of a module polynomial.
3783: @item dpm_rest(@var{dpoly})
1.25 ! noro 3784: \JP :: 加群多項式の頭単項式を取り除いた残りを返す.
1.23 noro 3785: \EG :: Gets the remainder of a module polynomial where the head monomial is removed.
3786: @end table
3787:
3788: @table @var
3789: \BJP
3790: @item return
1.25 ! noro 3791: @code{dp_hm()}, @code{dp_ht()}, @code{dp_rest()} : 加群多項式,
! 3792: @code{dp_hc()} : 数または多項式
1.23 noro 3793: @item dpoly
1.25 ! noro 3794: 加群多項式
1.23 noro 3795: \E
3796: \BEG
3797: @item return
3798: @code{dpm_hm()}, @code{dpm_ht()}, @code{dpm_rest()} : module polynomial
3799: @code{dpm_hc()} : monomial
3800: @item dpoly
3801: distributed polynomial
3802: \E
3803: @end table
3804:
3805: @itemize @bullet
3806: \BJP
3807: @item
1.25 ! noro 3808: これらは, 加群多項式の各部分を取り出すための函数である.
1.23 noro 3809: @item
1.25 ! noro 3810: @code{dpm_hc()} は, @code{dpm_hm()} の, 標準基底に関する係数である単項式を返す.
! 3811: スカラー係数を取り出すには, さらに @code{dp_hc()} を実行する.
1.23 noro 3812: @item
1.25 ! noro 3813: @code{dpm_hp()} は, 頭加群単項式に含まれる標準基底のインデックスを返す.
1.23 noro 3814: \E
3815: \BEG
3816: @item
3817: These are used to get various parts of a module polynomial.
3818: @item
3819: @code{dpm_hc()} returns the monomial that is the coefficient of @code{dpm_hm()} with respect to the
3820: standard base.
3821: For getting its scalar coefficient apply @code{dp_hc()}.
3822: @item
3823: @code{dpm_hp()} returns the index of the standard base conteind in the head module monomial.
3824: \E
3825: @end itemize
3826:
3827: @example
3828: [2126] dp_ord([1,0]);
3829: [1,0]
3830: [2127] F=2*<<1,2,0:2>>-3*<<1,0,2:3>>+<<2,1,0:2>>;
3831: (1)*<<2,1,0:2>>+(2)*<<1,2,0:2>>+(-3)*<<1,0,2:3>>
3832: [2128] M=dpm_hm(F);
3833: (1)*<<2,1,0:2>>
3834: [2129] C=dpm_hc(F);
3835: (1)*<<2,1,0>>
3836: [2130] R=dpm_rest(F);
3837: (2)*<<1,2,0:2>>+(-3)*<<1,0,2:3>>
3838: [2131] dpm_hp(F);
3839: 2
3840: @end example
3841:
3842:
1.25 ! noro 3843: \JP @node dp_td dp_sugar,,, グレブナ基底に関する函数
1.2 noro 3844: \EG @node dp_td dp_sugar,,, Functions for Groebner basis computation
1.1 noro 3845: @subsection @code{dp_td}, @code{dp_sugar}
3846: @findex dp_td
3847: @findex dp_sugar
3848:
3849: @table @t
3850: @item dp_td(@var{dpoly})
1.25 ! noro 3851: \JP :: 頭項の全次数を返す.
1.2 noro 3852: \EG :: Gets the total degree of the head term.
1.1 noro 3853: @item dp_sugar(@var{dpoly})
1.25 ! noro 3854: \JP :: 多項式の @code{sugar} を返す.
1.2 noro 3855: \EG :: Gets the @code{sugar} of a polynomial.
1.1 noro 3856: @end table
3857:
3858: @table @var
3859: @item return
1.25 ! noro 3860: \JP 自然数
1.2 noro 3861: \EG non-negative integer
1.1 noro 3862: @item dpoly
1.25 ! noro 3863: \JP 分散表現多項式
1.2 noro 3864: \EG distributed polynomial
1.1 noro 3865: @item onoff
1.25 ! noro 3866: \JP フラグ
1.2 noro 3867: \EG flag
1.1 noro 3868: @end table
3869:
3870: @itemize @bullet
1.2 noro 3871: \BJP
1.1 noro 3872: @item
1.25 ! noro 3873: @code{dp_td()} は, 頭項の全次数, すなわち各変数の指数の和を返す.
1.1 noro 3874: @item
1.25 ! noro 3875: 分散表現多項式が生成されると, @code{sugar} と呼ばれるある整数が付与
! 3876: される. この値は 仮想的に斉次化して計算した場合に結果が持つ全次数の値となる.
1.1 noro 3877: @item
1.25 ! noro 3878: @code{sugar} は, グレブナ基底計算における正規化対の選択のストラテジを
! 3879: 決定するための重要な指針となる.
1.2 noro 3880: \E
3881: \BEG
3882: @item
3883: Function @code{dp_td()} returns the total degree of the head term,
3884: i.e., the sum of all exponent of variables in that term.
3885: @item
3886: Upon creation of a distributed polynomial, an integer called @code{sugar}
3887: is associated. This value is
3888: the total degree of the virtually homogenized one of the original
3889: polynomial.
3890: @item
3891: The quantity @code{sugar} is an important guide to determine the
3892: selection strategy of critical pairs in Groebner basis computation.
3893: \E
1.1 noro 3894: @end itemize
3895:
3896: @example
3897: [74] dp_ord(0)$
3898: [75] X=<<1,2>>+<<0,1>>$
3899: [76] Y=<<1,2>>+<<1,0>>$
3900: [77] Z=X-Y;
3901: (-1)*<<1,0>>+(1)*<<0,1>>
3902: [78] dp_sugar(T);
3903: 3
3904: @end example
3905:
1.25 ! noro 3906: \JP @node dp_lcm,,, グレブナ基底に関する函数
1.2 noro 3907: \EG @node dp_lcm,,, Functions for Groebner basis computation
1.1 noro 3908: @subsection @code{dp_lcm}
3909: @findex dp_lcm
3910:
3911: @table @t
3912: @item dp_lcm(@var{dpoly1},@var{dpoly2})
1.25 ! noro 3913: \JP :: 最小公倍項を返す.
1.2 noro 3914: \EG :: Returns the least common multiple of the head terms of the given two polynomials.
1.1 noro 3915: @end table
3916:
3917: @table @var
3918: @item return
1.25 ! noro 3919: \JP 分散表現多項式
1.2 noro 3920: \EG distributed polynomial
1.4 noro 3921: @item dpoly1 dpoly2
1.25 ! noro 3922: \JP 分散表現多項式
1.2 noro 3923: \EG distributed polynomial
1.1 noro 3924: @end table
3925:
3926: @itemize @bullet
1.2 noro 3927: \BJP
1.1 noro 3928: @item
1.25 ! noro 3929: それぞれの引数の頭項の最小公倍項を返す. 係数は 1 である.
1.2 noro 3930: \E
3931: \BEG
3932: @item
3933: Returns the least common multiple of the head terms of the given
3934: two polynomials, where coefficient is always set to 1.
3935: \E
1.1 noro 3936: @end itemize
3937:
3938: @example
3939: [100] dp_lcm(<<1,2,3,4,5>>,<<5,4,3,2,1>>);
3940: (1)*<<5,4,3,4,5>>
3941: @end example
3942:
3943: @table @t
1.25 ! noro 3944: \JP @item 参照
1.2 noro 3945: \EG @item References
1.1 noro 3946: @fref{p_nf p_nf_mod p_true_nf p_true_nf_mod}.
3947: @end table
3948:
1.25 ! noro 3949: \JP @node dp_redble,,, グレブナ基底に関する函数
1.2 noro 3950: \EG @node dp_redble,,, Functions for Groebner basis computation
1.1 noro 3951: @subsection @code{dp_redble}
3952: @findex dp_redble
3953:
3954: @table @t
3955: @item dp_redble(@var{dpoly1},@var{dpoly2})
1.25 ! noro 3956: \JP :: 頭項どうしが整除可能かどうか調べる.
1.2 noro 3957: \EG :: Checks whether one head term is divisible by the other head term.
1.1 noro 3958: @end table
3959:
3960: @table @var
3961: @item return
1.25 ! noro 3962: \JP 整数
1.2 noro 3963: \EG integer
1.4 noro 3964: @item dpoly1 dpoly2
1.25 ! noro 3965: \JP 分散表現多項式
1.2 noro 3966: \EG distributed polynomial
1.1 noro 3967: @end table
3968:
3969: @itemize @bullet
1.2 noro 3970: \BJP
1.1 noro 3971: @item
1.25 ! noro 3972: @var{dpoly1} の頭項が @var{dpoly2} の頭項で割り切れれば 1, 割り切れなければ
! 3973: 0 を返す.
1.1 noro 3974: @item
1.25 ! noro 3975: 多項式の簡約を行う際, どの項を簡約できるかを探すのに用いる.
1.2 noro 3976: \E
3977: \BEG
3978: @item
3979: Returns 1 if the head term of @var{dpoly2} divides the head term of
3980: @var{dpoly1}; otherwise 0.
3981: @item
3982: Used for finding candidate terms at reduction of polynomials.
3983: \E
1.1 noro 3984: @end itemize
3985:
3986: @example
3987: [148] C;
3988: (1)*<<1,1,1,0,0>>+(1)*<<0,1,1,1,0>>+(1)*<<1,1,0,0,1>>+(1)*<<1,0,0,1,1>>
3989: [149] T;
3990: (3)*<<2,1,0,0,0>>+(3)*<<1,2,0,0,0>>+(1)*<<0,3,0,0,0>>+(6)*<<1,1,1,0,0>>
3991: [150] for ( ; T; T = dp_rest(T)) print(dp_redble(T,C));
3992: 0
3993: 0
3994: 0
3995: 1
3996: @end example
3997:
3998: @table @t
1.25 ! noro 3999: \JP @item 参照
1.2 noro 4000: \EG @item References
1.1 noro 4001: @fref{dp_red dp_red_mod}.
4002: @end table
4003:
1.25 ! noro 4004: \JP @node dpm_redble,,, グレブナ基底に関する函数
1.23 noro 4005: \EG @node dpm_redble,,, Functions for Groebner basis computation
4006: @subsection @code{dpm_redble}
4007: @findex dpm_redble
4008:
4009: @table @t
4010: @item dpm_redble(@var{dpoly1},@var{dpoly2})
1.25 ! noro 4011: \JP :: 頭項どうしが整除可能かどうか調べる.
1.23 noro 4012: \EG :: Checks whether one head term is divisible by the other head term.
4013: @end table
4014:
4015: @table @var
4016: @item return
1.25 ! noro 4017: \JP 整数
1.23 noro 4018: \EG integer
4019: @item dpoly1 dpoly2
1.25 ! noro 4020: \JP 加群多項式
1.23 noro 4021: \EG module polynomial
4022: @end table
4023:
4024: @itemize @bullet
4025: \BJP
4026: @item
1.25 ! noro 4027: @var{dpoly1} の頭項が @var{dpoly2} の頭項で割り切れれば 1, 割り切れなければ
! 4028: 0 を返す.
1.23 noro 4029: @item
1.25 ! noro 4030: 多項式の簡約を行う際, どの項を簡約できるかを探すのに用いる.
1.23 noro 4031: \E
4032: \BEG
4033: @item
4034: Returns 1 if the head term of @var{dpoly2} divides the head term of
4035: @var{dpoly1}; otherwise 0.
4036: @item
4037: Used for finding candidate terms at reduction of polynomials.
4038: \E
4039: @end itemize
4040:
1.25 ! noro 4041: \JP @node dp_subd,,, グレブナ基底に関する函数
1.2 noro 4042: \EG @node dp_subd,,, Functions for Groebner basis computation
1.1 noro 4043: @subsection @code{dp_subd}
4044: @findex dp_subd
4045:
4046: @table @t
4047: @item dp_subd(@var{dpoly1},@var{dpoly2})
1.25 ! noro 4048: \JP :: 頭項の商単項式を返す.
1.2 noro 4049: \EG :: Returns the quotient monomial of the head terms.
1.1 noro 4050: @end table
4051:
4052: @table @var
4053: @item return
1.25 ! noro 4054: \JP 分散表現多項式
1.2 noro 4055: \EG distributed polynomial
1.4 noro 4056: @item dpoly1 dpoly2
1.25 ! noro 4057: \JP 分散表現多項式
1.2 noro 4058: \EG distributed polynomial
1.1 noro 4059: @end table
4060:
4061: @itemize @bullet
1.2 noro 4062: \BJP
1.1 noro 4063: @item
1.25 ! noro 4064: @code{dp_ht(@var{dpoly1})/dp_ht(@var{dpoly2})} を求める. 結果の係数は 1
! 4065: である.
1.1 noro 4066: @item
1.25 ! noro 4067: 割り切れることがあらかじめわかっている必要がある.
1.2 noro 4068: \E
4069: \BEG
4070: @item
4071: Gets @code{dp_ht(@var{dpoly1})/dp_ht(@var{dpoly2})}.
4072: The coefficient of the result is always set to 1.
4073: @item
4074: Divisibility assumed.
4075: \E
1.1 noro 4076: @end itemize
4077:
4078: @example
4079: [162] dp_subd(<<1,2,3,4,5>>,<<1,1,2,3,4>>);
4080: (1)*<<0,1,1,1,1>>
4081: @end example
4082:
4083: @table @t
1.25 ! noro 4084: \JP @item 参照
1.2 noro 4085: \EG @item References
1.1 noro 4086: @fref{dp_red dp_red_mod}.
4087: @end table
4088:
1.25 ! noro 4089: \JP @node dp_vtoe dp_etov,,, グレブナ基底に関する函数
1.2 noro 4090: \EG @node dp_vtoe dp_etov,,, Functions for Groebner basis computation
1.1 noro 4091: @subsection @code{dp_vtoe}, @code{dp_etov}
4092: @findex dp_vtoe
4093: @findex dp_etov
4094:
4095: @table @t
4096: @item dp_vtoe(@var{vect})
1.25 ! noro 4097: \JP :: 指数ベクトルを項に変換
1.2 noro 4098: \EG :: Converts an exponent vector into a term.
1.1 noro 4099: @item dp_etov(@var{dpoly})
1.25 ! noro 4100: \JP :: 頭項を指数ベクトルに変換
1.2 noro 4101: \EG :: Convert the head term of a distributed polynomial into an exponent vector.
1.1 noro 4102: @end table
4103:
4104: @table @var
4105: @item return
1.25 ! noro 4106: \JP @code{dp_vtoe} : 分散表現多項式, @code{dp_etov} : ベクトル
1.2 noro 4107: \EG @code{dp_vtoe} : distributed polynomial, @code{dp_etov} : vector
1.1 noro 4108: @item vect
1.25 ! noro 4109: \JP ベクトル
1.2 noro 4110: \EG vector
1.1 noro 4111: @item dpoly
1.25 ! noro 4112: \JP 分散表現多項式
1.2 noro 4113: \EG distributed polynomial
1.1 noro 4114: @end table
4115:
4116: @itemize @bullet
1.2 noro 4117: \BJP
1.1 noro 4118: @item
1.25 ! noro 4119: @code{dp_vtoe()} は, ベクトル @var{vect} を指数ベクトルとする項を生成する.
1.1 noro 4120: @item
1.25 ! noro 4121: @code{dp_etov()} は, 分散表現多項式 @code{dpoly} の頭項の指数ベクトルを
! 4122: ベクトルに変換する.
1.2 noro 4123: \E
4124: \BEG
4125: @item
4126: @code{dp_vtoe()} generates a term whose exponent vector is @var{vect}.
4127: @item
4128: @code{dp_etov()} generates a vector which is the exponent vector of the
4129: head term of @code{dpoly}.
4130: \E
1.1 noro 4131: @end itemize
4132:
4133: @example
4134: [211] X=<<1,2,3>>;
4135: (1)*<<1,2,3>>
4136: [212] V=dp_etov(X);
4137: [ 1 2 3 ]
4138: [213] V[2]++$
4139: [214] Y=dp_vtoe(V);
4140: (1)*<<1,2,4>>
4141: @end example
4142:
1.25 ! noro 4143: \JP @node dp_mbase,,, グレブナ基底に関する函数
1.2 noro 4144: \EG @node dp_mbase,,, Functions for Groebner basis computation
1.1 noro 4145: @subsection @code{dp_mbase}
4146: @findex dp_mbase
4147:
4148: @table @t
4149: @item dp_mbase(@var{dplist})
1.25 ! noro 4150: \JP :: monomial 基底の計算
1.2 noro 4151: \EG :: Computes the monomial basis
1.1 noro 4152: @end table
4153:
4154: @table @var
4155: @item return
1.25 ! noro 4156: \JP 分散表現多項式のリスト
1.2 noro 4157: \EG list of distributed polynomial
1.1 noro 4158: @item dplist
1.25 ! noro 4159: \JP 分散表現多項式のリスト
1.2 noro 4160: \EG list of distributed polynomial
1.1 noro 4161: @end table
4162:
4163: @itemize @bullet
1.2 noro 4164: \BJP
1.1 noro 4165: @item
1.25 ! noro 4166: ある順序でグレブナ基底となっている多項式集合の, その順序に関する分散表現
! 4167: である @var{dplist} について,
! 4168: @var{dplist} が K[X] 中で生成するイデアル I が 0 次元の時,
! 4169: K 上有限次元線形空間である K[X]/I の monomial による基底を求める.
1.1 noro 4170: @item
1.25 ! noro 4171: 得られた基底の個数が, K[X]/I の K-線形空間としての次元に等しい.
1.2 noro 4172: \E
4173: \BEG
4174: @item
4175: Assuming that @var{dplist} is a list of distributed polynomials which
4176: is a Groebner basis with respect to the current ordering type and
4177: that the ideal @var{I} generated by @var{dplist} in K[X] is zero-dimensional,
4178: this function computes the monomial basis of a finite dimenstional K-vector
4179: space K[X]/I.
4180: @item
4181: The number of elements in the monomial basis is equal to the
4182: K-dimenstion of K[X]/I.
4183: \E
1.1 noro 4184: @end itemize
4185:
4186: @example
4187: [215] K=katsura(5)$
4188: [216] V=[u5,u4,u3,u2,u1,u0]$
4189: [217] G0=gr(K,V,0)$
4190: [218] H=map(dp_ptod,G0,V)$
4191: [219] map(dp_ptod,dp_mbase(H),V)$
4192: [u0^5,u4*u0^3,u3*u0^3,u2*u0^3,u1*u0^3,u0^4,u3^2*u0,u2*u3*u0,u1*u3*u0,
4193: u1*u2*u0,u1^2*u0,u4*u0^2,u3*u0^2,u2*u0^2,u1*u0^2,u0^3,u3^2,u2*u3,u1*u3,
4194: u1*u2,u1^2,u4*u0,u3*u0,u2*u0,u1*u0,u0^2,u4,u3,u2,u1,u0,1]
4195: @end example
4196:
4197: @table @t
1.25 ! noro 4198: \JP @item 参照
1.2 noro 4199: \EG @item References
1.1 noro 4200: @fref{gr hgr gr_mod}.
4201: @end table
4202:
1.25 ! noro 4203: \JP @node dp_mag,,, グレブナ基底に関する函数
1.2 noro 4204: \EG @node dp_mag,,, Functions for Groebner basis computation
1.1 noro 4205: @subsection @code{dp_mag}
4206: @findex dp_mag
4207:
4208: @table @t
4209: @item dp_mag(@var{p})
1.25 ! noro 4210: \JP :: 係数のビット長の和を返す
1.2 noro 4211: \EG :: Computes the sum of bit lengths of coefficients of a distributed polynomial.
1.1 noro 4212: @end table
4213:
4214: @table @var
4215: @item return
1.25 ! noro 4216: \JP 数
1.2 noro 4217: \EG integer
1.1 noro 4218: @item p
1.25 ! noro 4219: \JP 分散表現多項式
1.2 noro 4220: \EG distributed polynomial
1.1 noro 4221: @end table
4222:
4223: @itemize @bullet
1.2 noro 4224: \BJP
1.1 noro 4225: @item
1.25 ! noro 4226: 分散表現多項式の係数に現れる有理数につき, その分母分子 (整数の場合は分子)
! 4227: のビット長の総和を返す.
1.1 noro 4228: @item
1.25 ! noro 4229: 対象となる多項式の大きさの目安として有効である. 特に, 0 次元システムにおいては
! 4230: 係数膨張が問題となり, 途中生成される多項式が係数膨張を起こしているかどうか
! 4231: の判定に役立つ.
1.1 noro 4232: @item
1.25 ! noro 4233: @code{dp_gr_flags()} で, @code{ShowMag}, @code{Print} を on にすることにより
! 4234: 途中生成される多項式にたいする @code{dp_mag()} の値を見ることができる.
1.2 noro 4235: \E
4236: \BEG
4237: @item
4238: This function computes the sum of bit lengths of coefficients of a
4239: distributed polynomial @var{p}. If a coefficient is non integral,
4240: the sum of bit lengths of the numerator and the denominator is taken.
4241: @item
4242: This is a measure of the size of a polynomial. Especially for
4243: zero-dimensional system coefficient swells are often serious and
4244: the returned value is useful to detect such swells.
4245: @item
4246: If @code{ShowMag} and @code{Print} for @code{dp_gr_flags()} are on,
4247: values of @code{dp_mag()} for intermediate basis elements are shown.
4248: \E
1.1 noro 4249: @end itemize
4250:
4251: @example
4252: [221] X=dp_ptod((x+2*y)^10,[x,y])$
4253: [222] dp_mag(X);
4254: 115
4255: @end example
4256:
4257: @table @t
1.25 ! noro 4258: \JP @item 参照
1.2 noro 4259: \EG @item References
1.1 noro 4260: @fref{dp_gr_flags dp_gr_print}.
4261: @end table
4262:
1.25 ! noro 4263: \JP @node dp_red dp_red_mod,,, グレブナ基底に関する函数
1.2 noro 4264: \EG @node dp_red dp_red_mod,,, Functions for Groebner basis computation
1.1 noro 4265: @subsection @code{dp_red}, @code{dp_red_mod}
4266: @findex dp_red
4267: @findex dp_red_mod
4268:
4269: @table @t
4270: @item dp_red(@var{dpoly1},@var{dpoly2},@var{dpoly3})
4271: @item dp_red_mod(@var{dpoly1},@var{dpoly2},@var{dpoly3},@var{mod})
1.25 ! noro 4272: \JP :: 一回の簡約操作
1.2 noro 4273: \EG :: Single reduction operation
1.1 noro 4274: @end table
4275:
4276: @table @var
4277: @item return
1.25 ! noro 4278: \JP リスト
1.2 noro 4279: \EG list
1.4 noro 4280: @item dpoly1 dpoly2 dpoly3
1.25 ! noro 4281: \JP 分散表現多項式
1.2 noro 4282: \EG distributed polynomial
1.1 noro 4283: @item vlist
1.25 ! noro 4284: \JP リスト
1.2 noro 4285: \EG list
1.1 noro 4286: @item mod
1.25 ! noro 4287: \JP 素数
1.2 noro 4288: \EG prime
1.1 noro 4289: @end table
4290:
4291: @itemize @bullet
1.2 noro 4292: \BJP
1.1 noro 4293: @item
1.25 ! noro 4294: @var{dpoly1} + @var{dpoly2} なる分散表現多項式を @var{dpoly3} で
! 4295: 1 回簡約する.
1.1 noro 4296: @item
1.25 ! noro 4297: @code{dp_red_mod()} の入力は, 全て有限体係数に変換されている必要がある.
1.1 noro 4298: @item
1.25 ! noro 4299: 簡約される項は @var{dpoly2} の頭項である. 従って, @var{dpoly2} の
! 4300: 頭項が @var{dpoly3} の頭項で割り切れることがあらかじめわかっていなければ
! 4301: ならない.
1.1 noro 4302: @item
1.25 ! noro 4303: 引数が整数係数の時, 簡約は, 分数が現れないよう, 整数 @var{a}, @var{b},
! 4304: 項 @var{t} により @var{a}(@var{dpoly1} + @var{dpoly2})-@var{bt} @var{dpoly3} として計算される.
1.1 noro 4305: @item
1.25 ! noro 4306: 結果は, @code{[@var{a dpoly1},@var{a dpoly2 - bt dpoly3}]} なるリストである.
1.2 noro 4307: \E
4308: \BEG
4309: @item
4310: Reduces a distributed polynomial, @var{dpoly1} + @var{dpoly2},
4311: by @var{dpoly3} for single time.
4312: @item
4313: An input for @code{dp_red_mod()} must be converted into a distributed
4314: polynomial with coefficients in a finite field.
4315: @item
4316: This implies that
4317: the divisibility of the head term of @var{dpoly2} by the head term of
4318: @var{dpoly3} is assumed.
4319: @item
4320: When integral coefficients, computation is so carefully performed that
4321: no rational operations appear in the reduction procedure.
4322: It is computed for integers @var{a} and @var{b}, and a term @var{t} as:
1.4 noro 4323: @var{a}(@var{dpoly1} + @var{dpoly2})-@var{bt} @var{dpoly3}.
1.2 noro 4324: @item
4325: The result is a list @code{[@var{a dpoly1},@var{a dpoly2 - bt dpoly3}]}.
4326: \E
1.1 noro 4327: @end itemize
4328:
4329: @example
4330: [157] D=(3)*<<2,1,0,0,0>>+(3)*<<1,2,0,0,0>>+(1)*<<0,3,0,0,0>>;
4331: (3)*<<2,1,0,0,0>>+(3)*<<1,2,0,0,0>>+(1)*<<0,3,0,0,0>>
4332: [158] R=(6)*<<1,1,1,0,0>>;
4333: (6)*<<1,1,1,0,0>>
4334: [159] C=12*<<1,1,1,0,0>>+(1)*<<0,1,1,1,0>>+(1)*<<1,1,0,0,1>>;
4335: (12)*<<1,1,1,0,0>>+(1)*<<0,1,1,1,0>>+(1)*<<1,1,0,0,1>>
4336: [160] dp_red(D,R,C);
1.5 noro 4337: [(6)*<<2,1,0,0,0>>+(6)*<<1,2,0,0,0>>+(2)*<<0,3,0,0,0>>,
4338: (-1)*<<0,1,1,1,0>>+(-1)*<<1,1,0,0,1>>]
1.1 noro 4339: @end example
4340:
4341: @table @t
1.25 ! noro 4342: \JP @item 参照
1.2 noro 4343: \EG @item References
1.1 noro 4344: @fref{dp_mod dp_rat}.
4345: @end table
4346:
1.25 ! noro 4347: \JP @node dp_sp dp_sp_mod,,, グレブナ基底に関する函数
1.2 noro 4348: \EG @node dp_sp dp_sp_mod,,, Functions for Groebner basis computation
1.1 noro 4349: @subsection @code{dp_sp}, @code{dp_sp_mod}
4350: @findex dp_sp
4351: @findex dp_sp_mod
4352:
4353: @table @t
4354: @item dp_sp(@var{dpoly1},@var{dpoly2})
4355: @item dp_sp_mod(@var{dpoly1},@var{dpoly2},@var{mod})
1.25 ! noro 4356: \JP :: S-多項式の計算
1.2 noro 4357: \EG :: Computation of an S-polynomial
1.1 noro 4358: @end table
4359:
4360: @table @var
4361: @item return
1.25 ! noro 4362: \JP 分散表現多項式
1.2 noro 4363: \EG distributed polynomial
1.4 noro 4364: @item dpoly1 dpoly2
1.25 ! noro 4365: \JP 分散表現多項式
1.2 noro 4366: \EG distributed polynomial
1.1 noro 4367: @item mod
1.25 ! noro 4368: \JP 素数
1.2 noro 4369: \EG prime
1.1 noro 4370: @end table
4371:
4372: @itemize @bullet
1.2 noro 4373: \BJP
1.1 noro 4374: @item
1.25 ! noro 4375: @var{dpoly1}, @var{dpoly2} の S-多項式を計算する.
1.1 noro 4376: @item
1.25 ! noro 4377: @code{dp_sp_mod()} の入力は, 全て有限体係数に変換されている必要がある.
1.1 noro 4378: @item
1.25 ! noro 4379: 結果に有理数, 有理式が入るのを避けるため, 結果が定数倍, あるいは多項式
! 4380: 倍されている可能性がある.
1.2 noro 4381: \E
4382: \BEG
4383: @item
4384: This function computes the S-polynomial of @var{dpoly1} and @var{dpoly2}.
4385: @item
4386: Inputs of @code{dp_sp_mod()} must be polynomials with coefficients in a
4387: finite field.
4388: @item
4389: The result may be multiplied by a constant in the ground field in order to
4390: make the result integral.
4391: \E
1.1 noro 4392: @end itemize
4393:
4394: @example
4395: [227] X=dp_ptod(x^2*y+x*y,[x,y]);
4396: (1)*<<2,1>>+(1)*<<1,1>>
4397: [228] Y=dp_ptod(x*y^2+x*y,[x,y]);
4398: (1)*<<1,2>>+(1)*<<1,1>>
4399: [229] dp_sp(X,Y);
4400: (-1)*<<2,1>>+(1)*<<1,2>>
4401: @end example
4402:
4403: @table @t
1.25 ! noro 4404: \JP @item 参照
1.2 noro 4405: \EG @item References
1.1 noro 4406: @fref{dp_mod dp_rat}.
4407: @end table
1.23 noro 4408:
1.25 ! noro 4409: \JP @node dpm_sp,,, グレブナ基底に関する函数
1.23 noro 4410: \EG @node dmp_sp,,, Functions for Groebner basis computation
4411: @subsection @code{dpm_sp}
4412: @findex dpm_sp
4413:
4414: @table @t
4415: @item dpm_sp(@var{dpoly1},@var{dpoly2}[|coef=1])
1.25 ! noro 4416: \JP :: S-多項式の計算
1.23 noro 4417: \EG :: Computation of an S-polynomial
4418: @end table
4419:
4420: @table @var
4421: @item return
1.25 ! noro 4422: \JP 加群多項式またはリスト
1.23 noro 4423: \EG module polynomial or list
4424: @item dpoly1 dpoly2
1.25 ! noro 4425: \JP 加群多項式
1.23 noro 4426: \EG module polynomial
1.25 ! noro 4427: \JP 分散表現多項式
1.23 noro 4428: @end table
4429:
4430: @itemize @bullet
4431: \BJP
4432: @item
1.25 ! noro 4433: @var{dpoly1}, @var{dpoly2} の S-多項式を計算する.
1.23 noro 4434: @item
1.25 ! noro 4435: オプション @var{coef=1} が指定されている場合, @code{[S,t1,t2]} なるリストを返す.
! 4436: ここで, @code{t1}, @code{t2} はS-多項式を作る際の係数単項式で @code{S=t1 dpoly1-t2 dpoly2}
! 4437: を満たす.
1.23 noro 4438: \E
4439: \BEG
4440: @item
4441: This function computes the S-polynomial of @var{dpoly1} and @var{dpoly2}.
4442: @item
4443: If an option @var{coef=1} is specified, it returns a list @code{[S,t1,t2]},
4444: where @code{S} is the S-polynmial and @code{t1}, @code{t2} are monomials satisfying @code{S=t1 dpoly1-t2 dpoly2}.
4445: \E
4446: @end itemize
4447:
1.25 ! noro 4448: \JP @node dpm_schreyer_base,,, グレブナ基底に関する函数
! 4449: \EG @node dmp_schreyer_base,,, Functions for Groebner basis computation
! 4450: @subsection @code{dpm_schreyer_base}
! 4451: @findex dpm_schreyer_base
! 4452:
! 4453: @table @t
! 4454: @item dpm_schreyer_base(@var{G})
! 4455: \JP :: szygy 加群のグレブナー基底の計算
! 4456: \EG :: Computation of a Groebner basis of the syzygy module
! 4457: @end table
! 4458:
! 4459: @table @var
! 4460: @item return
! 4461: \JP 加群多項式リスト
! 4462: \EG list of module polynomials
! 4463: @item G
! 4464: \JP 加群多項式リスト
! 4465: \EG list of module polynomials
! 4466: @end table
! 4467:
! 4468: @itemize @bullet
! 4469: \BJP
! 4470: @item
! 4471: 加群多項式で表された簡約グレブナー基底 @var{G} に対し, @var{syz(G)} の極小グレブナー基底を計算して返す.
! 4472: @item
! 4473: 得られる結果は, @var{G} の先頭項から定まる Schreyer 順序に関するグレブナー基底である.
! 4474: 副作用として, この Schreyer 順序が自動的に設定される.
! 4475: \E
! 4476: \BEG
! 4477: @item
! 4478: This function computes a minimal Groebner basis of @var{syz(G)} for a Groenber basis @var{G}
! 4479: that is represented as a list of module polynomials.
! 4480: @item
! 4481: The result is a Groebner basis with respect to a Schreyer ordering determined by the leading terms of
! 4482: @var{G}. As a side effect, this Schreyer ordering is autoatically set.
! 4483: \E
! 4484: @end itemize
! 4485:
! 4486: \JP @node dpm_schreyer_frame,,, グレブナ基底に関する函数
! 4487: \EG @node dmp_schreyer_frame,,, Functions for Groebner basis computation
! 4488: @subsection @code{dpm_schreyer_frame}
! 4489: @findex dpm_schreyer_frame
! 4490:
! 4491: @table @t
! 4492: @item dpm_schreyer_frame(@var{G})
! 4493: \JP :: Schreyer フレームの計算
! 4494: \EG :: Computation of the Schreyer frame
! 4495: @end table
! 4496:
! 4497: @table @var
! 4498: @item return
! 4499: \JP 加群単項式リストのリスト
! 4500: \EG a list of lists of module monomials
! 4501: @item G
! 4502: \JP 加群多項式リスト
! 4503: \EG list of module polynomials
! 4504: @end table
! 4505:
! 4506: @itemize @bullet
! 4507: \BJP
! 4508: @item
! 4509: @var{G} の先頭項からスタートして, Schreyer フレーム, すなわち Schreyer の自由分解に現れるグレブナー基底の,
! 4510: Schreyer 順序に関する先頭単項式を計算する.
! 4511: @item
! 4512: 得られる結果は, 自由分解における F_i の標準基底の像の先頭単項式のリスト M_i のリスト
! 4513: [M_m,...,M_1] である.
! 4514: @item
! 4515: 副作用として, 各レベルにおける Schreyer 順序を設定するためのデータが作られる. このデータは
! 4516: @code{dpm_set_schreyer_level} により, 各レベルの Schreyer 順序を設定する際に用いられる.
! 4517: \E
! 4518: \BEG
! 4519: @item
! 4520: This function computes the Schreyer frame starting from a Groebner basis @var{G}, that is the lists of leading monomials of Groebner bases
! 4521: of syzygy modules with respect to Schreyer orderings in the Schreyer free resolution.
! 4522: @item
! 4523: The result is a list @var{[Mm,...,M1]}, where @var{Mi} is the list of leading monomials of
! 4524: the images of standard bases of the free module @var{Fi} in the Schreyer free resolution.
! 4525: @item
! 4526: As a by-product, data for setting a Schreyer order in each level are created. The date are
! 4527: used by @code{dpm_set_schreyer_level} for setting a Schreyer order in each level.
! 4528: \E
! 4529: @end itemize
! 4530:
! 4531: \JP @node dpm_set_schreyer_level,,, グレブナ基底に関する函数
! 4532: \EG @node dmp_set_schreyer_level,,, Functions for Groebner basis computation
! 4533: @subsection @code{dpm_set_schreyer_level}
! 4534: @findex dpm_set_schreyer_level
! 4535:
! 4536: @table @t
! 4537: @item dpm_set_schreyer_level(@var{L})
! 4538: \JP :: 指定されたレベルの Schreyer ordering の設定
! 4539: \EG :: Setting the Schreyer ordering of a specified level
! 4540: @end table
! 4541:
! 4542: @table @var
! 4543: @item return
! 4544: \JP 非負整数
! 4545: \EG a non-negative integer
! 4546: @item G
! 4547: \JP 非負整数
! 4548: \EG a non-negative integer
! 4549: @end table
! 4550:
! 4551: @itemize @bullet
! 4552: \BJP
! 4553: @item
! 4554: @var{G} の先頭項からスタートして, Schreyer フレーム, すなわち Schreyer の自由分解に現れるグレブナー基底の,
! 4555: Schreyer 順序に関する先頭単項式を計算する.
! 4556: @item
! 4557: 得られる結果は, 自由分解における F_i の標準基底の像の先頭単項式のリスト M_i のリスト
! 4558: [M_m,...,M_1] である.
! 4559: @item
! 4560: 副作用として, 各レベルにおける Schreyer 順序を設定するためのデータが作られる. このデータは
! 4561: @code{dpm_set_schreyer_level} により, 各レベルの Schreyer 順序を設定する際に用いられる.
! 4562: \E
! 4563: \BEG
! 4564: @item
! 4565: This function computes the Schreyer frame starting from a Groebner basis @var{G}, that is the lists of leading monomials of Groebner bases
! 4566: of syzygy modules with respect to Schreyer orderings in the Schreyer free resolution.
! 4567: @item
! 4568: The result is a list @var{[Mm,...,M1]}, where @var{Mi} is the list of leading monomials of
! 4569: the images of standard bases of the free module @var{Fi} in the Schreyer free resolution.
! 4570: @item
! 4571: As a by-product, data for setting a Schreyer order in each level are created. The date are
! 4572: used by @code{dpm_set_schreyer_level} for setting a Schreyer order in each level.
! 4573: \E
! 4574: @end itemize
! 4575:
! 4576: \JP @node dpm_sp_nf,,, グレブナ基底に関する函数
! 4577: \EG @node dmp_sp_nf,,, Functions for Groebner basis computation
! 4578: @subsection @code{dpm_sp_nf}
! 4579: @findex dpm_sp_nf
! 4580:
! 4581: @table @t
! 4582: @item dpm_sp_nf(@var{C},@var{Z},@var{P},@var{Q})
! 4583: \JP :: S-多項式を多項式配列で割った余りの計算
! 4584: \EG :: Computation of a remainder of an S-polynomial modulo a polynomial array
! 4585: @end table
! 4586:
! 4587: @table @var
! 4588: @item return
! 4589: \JP 加群単項式のリスト
! 4590: \EG a list of module monomials
! 4591: @item C
! 4592: \JP 加群多項式配列
! 4593: \EG an array of module polynomials
! 4594: @item Z
! 4595: \JP 整数リストの配列
! 4596: \EG an array of integer lists
! 4597: @item P
! 4598: @itemx Q
! 4599: \JP 整数
! 4600: \EG integers
! 4601: @end table
! 4602:
! 4603: @itemize @bullet
! 4604: \BJP
! 4605: @item
! 4606: C[P], C[Q] の S-多項式を C で割った余り f が
! 4607: ct C[P]-c't'C[Q]=g1C[1]+...+gLC[L]+f と表されるとき
! 4608: g'=ct e_P-c't' e_Q-(g1 e_1+...+gL e_L) に対し [g',f] を返す.
! 4609: @item
! 4610: 配列 @var{Z} の第 I 成分は, 先頭項の位置が @var{I} であるような @var{C} の元の配列インデックスのリストである.
! 4611: \E
! 4612: \BEG
! 4613: @item
! 4614: When the remainder of the S-polynomial of @var{C[P]} and @var{C[Q]} modulo @var{C}
! 4615: is represented as @var{ct C[P]-c't'C[Q]=g1C[1]+...+gLC[L]+f},
! 4616: this function returns a list @var{[g',f]}, where @var{g'=ct eP-c't' eQ-(g1 e1+...+gL eL}.
! 4617: @item
! 4618: The @var{I}-th element of an array @var{Z} is a list of indices of elements of @var{C}
! 4619: whose leading position is @var{I}.
! 4620: \E
! 4621: @end itemize
! 4622:
! 4623:
! 4624:
! 4625: \JP @node p_nf p_nf_mod p_true_nf p_true_nf_mod,,, グレブナ基底に関する函数
1.2 noro 4626: \EG @node p_nf p_nf_mod p_true_nf p_true_nf_mod,,, Functions for Groebner basis computation
1.1 noro 4627: @subsection @code{p_nf}, @code{p_nf_mod}, @code{p_true_nf}, @code{p_true_nf_mod}
4628: @findex p_nf
4629: @findex p_nf_mod
4630: @findex p_true_nf
4631: @findex p_true_nf_mod
4632:
4633: @table @t
4634: @item p_nf(@var{poly},@var{plist},@var{vlist},@var{order})
4635: @itemx p_nf_mod(@var{poly},@var{plist},@var{vlist},@var{order},@var{mod})
1.25 ! noro 4636: \JP :: 表現多項式の正規形を求める. (結果は定数倍されている可能性あり)
1.2 noro 4637: \BEG
4638: :: Computes the normal form of the given polynomial.
4639: (The result may be multiplied by a constant.)
4640: \E
1.1 noro 4641: @item p_true_nf(@var{poly},@var{plist},@var{vlist},@var{order})
4642: @itemx p_true_nf_mod(@var{poly},@var{plist},@var{vlist},@var{order},@var{mod})
1.25 ! noro 4643: \JP :: 表現多項式の正規形を求める. (真の結果を @code{[分子, 分母]} の形で返す)
1.2 noro 4644: \BEG
4645: :: Computes the normal form of the given polynomial. (The result is returned
4646: as a form of @code{[numerator, denominator]})
4647: \E
1.1 noro 4648: @end table
4649:
4650: @table @var
4651: @item return
1.25 ! noro 4652: \JP @code{p_nf} : 多項式, @code{p_true_nf} : リスト
1.2 noro 4653: \EG @code{p_nf} : polynomial, @code{p_true_nf} : list
1.1 noro 4654: @item poly
1.25 ! noro 4655: \JP 多項式
1.2 noro 4656: \EG polynomial
1.4 noro 4657: @item plist vlist
1.25 ! noro 4658: \JP リスト
1.2 noro 4659: \EG list
1.1 noro 4660: @item order
1.25 ! noro 4661: \JP 数, リストまたは行列
1.2 noro 4662: \EG number, list or matrix
1.1 noro 4663: @item mod
1.25 ! noro 4664: \JP 素数
1.2 noro 4665: \EG prime
1.1 noro 4666: @end table
4667:
4668: @itemize @bullet
1.2 noro 4669: \BJP
1.1 noro 4670: @item
1.25 ! noro 4671: @samp{gr} で定義されている.
1.1 noro 4672: @item
1.25 ! noro 4673: 多項式の, 多項式リストによる正規形を求める.
1.1 noro 4674: @item
4675: @code{dp_nf()}, @code{dp_true_nf()}, @code{dp_nf_mod()}, @code{dp_true_nf_mod}
1.25 ! noro 4676: に対するインタフェースである.
1.1 noro 4677: @item
1.25 ! noro 4678: @var{poly} および @var{plist} は, 変数順序 @var{vlist} および
! 4679: 変数順序型 @var{otype} に従って分散表現多項式に変換され,
1.1 noro 4680: @code{dp_nf()}, @code{dp_true_nf()}, @code{dp_nf_mod()},
1.25 ! noro 4681: @code{dp_true_nf_mod()} に渡される.
1.1 noro 4682: @item
4683: @code{dp_nf()}, @code{dp_true_nf()}, @code{dp_nf_mod()},
1.25 ! noro 4684: @code{dp_true_nf_mod()} は @var{fullreduce} が 1 で呼び出される.
1.1 noro 4685: @item
1.25 ! noro 4686: 結果は多項式に変換されて出力される.
1.1 noro 4687: @item
1.25 ! noro 4688: @code{p_true_nf()}, @code{p_true_nf_mod()} の出力に関しては,
! 4689: @code{dp_true_nf()}, @code{dp_true_nf_mod()} の項を参照.
1.2 noro 4690: \E
4691: \BEG
4692: @item
4693: Defined in the package @samp{gr}.
4694: @item
4695: Obtains the normal form of a polynomial by a polynomial list.
4696: @item
4697: These are interfaces to @code{dp_nf()}, @code{dp_true_nf()}, @code{dp_nf_mod()},
4698: @code{dp_true_nf_mod}
4699: @item
4700: The polynomial @var{poly} and the polynomials in @var{plist} is
4701: converted, according to the variable ordering @var{vlist} and
4702: type of term ordering @var{otype}, into their distributed polynomial
4703: counterparts and passed to @code{dp_nf()}.
4704: @item
4705: @code{dp_nf()}, @code{dp_true_nf()}, @code{dp_nf_mod()} and
4706: @code{dp_true_nf_mod()}
4707: is called with value 1 for @var{fullreduce}.
4708: @item
4709: The result is converted back into an ordinary polynomial.
4710: @item
4711: As for @code{p_true_nf()}, @code{p_true_nf_mod()}
4712: refer to @code{dp_true_nf()} and @code{dp_true_nf_mod()}.
4713: \E
1.1 noro 4714: @end itemize
4715:
4716: @example
4717: [79] K = katsura(5)$
4718: [80] V = [u5,u4,u3,u2,u1,u0]$
4719: [81] G = hgr(K,V,2)$
4720: [82] p_nf(K[1],G,V,2);
4721: 0
4722: [83] L = p_true_nf(K[1]+1,G,V,2);
4723: [-1503...,-1503...]
4724: [84] L[0]/L[1];
4725: 1
4726: @end example
4727:
4728: @table @t
1.25 ! noro 4729: \JP @item 参照
1.2 noro 4730: \EG @item References
1.1 noro 4731: @fref{dp_ptod},
4732: @fref{dp_dtop},
4733: @fref{dp_ord},
1.19 noro 4734: @fref{dp_nf dp_nf_mod dp_true_nf dp_true_nf_mod dp_weyl_nf dp_weyl_nf_mod}.
1.1 noro 4735: @end table
4736:
1.25 ! noro 4737: \JP @node p_terms,,, グレブナ基底に関する函数
1.2 noro 4738: \EG @node p_terms,,, Functions for Groebner basis computation
1.1 noro 4739: @subsection @code{p_terms}
4740: @findex p_terms
4741:
4742: @table @t
4743: @item p_terms(@var{poly},@var{vlist},@var{order})
1.25 ! noro 4744: \JP :: 多項式にあらわれる単項をリストにする.
1.2 noro 4745: \EG :: Monomials appearing in the given polynomial is collected into a list.
1.1 noro 4746: @end table
4747:
4748: @table @var
4749: @item return
1.25 ! noro 4750: \JP リスト
1.2 noro 4751: \EG list
1.1 noro 4752: @item poly
1.25 ! noro 4753: \JP 多項式
1.2 noro 4754: \EG polynomial
1.1 noro 4755: @item vlist
1.25 ! noro 4756: \JP リスト
1.2 noro 4757: \EG list
1.1 noro 4758: @item order
1.25 ! noro 4759: \JP 数, リストまたは行列
1.2 noro 4760: \EG number, list or matrix
1.1 noro 4761: @end table
4762:
4763: @itemize @bullet
1.2 noro 4764: \BJP
1.1 noro 4765: @item
1.25 ! noro 4766: @samp{gr} で定義されている.
1.1 noro 4767: @item
1.25 ! noro 4768: 多項式を単項に展開した時に現れる項をリストにして返す.
! 4769: @var{vlist} および @var{order} により定まる項順序により, 順序の高いもの
! 4770: がリストの先頭に来るようにソートされる.
1.1 noro 4771: @item
1.25 ! noro 4772: グレブナ基底はしばしば係数が巨大になるため, 実際にどの項が現れて
! 4773: いるのかを見るためなどに用いる.
1.2 noro 4774: \E
4775: \BEG
4776: @item
4777: Defined in the package @samp{gr}.
4778: @item
4779: This returns a list which contains all non-zero monomials in the given
4780: polynomial. The monomials are ordered according to the current
4781: type of term ordering and @var{vlist}.
4782: @item
4783: Since polynomials in a Groebner base often have very large coefficients,
4784: examining a polynomial as it is may sometimes be difficult to perform.
4785: For such a case, this function enables to examine which term is really
4786: exists.
4787: \E
1.1 noro 4788: @end itemize
4789:
4790: @example
4791: [233] G=gr(katsura(5),[u5,u4,u3,u2,u1,u0],2)$
4792: [234] p_terms(G[0],[u5,u4,u3,u2,u1,u0],2);
1.5 noro 4793: [u5,u0^31,u0^30,u0^29,u0^28,u0^27,u0^26,u0^25,u0^24,u0^23,u0^22,
4794: u0^21,u0^20,u0^19,u0^18,u0^17,u0^16,u0^15,u0^14,u0^13,u0^12,u0^11,
4795: u0^10,u0^9,u0^8,u0^7,u0^6,u0^5,u0^4,u0^3,u0^2,u0,1]
1.1 noro 4796: @end example
4797:
1.25 ! noro 4798: \JP @node gb_comp,,, グレブナ基底に関する函数
1.2 noro 4799: \EG @node gb_comp,,, Functions for Groebner basis computation
1.1 noro 4800: @subsection @code{gb_comp}
4801: @findex gb_comp
4802:
4803: @table @t
4804: @item gb_comp(@var{plist1}, @var{plist2})
1.25 ! noro 4805: \JP :: 多項式リストが, 符号を除いて集合として等しいかどうか調べる.
1.2 noro 4806: \EG :: Checks whether two polynomial lists are equal or not as a set
1.1 noro 4807: @end table
4808:
4809: @table @var
1.25 ! noro 4810: \JP @item return 0 または 1
1.2 noro 4811: \EG @item return 0 or 1
1.4 noro 4812: @item plist1 plist2
1.1 noro 4813: @end table
4814:
4815: @itemize @bullet
1.2 noro 4816: \BJP
1.1 noro 4817: @item
1.25 ! noro 4818: @var{plist1}, @var{plist2} について, 符号を除いて集合として等しいかどうか
! 4819: 調べる.
1.1 noro 4820: @item
1.25 ! noro 4821: 異なる方法で求めたグレブナ基底は, 基底の順序, 符号が異なる場合があり,
! 4822: それらが等しいかどうかを調べるために用いる.
1.2 noro 4823: \E
4824: \BEG
4825: @item
4826: This function checks whether @var{plist1} and @var{plist2} are equal or
4827: not as a set .
4828: @item
4829: For the same input and the same term ordering different
4830: functions for Groebner basis computations may produce different outputs
4831: as lists. This function compares such lists whether they are equal
4832: as a generating set of an ideal.
4833: \E
1.1 noro 4834: @end itemize
4835:
4836: @example
4837: [243] C=cyclic(6)$
4838: [244] V=[c0,c1,c2,c3,c4,c5]$
4839: [245] G0=gr(C,V,0)$
4840: [246] G=tolex(G0,V,0,V)$
4841: [247] GG=lex_tl(C,V,0,V,0)$
4842: [248] gb_comp(G,GG);
4843: 1
4844: @end example
4845:
1.25 ! noro 4846: \JP @node katsura hkatsura cyclic hcyclic,,, グレブナ基底に関する函数
1.2 noro 4847: \EG @node katsura hkatsura cyclic hcyclic,,, Functions for Groebner basis computation
1.1 noro 4848: @subsection @code{katsura}, @code{hkatsura}, @code{cyclic}, @code{hcyclic}
4849: @findex katsura
4850: @findex hkatsura
4851: @findex cyclic
4852: @findex hcyclic
4853:
4854: @table @t
4855: @item katsura(@var{n})
4856: @item hkatsura(@var{n})
4857: @item cyclic(@var{n})
4858: @item hcyclic(@var{n})
1.25 ! noro 4859: \JP :: 多項式リストの生成
1.2 noro 4860: \EG :: Generates a polynomial list of standard benchmark.
1.1 noro 4861: @end table
4862:
4863: @table @var
4864: @item return
1.25 ! noro 4865: \JP リスト
1.2 noro 4866: \EG list
1.1 noro 4867: @item n
1.25 ! noro 4868: \JP 整数
1.2 noro 4869: \EG integer
1.1 noro 4870: @end table
4871:
4872: @itemize @bullet
1.2 noro 4873: \BJP
1.1 noro 4874: @item
1.25 ! noro 4875: @code{katsura()} は @samp{katsura}, @code{cyclic()} は @samp{cyclic}
! 4876: で定義されている.
1.1 noro 4877: @item
1.25 ! noro 4878: グレブナ基底計算でしばしばテスト, ベンチマークに用いられる @code{katsura},
! 4879: @code{cyclic} およびその斉次化を生成する.
1.1 noro 4880: @item
1.25 ! noro 4881: @code{cyclic} は @code{Arnborg}, @code{Lazard}, @code{Davenport} などの
! 4882: 名で呼ばれることもある.
1.2 noro 4883: \E
4884: \BEG
4885: @item
4886: Function @code{katsura()} is defined in @samp{katsura}, and
4887: function @code{cyclic()} in @samp{cyclic}.
4888: @item
4889: These functions generate a series of polynomial sets, respectively,
4890: which are often used for testing and bench marking:
4891: @code{katsura}, @code{cyclic} and their homogenized versions.
4892: @item
4893: Polynomial set @code{cyclic} is sometimes called by other name:
4894: @code{Arnborg}, @code{Lazard}, and @code{Davenport}.
4895: \E
1.1 noro 4896: @end itemize
4897:
4898: @example
4899: [74] load("katsura")$
4900: [79] load("cyclic")$
4901: [89] katsura(5);
4902: [u0+2*u4+2*u3+2*u2+2*u1+2*u5-1,2*u4*u0-u4+2*u1*u3+u2^2+2*u5*u1,
1.5 noro 4903: 2*u3*u0+2*u1*u4-u3+(2*u1+2*u5)*u2,2*u2*u0+2*u2*u4+(2*u1+2*u5)*u3
4904: -u2+u1^2,2*u1*u0+(2*u3+2*u5)*u4+2*u2*u3+2*u1*u2-u1,
1.1 noro 4905: u0^2-u0+2*u4^2+2*u3^2+2*u2^2+2*u1^2+2*u5^2]
4906: [90] hkatsura(5);
4907: [-t+u0+2*u4+2*u3+2*u2+2*u1+2*u5,
4908: -u4*t+2*u4*u0+2*u1*u3+u2^2+2*u5*u1,-u3*t+2*u3*u0+2*u1*u4+(2*u1+2*u5)*u2,
4909: -u2*t+2*u2*u0+2*u2*u4+(2*u1+2*u5)*u3+u1^2,
4910: -u1*t+2*u1*u0+(2*u3+2*u5)*u4+2*u2*u3+2*u1*u2,
4911: -u0*t+u0^2+2*u4^2+2*u3^2+2*u2^2+2*u1^2+2*u5^2]
4912: [91] cyclic(6);
4913: [c5*c4*c3*c2*c1*c0-1,
4914: ((((c4+c5)*c3+c5*c4)*c2+c5*c4*c3)*c1+c5*c4*c3*c2)*c0+c5*c4*c3*c2*c1,
4915: (((c3+c5)*c2+c5*c4)*c1+c5*c4*c3)*c0+c4*c3*c2*c1+c5*c4*c3*c2,
4916: ((c2+c5)*c1+c5*c4)*c0+c3*c2*c1+c4*c3*c2+c5*c4*c3,
4917: (c1+c5)*c0+c2*c1+c3*c2+c4*c3+c5*c4,c0+c1+c2+c3+c4+c5]
4918: [92] hcyclic(6);
4919: [-c^6+c5*c4*c3*c2*c1*c0,
4920: ((((c4+c5)*c3+c5*c4)*c2+c5*c4*c3)*c1+c5*c4*c3*c2)*c0+c5*c4*c3*c2*c1,
4921: (((c3+c5)*c2+c5*c4)*c1+c5*c4*c3)*c0+c4*c3*c2*c1+c5*c4*c3*c2,
4922: ((c2+c5)*c1+c5*c4)*c0+c3*c2*c1+c4*c3*c2+c5*c4*c3,
4923: (c1+c5)*c0+c2*c1+c3*c2+c4*c3+c5*c4,c0+c1+c2+c3+c4+c5]
4924: @end example
4925:
4926: @table @t
1.25 ! noro 4927: \JP @item 参照
1.2 noro 4928: \EG @item References
1.1 noro 4929: @fref{dp_dtop}.
4930: @end table
4931:
1.25 ! noro 4932: \JP @node primadec primedec,,, グレブナ基底に関する函数
1.3 noro 4933: \EG @node primadec primedec,,, Functions for Groebner basis computation
4934: @subsection @code{primadec}, @code{primedec}
4935: @findex primadec
4936: @findex primedec
4937:
4938: @table @t
4939: @item primadec(@var{plist},@var{vlist})
4940: @item primedec(@var{plist},@var{vlist})
1.25 ! noro 4941: \JP :: イデアルの分解
1.3 noro 4942: \EG :: Computes decompositions of ideals.
4943: @end table
4944:
4945: @table @var
4946: @item return
4947: @itemx plist
1.25 ! noro 4948: \JP 多項式リスト
1.3 noro 4949: \EG list of polynomials
4950: @item vlist
1.25 ! noro 4951: \JP 変数リスト
1.3 noro 4952: \EG list of variables
4953: @end table
4954:
4955: @itemize @bullet
4956: \BJP
4957: @item
1.25 ! noro 4958: ここで解説されているイデアル分解については, 新しいパッケージ @samp{noro_pd.rr}
! 4959: においてより高速な実装が利用できる.
! 4960: @item
! 4961: @code{primadec()}, @code{primedec} は @samp{primdec} で定義されている.
1.3 noro 4962: @item
1.25 ! noro 4963: @code{primadec()}, @code{primedec()} はそれぞれ有理数体上でのイデアルの
! 4964: 準素分解, 根基の素イデアル分解を行う.
1.3 noro 4965: @item
1.25 ! noro 4966: 引数は多項式リストおよび変数リストである. 多項式は有理数係数のみが許される.
1.3 noro 4967: @item
1.25 ! noro 4968: @code{primadec} は @code{[準素成分, 付属素イデアル]} のリストを返す.
1.3 noro 4969: @item
1.25 ! noro 4970: @code{primadec} は 素因子のリストを返す.
1.3 noro 4971: @item
1.25 ! noro 4972: 結果において, 多項式リストとして表示されている各イデアルは全て
! 4973: グレブナ基底である. 対応する項順序は, それぞれ
! 4974: 変数 @code{PRIMAORD}, @code{PRIMEORD} に格納されている.
1.3 noro 4975: @item
1.25 ! noro 4976: @code{primadec} は @code{[Shimoyama,Yokoyama]} の準素分解アルゴリズム
! 4977: を実装している.
1.3 noro 4978: @item
1.25 ! noro 4979: もし素因子のみを求めたいなら, @code{primedec} を使う方がよい.
! 4980: これは, 入力イデアルが根基イデアルでない場合に, @code{primadec}
! 4981: の計算に余分なコストが必要となる場合があるからである.
1.3 noro 4982: \E
4983: \BEG
4984: @item
1.25 ! noro 4985: A new package @samp{noro_pd.rr} provides more efficient functions for ideal decomposition.
! 4986: @item
1.3 noro 4987: Function @code{primadec()} and @code{primedec} are defined in @samp{primdec}.
4988: @item
4989: @code{primadec()}, @code{primedec()} are the function for primary
4990: ideal decomposition and prime decomposition of the radical over the
4991: rationals respectively.
4992: @item
4993: The arguments are a list of polynomials and a list of variables.
4994: These functions accept ideals with rational function coefficients only.
4995: @item
4996: @code{primadec} returns the list of pair lists consisting a primary component
4997: and its associated prime.
4998: @item
4999: @code{primedec} returns the list of prime components.
5000: @item
5001: Each component is a Groebner basis and the corresponding term order
5002: is indicated by the global variables @code{PRIMAORD}, @code{PRIMEORD}
5003: respectively.
5004: @item
5005: @code{primadec} implements the primary decompostion algorithm
5006: in @code{[Shimoyama,Yokoyama]}.
5007: @item
5008: If one only wants to know the prime components of an ideal, then
5009: use @code{primedec} because @code{primadec} may need additional costs
5010: if an input ideal is not radical.
5011: \E
5012: @end itemize
5013:
5014: @example
5015: [84] load("primdec")$
5016: [102] primedec([p*q*x-q^2*y^2+q^2*y,-p^2*x^2+p^2*x+p*q*y,
5017: (q^3*y^4-2*q^3*y^3+q^3*y^2)*x-q^3*y^4+q^3*y^3,
5018: -q^3*y^4+2*q^3*y^3+(-q^3+p*q^2)*y^2],[p,q,x,y]);
5019: [[y,x],[y,p],[x,q],[q,p],[x-1,q],[y-1,p],[(y-1)*x-y,q*y^2-2*q*y-p+q]]
5020: [103] primadec([x,z*y,w*y^2,w^2*y-z^3,y^3],[x,y,z,w]);
5021: [[[x,z*y,y^2,w^2*y-z^3],[z,y,x]],[[w,x,z*y,z^3,y^3],[w,z,y,x]]]
5022: @end example
5023:
5024: @table @t
1.25 ! noro 5025: \JP @item 参照
1.3 noro 5026: \EG @item References
5027: @fref{fctr sqfr},
1.25 ! noro 5028: \JP @fref{項順序の設定}.
1.3 noro 5029: \EG @fref{Setting term orderings}.
5030: @end table
1.5 noro 5031:
1.25 ! noro 5032: \JP @node primedec_mod,,, グレブナ基底に関する函数
1.5 noro 5033: \EG @node primedec_mod,,, Functions for Groebner basis computation
5034: @subsection @code{primedec_mod}
5035: @findex primedec_mod
5036:
5037: @table @t
5038: @item primedec_mod(@var{plist},@var{vlist},@var{ord},@var{mod},@var{strategy})
1.25 ! noro 5039: \JP :: イデアルの分解
1.5 noro 5040: \EG :: Computes decompositions of ideals over small finite fields.
5041: @end table
5042:
5043: @table @var
5044: @item return
5045: @itemx plist
1.25 ! noro 5046: \JP 多項式リスト
1.5 noro 5047: \EG list of polynomials
5048: @item vlist
1.25 ! noro 5049: \JP 変数リスト
1.5 noro 5050: \EG list of variables
5051: @item ord
1.25 ! noro 5052: \JP 数, リストまたは行列
1.5 noro 5053: \EG number, list or matrix
5054: @item mod
1.25 ! noro 5055: \JP 正整数
1.5 noro 5056: \EG positive integer
5057: @item strategy
1.25 ! noro 5058: \JP 整数
1.5 noro 5059: \EG integer
5060: @end table
5061:
5062: @itemize @bullet
5063: \BJP
5064: @item
1.25 ! noro 5065: @code{primedec_mod()} は @samp{primdec_mod}
! 5066: で定義されている. @code{[Yokoyama]} の素イデアル分解アルゴリズム
! 5067: を実装している.
! 5068: @item
! 5069: @code{primedec_mod()} は有限体上でのイデアルの
! 5070: 根基の素イデアル分解を行い, 素イデアルのリストを返す.
! 5071: @item
! 5072: @code{primedec_mod()} は, GF(@var{mod}) 上での分解を与える.
! 5073: 結果の各成分の生成元は, 整数係数多項式である.
! 5074: @item
! 5075: 結果において, 多項式リストとして表示されている各イデアルは全て
! 5076: [@var{vlist},@var{ord}] で指定される項順序に関するグレブナ基底である.
! 5077: @item
! 5078: @var{strategy} が 0 でないとき, incremental に component の共通
! 5079: 部分を計算することによる early termination を行う. 一般に,
! 5080: イデアルの次元が高い場合に有効だが, 0 次元の場合など, 次元が小さい
! 5081: 場合には overhead が大きい場合がある.
1.7 noro 5082: @item
1.25 ! noro 5083: 計算途中で内部情報を見たい場合には、
! 5084: 前もって @code{dp_gr_print(2)} を実行しておけばよい.
1.5 noro 5085: \E
5086: \BEG
5087: @item
5088: Function @code{primedec_mod()}
5089: is defined in @samp{primdec_mod} and implements the prime decomposition
5090: algorithm in @code{[Yokoyama]}.
5091: @item
5092: @code{primedec_mod()}
5093: is the function for prime ideal decomposition
5094: of the radical of a polynomial ideal over small finite field,
5095: and they return a list of prime ideals, which are associated primes
5096: of the input ideal.
5097: @item
5098: @code{primedec_mod()} gives the decomposition over GF(@var{mod}).
5099: The generators of each resulting component consists of integral polynomials.
5100: @item
5101: Each resulting component is a Groebner basis with respect to
5102: a term order specified by [@var{vlist},@var{ord}].
5103: @item
5104: If @var{strategy} is non zero, then the early termination strategy
5105: is tried by computing the intersection of obtained components
5106: incrementally. In general, this strategy is useful when the krull
5107: dimension of the ideal is high, but it may add some overhead
5108: if the dimension is small.
1.7 noro 5109: @item
5110: If you want to see internal information during the computation,
5111: execute @code{dp_gr_print(2)} in advance.
1.5 noro 5112: \E
5113: @end itemize
5114:
5115: @example
5116: [0] load("primdec_mod")$
5117: [246] PP444=[x^8+x^2+t,y^8+y^2+t,z^8+z^2+t]$
5118: [247] primedec_mod(PP444,[x,y,z,t],0,2,1);
5119: [[y+z,x+z,z^8+z^2+t],[x+y,y^2+y+z^2+z+1,z^8+z^2+t],
5120: [y+z+1,x+z+1,z^8+z^2+t],[x+z,y^2+y+z^2+z+1,z^8+z^2+t],
5121: [y+z,x^2+x+z^2+z+1,z^8+z^2+t],[y+z+1,x^2+x+z^2+z+1,z^8+z^2+t],
5122: [x+z+1,y^2+y+z^2+z+1,z^8+z^2+t],[y+z+1,x+z,z^8+z^2+t],
5123: [x+y+1,y^2+y+z^2+z+1,z^8+z^2+t],[y+z,x+z+1,z^8+z^2+t]]
5124: [248]
5125: @end example
5126:
5127: @table @t
1.25 ! noro 5128: \JP @item 参照
1.5 noro 5129: \EG @item References
5130: @fref{modfctr},
1.6 noro 5131: @fref{dp_gr_main dp_gr_mod_main dp_gr_f_main dp_weyl_gr_main dp_weyl_gr_mod_main dp_weyl_gr_f_main},
1.25 ! noro 5132: \JP @fref{項順序の設定}.
1.7 noro 5133: \EG @fref{Setting term orderings},
5134: @fref{dp_gr_flags dp_gr_print}.
1.5 noro 5135: @end table
5136:
1.25 ! noro 5137: \JP @node bfunction bfct generic_bfct ann ann0,,, グレブナ基底に関する函数
1.10 noro 5138: \EG @node bfunction bfct generic_bfct ann ann0,,, Functions for Groebner basis computation
5139: @subsection @code{bfunction}, @code{bfct}, @code{generic_bfct}, @code{ann}, @code{ann0}
1.6 noro 5140: @findex bfunction
1.9 noro 5141: @findex bfct
1.6 noro 5142: @findex generic_bfct
1.10 noro 5143: @findex ann
5144: @findex ann0
1.5 noro 5145:
1.6 noro 5146: @table @t
5147: @item bfunction(@var{f})
1.10 noro 5148: @itemx bfct(@var{f})
5149: @itemx generic_bfct(@var{plist},@var{vlist},@var{dvlist},@var{weight})
1.25 ! noro 5150: \JP :: @var{b} 関数の計算
1.10 noro 5151: \EG :: Computes the global @var{b} function of a polynomial or an ideal
5152: @item ann(@var{f})
5153: @itemx ann0(@var{f})
1.25 ! noro 5154: \JP :: 多項式のベキの annihilator の計算
1.10 noro 5155: \EG :: Computes the annihilator of a power of polynomial
1.6 noro 5156: @end table
1.10 noro 5157:
1.6 noro 5158: @table @var
5159: @item return
1.25 ! noro 5160: \JP 多項式またはリスト
1.10 noro 5161: \EG polynomial or list
5162: @item f
1.25 ! noro 5163: \JP 多項式
1.6 noro 5164: \EG polynomial
5165: @item plist
1.25 ! noro 5166: \JP 多項式リスト
1.6 noro 5167: \EG list of polynomials
5168: @item vlist dvlist
1.25 ! noro 5169: \JP 変数リスト
1.6 noro 5170: \EG list of variables
5171: @end table
1.5 noro 5172:
1.6 noro 5173: @itemize @bullet
5174: \BJP
1.25 ! noro 5175: @item @samp{bfct} で定義されている.
! 5176: @item @code{bfunction(@var{f})}, @code{bfct(@var{f})} は多項式 @var{f} の global @var{b} 関数 @code{b(s)} を
! 5177: 計算する. @code{b(s)} は, Weyl 代数 @code{D} 上の一変数多項式環 @code{D[s]}
! 5178: の元 @code{P(x,s)} が存在して, @code{P(x,s)f^(s+1)=b(s)f^s} を満たすような
! 5179: 多項式 @code{b(s)} の中で, 次数が最も低いものである.
1.6 noro 5180: @item @code{generic_bfct(@var{f},@var{vlist},@var{dvlist},@var{weight})}
1.25 ! noro 5181: は, @var{plist} で生成される @code{D} の左イデアル @code{I} の,
! 5182: ウェイト @var{weight} に関する global @var{b} 関数を計算する.
! 5183: @var{vlist} は @code{x}-変数, @var{vlist} は対応する @code{D}-変数
! 5184: を順に並べる.
! 5185: @item @code{bfunction} と @code{bfct} では用いているアルゴリズムが
! 5186: 異なる. どちらが高速かは入力による.
! 5187: @item @code{ann(@var{f})} は, @code{@var{f}^s} の annihilator ideal
! 5188: の生成系を返す. @code{ann(@var{f})} は, @code{[@var{a},@var{list}]}
! 5189: なるリストを返す. ここで, @var{a} は @var{f} の @var{b} 関数の最小整数根,
! 5190: @var{list} は @code{ann(@var{f})} の結果の @code{s}$ に, @var{a} を
! 5191: 代入したものである.
! 5192: @item 詳細については, [Saito,Sturmfels,Takayama] を見よ.
1.6 noro 5193: \E
5194: \BEG
5195: @item These functions are defined in @samp{bfct}.
1.10 noro 5196: @item @code{bfunction(@var{f})} and @code{bfct(@var{f})} compute the global @var{b}-function @code{b(s)} of
1.6 noro 5197: a polynomial @var{f}.
5198: @code{b(s)} is a polynomial of the minimal degree
5199: such that there exists @code{P(x,s)} in D[s], which is a polynomial
5200: ring over Weyl algebra @code{D}, and @code{P(x,s)f^(s+1)=b(s)f^s} holds.
5201: @item @code{generic_bfct(@var{f},@var{vlist},@var{dvlist},@var{weight})}
1.10 noro 5202: computes the global @var{b}-function of a left ideal @code{I} in @code{D}
1.6 noro 5203: generated by @var{plist}, with respect to @var{weight}.
5204: @var{vlist} is the list of @code{x}-variables,
5205: @var{vlist} is the list of corresponding @code{D}-variables.
1.9 noro 5206: @item @code{bfunction(@var{f})} and @code{bfct(@var{f})} implement
5207: different algorithms and the efficiency depends on inputs.
1.10 noro 5208: @item @code{ann(@var{f})} returns the generator set of the annihilator
5209: ideal of @code{@var{f}^s}.
5210: @code{ann(@var{f})} returns a list @code{[@var{a},@var{list}]},
5211: where @var{a} is the minimal integral root of the global @var{b}-function
5212: of @var{f}, and @var{list} is a list of polynomials obtained by
5213: substituting @code{s} in @code{ann(@var{f})} with @var{a}.
1.7 noro 5214: @item See [Saito,Sturmfels,Takayama] for the details.
1.6 noro 5215: \E
5216: @end itemize
5217:
5218: @example
5219: [0] load("bfct")$
5220: [216] bfunction(x^3+y^3+z^3+x^2*y^2*z^2+x*y*z);
5221: -9*s^5-63*s^4-173*s^3-233*s^2-154*s-40
5222: [217] fctr(@@);
5223: [[-1,1],[s+2,1],[3*s+4,1],[3*s+5,1],[s+1,2]]
5224: [218] F = [4*x^3*dt+y*z*dt+dx,x*z*dt+4*y^3*dt+dy,
5225: x*y*dt+5*z^4*dt+dz,-x^4-z*y*x-y^4-z^5+t]$
5226: [219] generic_bfct(F,[t,z,y,x],[dt,dz,dy,dx],[1,0,0,0]);
5227: 20000*s^10-70000*s^9+101750*s^8-79375*s^7+35768*s^6-9277*s^5
5228: +1278*s^4-72*s^3
1.10 noro 5229: [220] P=x^3-y^2$
5230: [221] ann(P);
5231: [2*dy*x+3*dx*y^2,-3*dx*x-2*dy*y+6*s]
5232: [222] ann0(P);
5233: [-1,[2*dy*x+3*dx*y^2,-3*dx*x-2*dy*y-6]]
1.6 noro 5234: @end example
5235:
5236: @table @t
1.25 ! noro 5237: \JP @item 参照
1.6 noro 5238: \EG @item References
1.25 ! noro 5239: \JP @fref{Weyl 代数}.
1.6 noro 5240: \EG @fref{Weyl algebra}.
5241: @end table
1.5 noro 5242:
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to groebner.texi CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [local] / OpenXM / src / asir-doc / parts