グレブナ基底の計算
*********

Groebner basis computation
**************************

分散表現多項式
=======

Distributed polynomial
======================

分散表現多項式とは, 多項式の内部形式の一つである. 通常の多項式 (type が 2) は, 再帰表現と呼ばれる形式で表現されている. すなわち, 特定の変数を主変数とする 1 変数多項式で, その他の変数は, その 1 変数多項式の係数に, 主変数を含まない多項式として現れる. この係数が, また, ある変数を主変数とする多項式となっていることから再帰表現と呼ばれる.

A distributed polynomial is a polynomial with a special internal representation different from the ordinary one.

An ordinary polynomial (having type 2) is internally represented in a format, called recursive representation. In fact, it is represented as an uni-variate polynomial with respect to a fixed variable, called main variable of that polynomial, where the other variables appear in the coefficients which may again polynomials in such variables other than the previous main variable. A polynomial in the coefficients is again represented as an uni-variate polynomial in a certain fixed variable, the main variable.  Thus, by this recursive structure of polynomial representation, it is called the `recursive representation.'

     (x+y+z)^2 = 1 x^2 + (2 y + (2 z)) x + ((2 z) y + (1 z^2 ))

これに対し, 多項式を, 変数の冪積と係数の積の和として表現したものを分散表現と呼ぶ.

On the other hand, we call a representation the distributed representation of a polynomial, if a polynomial is represented, according to its original meaning, as a sum of monomials, where a monomial is the product of power product of variables and a coefficient.  We call a polynomial, represented in such an internal format, a distributed polynomial. (This naming may sounds something strange.)

     (x+y+z)^2 = 1 x^2 + 2 xy + 2 xz + 1 y^2 + 2 yz +1 z^2$

グレブナ基底計算においては, 単項式に注目して操作を行うため多項式が分散表現されている方がより効率のよい演算が可能になる. このため, 分散表現多項式が, 識別子 9 の型として Asir のトップレベルから利用可能となっている. ここで, 後の説明のために, いくつかの言葉を定義しておく.

For computation of Groebner basis, efficient operation is expected if polynomials are represented in a distributed representation, because major operations for Groebner basis are performed with respect to monomials. From this view point, we provide the object type distributed polynomial with its object identification number 9, and objects having such a type are available by Asir language.

Here, we provide several definitions for the later description.

項 (term)
     変数の冪積. すなわち, 係数 1 の単項式のこと. Asir においては,

term
     The power product of variables, i.e., a monomial with coefficient 1. In an Asir session, it is displayed in the form like

          <<0,1,2,3,4>>

     という形で表示され, また, この形で入力可能である. この例は, 5 変数の項を示す. 各変数を a, b, c, d, e とするとこの項は b*c^2*d^3*e^4 を表す.

     and also can be input in such a form. This example shows a term in 5 variables.  If we assume the 5 variables as a, b, c, d, and e, the term represents b*c^2*d^3*e^4 in the ordinary expression.

項順序 (term order)
     分散表現多項式における項は, 次の性質を満たす全順序により整列される.

term order
     Terms are ordered according to a total order with the following properties.

      1. 任意の項 t に対し t > 1

          For all t t > 1.

      2. t, s, u を項とする時, t > s ならば tu > su

          For all t, s, u t > s implies tu > su.

     この性質を満たす全順序を項順序と呼ぶ. この順序は変数順序 (変数のリスト) と項順序型 (数, リストまたは行列) により指定される.

     Such a total order is called a term ordering. A term ordering is specified by a variable ordering (a list of variables) and a type of term ordering (an integer, a list or a matrix).

単項式 (monomial)
     項と係数の積.

monomial
     The product of a term and a coefficient. In an Asir session, it is displayed in the form like

          2*<<0,1,2,3,4>>

     という形で表示され, また, この形で入力可能である.

     and also can be input in such a form.

頭項 (head term)
頭単項式 (head monomial)
頭係数 (head coefficient)
     分散表現多項式における各単項式は, 項順序により整列される. この時順序最大の単項式を頭単項式, それに現れる項, 係数をそれぞれ頭項, 頭係数と呼ぶ.

head term
head monomial
head coefficient

     Monomials in a distributed polynomial is sorted by a total order. In such representation, we call the monomial that is maximum with respect to the order the head monomial, and its term and coefficient the head term and the head coefficient respectively.

ChangeLog

  * 分散表現多項式は任意のオブジェクトを係数にもてるようになった. また加群のk成分の要素を次の形式 <<d0,d1,...:k>> で表現するようになった (2017-08-31).

  * Distributed polynomials accept objects as coefficients. The k-th element of a free module is expressed as <<d0,d1,...:k>> (2017-08-31).

  * 1.15 algnum.c, 1.53 ctrl.c, 1.66 dp-supp.c, 1.105 dp.c, 1.73 gr.c, 1.4 reduct.c, 1.16 _distm.c, 1.17 dalg.c, 1.52 dist.c, 1.20 distm.c, 1.8  gmpq.c, 1.238 engine/nd.c, 1.102  ca.h, 1.411  version.h, 1.28 cpexpr.c, 1.42 pexpr.c, 1.20 pexpr_body.c, 1.40 spexpr.c, 1.27 arith.c, 1.77 eval.c, 1.56 parse.h, 1.37 parse.y, 1.8 stdio.c, 1.31 plotf.c

ファイルの読み込み
=========

Reading files
=============

グレブナ基底を計算するための基本的な函数は dp_gr_main() および dp_gr_mod_main(), dp_gr_f_main() なる 3 つの組み込み函数であるが, 通常は, パラメタ設定などを行ったのちこれらを呼び出すユーザ函数を用いるのが便利である. これらのユーザ函数は, ファイル gr を load() により読み込むことにより使用可能となる. gr は, Asir の標準ライブラリディレクトリに置かれている.

Facilities for computing Groebner bases are dp_gr_main(), dp_gr_mod_main()and dp_gr_f_main(). To call these functions, it is necessary to set several parameters correctly and it is convenient to use a set of interface functions provided in the library file gr. The facilities will be ready to use after you load the package by load().  The package gr is placed in the standard library directory of Asir.

     [0] load("gr")$

基本的な函数
======

Fundamental functions
=====================

gr では数多くの函数が定義されているが, 直接グレブナ基底を計算するためのトップレベルは次の 3 つである. 以下で, PLIST は多項式のリスト, VLIST は変数 (不定元) のリスト, ORDER は変数順序型, P は 2^27 未満の素数である.

There are many functions and options defined in the package gr. Usually not so many of them are used.  Top level functions for Groebner basis computation are the following three functions.

In the following description, PLIST, VLIST, ORDER and P stand for  a list of polynomials,  a list of variables (indeterminates), a type of term ordering and a prime less than 2^27 respectively.

gr(PLIST,VLIST,ORDER)

     Gebauer-Moeller による useless pair elimination criteria, sugar strategy および Traverso による trace-lifting を用いた Buchberger アルゴリズムによる有理数係数グレブナ基底計算函数. 一般にはこの函数を用いる.

     Function that computes Groebner bases over the rationals. The algorithm is Buchberger algorithm with useless pair elimination criteria by Gebauer-Moeller, sugar strategy and trace-lifting by Traverso. For ordinary computation, this function is used.

hgr(PLIST,VLIST,ORDER)

     入力多項式を斉次化した後 gr() のグレブナ基底候補生成部により候補生成し, 非斉次化, interreduce したものを gr() のグレブナ基底チェック部でチェックする. 0 次元システム (解の個数が有限個の方程式系) の場合, sugar strategy が係数膨張を引き起こす場合がある. このような場合, strategy を斉次化による strategy に置き換えることにより係数膨張を抑制することができる場合が多い.

     After homogenizing the input polynomials a candidate of the \gr basis is computed by trace-lifting. Then the candidate is dehomogenized and checked whether it is indeed a Groebner basis of the input.  Sugar strategy often causes intermediate coefficient swells.  It is empirically known that the combination of homogenization and supresses the swells for such cases.

gr_mod(PLIST,VLIST,ORDER,P)

     Gebauer-Moeller による useless pair elimination criteria, sugar strategy および Buchberger アルゴリズムによる GF(p) 係数グレブナ基底計算函数.

     Function that computes Groebner bases over GF(P). The same algorithm as gr() is used.

計算および表示の制御
==========

Controlling Groebner basis computations
=======================================

グレブナ基底の計算において, さまざまなパラメタ設定を行うことにより計算, 表示を制御することができる. これらは, 組み込み函数 dp_gr_flags() により設定参照することができる. 無引数で dp_gr_flags() を実行すると, 現在設定されているパラメタが, 名前と値のリストで返される.

One can cotrol a Groebner basis computation by setting various parameters. These parameters can be set and examined by a built-in function dp_gr_flags(). Without argument it returns the current settings.

     [100] dp_gr_flags();
     [Demand,0,NoSugar,0,NoCriB,0,NoGC,0,NoMC,0,NoRA,0,NoGCD,0,Top,0,
     ShowMag,1,Print,1,Stat,0,Reverse,0,InterReduce,0,Multiple,0]
     [101]

以下で, 各パラメタの意味を説明する. on の場合とは, パラメタが 0 でない場合をいう. これらのパラメタの初期値は全て 0 (off) である.

The return value is a list which contains the names of parameters and their values. The meaning of the parameters are as follows. `on' means that the parameter is not zero.

NoSugar

     on の場合, sugar strategy の代わりに Buchbergerの normal strategy が用いられる.

     If `on', Buchberger's normal strategy is used instead of sugar strategy.

NoCriB
     on の場合, 不必要対検出規準のうち, 規準 B を適用しない.

     If `on', criterion B among the Gebauer-Moeller's criteria is not applied.

NoGC
     on の場合, 結果がグレブナ基底になっているかどうかのチェックを行わない.

     If `on', the check that a Groebner basis candidate is indeed a Groebner basis, is not executed.

NoMC

     on の場合, 結果が入力イデアルと同等のイデアルであるかどうかのチェックを行わない.

     If `on', the check that the resulting polynomials generates the same ideal as the ideal generated by the input, is not executed.

NoRA

     on の場合, 結果を reduced グレブナ基底にするための interreduce を行わない.

     If `on', the interreduction, which makes the Groebner basis reduced, is not executed.

NoGCD

     on の場合, 有理式係数のグレブナ基底計算において, 生成された多項式の, 係数の content をとらない.

     If `on', content removals are not executed during a Groebner basis computation over a rational function field.

Top
     on の場合, normal form 計算において頭項消去のみを行う.

     If `on', Only the head term of the polynomial being reduced is reduced.

Reverse

     on の場合, normal form 計算の際の reducer を, 新しく生成されたものを優先して選ぶ.

     If `on', the selection strategy of reducer in a normal form computation is such that a newer reducer is used first.

Print
     on の場合, グレブナ基底計算の途中におけるさまざまな情報を表示する.

     If `on', various informations during a Groebner basis computation is displayed.

PrintShort
     on で、Print が off の場合, グレブナ基底計算の途中の情報を短縮形で表示する.

     If `on' and Print is `off', short information during a Groebner basis computation is displayed.

Stat

     on で Print が off ならば, Print が on のとき表示されるデータの内, 集計データのみが表示される.

     If `on', a summary of informations is shown after a Groebner basis computation. Note that the summary is always shown if Print is `on'.

ShowMag

     on で Print が on ならば, 生成が生成される毎に, その多項式の係数のビット長の和を表示し, 最後に, それらの和の最大値を表示する.

     If `on' and Print is `on', the sum of bit length of coefficients of a generated basis element, which we call MAGNITUDE, is shown after every normal computation.  After comleting the computation the maximal value among the sums is shown.

Content
Multiple

     0 でない有理数の時, 有理数上の正規形計算において, 係数のビット長の和が Content 倍になるごとに係数全体の GCD が計算され, その GCD で割った多項式を簡約する. Content が 1 ならば, 簡約するごとに GCD 計算が行われ一般には効率が悪くなるが, Content を 2 程度とすると, 巨大な整数が係数に現れる場合, 効率が良くなる場合がある. backward compatibility のため、Multiple で整数値を指定できる.

     If a non-zero rational number, in a normal form computation over the rationals, the integer content of the polynomial being reduced is removed when its magnitude becomes Content times larger than a registered value, which is set to the magnitude of the input polynomial. After each content removal the registered value is set to the magnitude of the resulting polynomial. Content is equal to 1, the simiplification is done after every normal form computation. It is empirically known that it is often efficient to set Content to 2 for the case where large integers appear during the computation. An integer value can be set by the keyword Multiple for backward compatibility.

Demand

     正当なディレクトリ名 (文字列) を値に持つとき, 生成された多項式はメモリ中におかれず, そのディレクトリ中にバイナリデータとして置かれ, その多項式を用いる normal form 計算の際, 自動的にメモリ中にロードされる. 各多項式は, 内部でのインデックスをファイル名に持つファイルに格納される. ここで指定されたディレクトリに書かれたファイルは自動的には消去されないため, ユーザが責任を持って消去する必要がある.

     If the value (a character string) is a valid directory name, then generated basis elements are put in the directory and are loaded on demand during normal form computations.  Each elements is saved in the binary form and its name coincides with the index internally used in the computation. These binary files are not removed automatically and one should remove them by hand.

Print が 0 でない場合次のようなデータが表示される.

If Print is `on', the following informations are shown.

     [93] gr(cyclic(4),[c0,c1,c2,c3],0)$
     mod= 99999989, eval = []
     (0)(0)<<0,2,0,0>>(2,3),nb=2,nab=5,rp=2,sugar=2,mag=4
     (0)(0)<<0,1,2,0>>(1,2),nb=3,nab=6,rp=2,sugar=3,mag=4
     (0)(0)<<0,1,1,2>>(0,1),nb=4,nab=7,rp=3,sugar=4,mag=6
     .
     (0)(0)<<0,0,3,2>>(5,6),nb=5,nab=8,rp=2,sugar=5,mag=4
     (0)(0)<<0,1,0,4>>(4,6),nb=6,nab=9,rp=3,sugar=5,mag=4
     (0)(0)<<0,0,2,4>>(6,8),nb=7,nab=10,rp=4,sugar=6,mag=6
     ....gb done
     reduceall
     .......
     membercheck
     (0,0)(0,0)(0,0)(0,0)
     gbcheck total 8 pairs
     ........
     UP=(0,0)SP=(0,0)SPM=(0,0)NF=(0,0)NFM=(0.010002,0)ZNFM=(0.010002,0)
     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
     D=12 ZR=5 NZR=6 Max_mag=6
     [94]

最初に表示される mod, eval は, trace-lifting で用いられる法である. mod は素数, eval は有理式係数の場合に用いられる数のリストである.

In this example mod and eval indicate moduli used in trace-lifting. mod is a prime and eval is a list of integers used for evaluation when the ground field is a field of rational functions.

計算途中で多項式が生成される毎に次の形のデータが表示される.

The following information is shown after every normal form computation.

     (TNF)(TCONT)HT(INDEX),nb=NB,nab=NAB,rp=RP,sugar=S,mag=M

それらの意味は次の通り.

Meaning of each component is as follows.

TNF

     normal form 計算時間 (秒)

TCONT

     content 計算時間 (秒)

HT

     生成された多項式の頭項

INDEX

     S-多項式を構成する多項式のインデックスのペア

NB

     現在の, 冗長性を除いた基底の数

NAB

     現在までに生成された基底の数

RP

     残りのペアの数

S

     生成された多項式の sugar の値

M

     生成された多項式の係数のビット長の和 (ShowMag が on の時に表示される. )

TNF

     CPU time for normal form computation (second)

TCONT

     CPU time for content removal(second)

HT

     Head term of the generated basis element

INDEX

     Pair of indices which corresponds to the reduced S-polynomial

NB

     Number of basis elements after removing redundancy

NAB

     Number of all the basis elements

RP

     Number of remaining pairs

S

     Sugar of the generated basis element

M

     Magnitude of the genrated basis element (shown if ShowMag is `on'.)

最後に, 集計データが表示される. 意味は次の通り. (時間の表示において, 数字が 2 つあるものは, 計算時間と GC 時間のペアである.)

The summary of the informations shown after a Groebner basis computation is as follows.  If a component shows timings and it contains two numbers, they are a pair of time for computation and time for garbage colection.

UP

     ペアのリストの操作にかかった時間

SP

     有理数上の S-多項式計算時間

SPM

     有限体上の S-多項式計算時間

NF

     有理数上の normal form 計算時間

NFM

     有限体上の normal form 計算時間

ZNFM

     NFM の内, 0 への reduction にかかった時間

PZ

     content 計算時間

NP

     有理数係数多項式の係数に対する剰余演算の計算時間

MP

     S-多項式を生成するペアの選択にかかった時間

RA

     interreduce 計算時間

MC

     trace-lifting における, 入力多項式のメンバシップ計算時間

GC

     結果のグレブナ基底候補のグレブナ基底チェック時間

T

     生成されたペアの数

B, M, F, D

     各 criterion により除かれたペアの数

ZR

     0 に reduce されたペアの数

NZR

     0 でない多項式に reduce されたペアの数

Max_mag

     生成された多項式の, 係数のビット長の和の最大値

UP

     Time to manipulate the list of critical pairs

SP

     Time to compute S-polynomials over the rationals

SPM

     Time to compute S-polynomials over a finite field

NF

     Time to compute normal forms over the rationals

NFM

     Time to compute normal forms over a finite field

ZNFM

     Time for zero reductions in NFM

PZ

     Time to remove integer contets

NP

     Time to compute remainders for coefficients of polynomials with coeffieints in the rationals

MP

     Time to select pairs from which S-polynomials are computed

RA

     Time to interreduce the Groebner basis candidate

MC

     Time to check that each input polynomial is a member of the ideal generated by the Groebner basis candidate.

GC

     Time to check that the Groebner basis candidate is a Groebner basis

T

     Number of critical pairs generated

B, M, F, D

     Number of critical pairs removed by using each criterion

ZR

     Number of S-polynomials reduced to 0

NZR

     Number of S-polynomials reduced to non-zero results

Max_mag

     Maximal magnitude among all the generated polynomials

項順序の設定
======

Setting term orderings
======================

項は内部では, 各変数に関する指数を成分とする整数ベクトルとして表現される. 多項式を分散表現多項式に変換する際, 各変数がどの成分に対応するかを指定するのが, 変数リストである. さらに, それら整数ベクトルの全順序を指定するのが項順序の型である. 項順序型は, 数, 数のリストあるいは行列で表現される.

A term is internally represented as an integer vector whose components are exponents with respect to variables. A variable list specifies the correspondences between variables and components. A type of term ordering specifies a total order for integer vectors. A type of term ordering is represented by an integer, a list of integer or matrices.

基本的な項順序型として次の 3 つがある.

There are following three fundamental types.

0 (DegRevLex; 全次数逆辞書式順序)

0 (DegRevLex; total degree reverse lexicographic ordering)

     一般に, この順序によるグレブナ基底計算が最も高速である. ただし, 方程式を解くという目的に用いることは, 一般にはできない. この順序によるグレブナ基底は, 解の個数の計算, イデアルのメンバシップや, 他の変数順序への基底変換のためのソースとして用いられる.

     In general, computation by this ordering shows the fastest speed in most Groebner basis computations. However, for the purpose to solve polynomial equations, this type of ordering is, in general, not so suitable. The Groebner bases obtained by this ordering is used for computing the number of solutions, solving ideal membership problem and seeds for conversion to other Groebner bases under different ordering.

1 (DegLex; 全次数辞書式順序)

1 (DegLex; total degree lexicographic ordering)

     この順序も, 辞書式順序に比べて高速にグレブナ基底を求めることができるが, DegRevLex と同様直接その結果を用いることは困難である. しかし, 辞書式順序のグレブナ基底を求める際に, 斉次化後にこの順序でグレブナ基底を求めている.

     By this type term ordering, Groebner bases are obtained fairly faster than Lex (lexicographic) ordering, too. Alike the DegRevLex ordering, the result, in general, cannot directly be used for solving polynomial equations. It is used, however, in such a way that a Groebner basis is computed in this ordering after homogenization to obtain the final lexicographic Groebner basis.

2 (Lex; 辞書式順序)

2 (Lex; lexicographic ordering)

     この順序によるグレブナ基底は, 方程式を解く場合に最適の形の基底を与えるが計算時間がかかり過ぎるのが難点である. 特に, 解が有限個の場合, 結果の係数が極めて長大な多倍長数になる場合が多い. この場合, gr(), hgr() による計算が極めて有効になる場合が多い.

     Groebner bases computed by this ordering give the most convenient Groebner bases for solving the polynomial equations. The only and serious shortcoming is the enormously long computation time. It is often observed that the number coefficients of the result becomes very very long integers, especially if the ideal is 0-dimensional. For such a case, it is empirically true for many cases that i.e., computation by gr() and/or hgr() may be quite effective.

これらを組み合わせてリストで指定することにより, 様々な消去順序が指定できる. これは,

By combining these fundamental orderingl into a list, one can make various term ordering called elimination orderings.

[[O1,L1],[O2,L2],...]

で指定される. Oi は 0, 1, 2 のいずれかで, Li は変数の個数を表す. この指定は, 変数を先頭から L1, L2 , ...個ずつの組に分け, それぞれの変数に関し, 順に O1, O2, ...の項順序型で大小が決定するまで比較することを意味する. この型の順序は一般に消去順序と呼ばれる.

In this example Oi indicates 0, 1 or 2 and Li indicates the number of variables subject to the correspoinding orderings. This specification means the following.

The variable list is separated into sub lists from left to right where the i-th list contains Li members and it corresponds to the ordering of type Oi. The result of a comparison is equal to that for the leftmost different sub components. This type of ordering is called an elimination ordering.

さらに, 行列により項順序を指定することができる. 一般に, n 行 m 列の実数行列 M が次の性質を持つとする.

Furthermore one can specify a term ordering by a matix. Suppose that a real n, m matrix M has the following properties.

 1. 長さ m の整数ベクトル v に対し Mv=0 と v=0 は同値.

     For all integer verctors v of length m Mv=0 is equivalent to v=0.

 2. 非負成分を持つ長さ m の 0 でない整数ベクトル v に対し, Mv の 0 でない最初の成分は非負.

     For all non-negative integer vectors v the first non-zero component of Mv is non-negative.

この時, 2 つのベクトル t, s に対し, t>s を, M(t-s) の 0 でない最初の成分が非負, で定義することにより項順序が定義できる.

Then we can define a term ordering such that, for two vectors t, s, t>s means that the first non-zero component of M(t-s) is non-negative.

項順序型は, gr() などの引数として指定される他, 組み込み函数 dp_ord() で指定され, さまざまな函数の実行の際に参照される.

Types of term orderings are used as arguments of functions such as gr(). It is also set internally by dp_ord() and is used during executions of various functions.

これらの順序の具体的な定義およびグレブナ基底に関する更に詳しい解説は [Becker,Weispfenning] などを参照のこと.

For concrete definitions of term ordering and more information about Groebner basis, refer to, for example, the book [Becker,Weispfenning].

項順序型の設定の他に, 変数の順序自体も計算時間に大きな影響を与える.

Note that the variable ordering have strong effects on the computation time as well as the choice of types of term orderings.

     [90] B=[x^10-t,x^8-z,x^31-x^6-x-y]$
     [91] gr(B,[x,y,z,t],2);
     [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
     -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
     +(-12*t^16+72*t^13-28*t^11-180*t^10+112*t^8+240*t^7+28*t^6-127*t^5
     -167*t^4-55*t^3+30*t^2+58*t-15)*z^4,
     (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
     +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
     +(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
     +27*t^3-16*t^2-30*t+7)*z^4,
     (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
     -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
     +10*t^4-36*t^3-11*t^2-5*t+9)*z^2,
     -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
     -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
     +20*t^19+28*t^18-120*t^16-56*t^15+14*t^14+300*t^13+70*t^12-56*t^11
     -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
     -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
     -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,
     -z*y^3+(t^7-2*t^4+3*t^2+t)*y+(-2*t^6+4*t^3+2*t-2)*z^2,
     2*t^2*y^3+z^2*y^2+(-2*t^5+4*t^2-6)*z^4*y
     +(4*t^8-t^7-8*t^5+2*t^4-4*t^3+5*t^2-t)*z,
     z^3*y^2+2*t^3*y+(-t^7+2*t^4+t^2-t)*z^2,
     -t*z*y^2-2*z^3*y+t^8-2*t^5-t^3+t^2,
     -t^3*y^2-2*t^2*z^2*y+(t^6-2*t^3-t+1)*z^4,z^5-t^4]
     [93] gr(B,[t,z,y,x],2);
     [x^10-t,x^8-z,x^31-x^6-x-y]

変数順序 [x,y,z,t] におけるグレブナ基底は, 基底の数も多く, それぞれの式も大きい. しかし, 順序 [t,z,y,x] にもとでは, B がすでにグレブナ基底となっている. 大雑把にいえば, 辞書式順序でグレブナ基底を求めることは, 左側の (順序の高い) 変数を, 右側の (順序の低い) 変数で書き表すことであり, この例の場合は, t,  z, y が既に x で表されていることからこのような極端な結果となったわけである. 実際に現れる計算においては, このように選ぶべき変数順序が明らかであることは少なく, 試行錯誤が必要な場合もある.

As you see in the above example, the Groebner base under variable ordering [x,y,z,t] has a lot of bases and each base itself is large.  Under variable ordering [t,z,y,x], however, B itself is already the Groebner basis. Roughly speaking, to obtain a Groebner base under the lexicographic ordering is to express the variables on the left (having higher order) in terms of variables on the right (having lower order). In the example, variables t,  z, and y are already expressed by variable x, and the above explanation justifies such a drastic experimental results. In practice, however, optimum ordering for variables may not known beforehand, and some heuristic trial may be inevitable.

Weight
======

Weight
======

前節で紹介した項順序は, 各変数に weight (重み) を設定することでより一般的なものとなる.

Term orderings introduced in the previous section can be generalized by setting a weight for each variable.

     [0] dp_td(<<1,1,1>>);
     3
     [1] dp_set_weight([1,2,3])$
     [2] dp_td(<<1,1,1>>);
     6

単項式の全次数を計算する際, デフォルトでは各変数の指数の和を全次数とする. これは各変数の weight を 1 と考えていることに相当する. この例では, 第一, 第二, 第三変数の weight をそれぞれ 1,2,3 と指定している. このため, <<1,1,1>> の全次数 (以下ではこれを単項式の weight と呼ぶ) が 1*1+1*2+1*3=6 となる. weight を設定することで, 同じ項順序型のもとで異なる項順序が定義できる. 例えば, weight をうまく設定することで, 多項式を weighted homogeneous にすることができる場合がある.

By default, the total degree of a monomial is equal to the sum of all exponents. This means that the weight for each variable is set to 1. In this example, the weights for the first, the second and the third variable are set to 1, 2 and 3 respectively. Therefore the total degree of <<1,1,1>> under this weight, which is called the weight of the monomial, is 1*1+1*2+1*3=6. By setting weights, different term orderings can be set under a type of term ordeing. In some case a polynomial can be made weighted homogeneous by setting an appropriate weight.

各変数に対する weight をまとめたものを weight vector と呼ぶ. すべての成分が正であり, グレブナ基底計算において, 全次数の代わりに用いられるものを特に sugar weight と呼ぶことにする. sugar strategy において, 全次数の代わりに使われるからである. 一方で, 各成分が必ずしも正とは限らない weight vector は, sugar weight として設定することはできないが, 項順序の一般化には有用である. これらは, 行列による項順序の設定にすでに現れている. すなわち, 項順序を定義する行列の各行が, 一つの weight vector と見なされる. また, ブロック順序は, 各ブロックの変数に対応する成分のみ 1 で他は 0 の weight vector による比較を最初に行ってから, 各ブロック毎の tie breaking を行うことに相当する.

A list of weights for all variables is called a weight vector. A weight vector is called a sugar weight vector if its elements are all positive and it is used for computing a weighted total degree of a monomial, because such a weight is used instead of total degree in sugar strategy. On the other hand, a weight vector whose elements are not necessarily positive cannot be set as a sugar weight, but it is useful for generalizing term order. In fact, such a weight vector already appeared in a matrix order. That is, each row of a matrix defining a term order is regarded as a weight vector. A block order is also considered as a refinement of comparison by weight vectors. It compares two terms by using a weight vector whose elements corresponding to variables in a block is 1 and 0 otherwise, then it applies a tie breaker.

weight vector の設定は dp_set_weight() で行うことができるが, 項順序を指定する際の他のパラメタ (項順序型, 変数順序) とまとめて設定できることが望ましい. このため, 次のような形でも項順序が指定できる.

A weight vector can be set by using dp_set_weight(). However it is more preferable if a weight vector can be set together with other parapmeters such as a type of term ordering and a variable order. This is realized as follows.

     [64] B=[x+y+z-6,x*y+y*z+z*x-11,x*y*z-6]$
     [65] dp_gr_main(B|v=[x,y,z],sugarweight=[3,2,1],order=0);
     [z^3-6*z^2+11*z-6,x+y+z-6,-y^2+(-z+6)*y-z^2+6*z-11]
     [66] dp_gr_main(B|v=[y,z,x],order=[[1,1,0],[0,1,0],[0,0,1]]);
     [x^3-6*x^2+11*x-6,x+y+z-6,-x^2+(-y+6)*x-y^2+6*y-11]
     [67] dp_gr_main(B|v=[y,z,x],order=[[x,1,y,2,z,3]]);
     [x+y+z-6,x^3-6*x^2+11*x-6,-x^2+(-y+6)*x-y^2+6*y-11]

いずれの例においても, 項順序は option として指定されている. 最初の例では v により変数順序を, sugarweight により sugar weight vector を, orderにより項順序型を指定している. 二つ目の例における order の指定は matrix order と同様である. すなわち, 指定された weight vector を左から順に使って weight の比較を行う. 三つ目の例も同様であるが, ここでは weight vector の要素を変数毎に指定している. 指定がないものは 0 となる. 三つ目の例では, order による指定では項順序が決定しない. この場合には, tie breaker として全次数逆辞書式順序が自動的に設定される. この指定方法は, dp_gr_main, dp_gr_mod_main などの組み込み関数でのみ可能であり, gr などのユーザ定義関数では未対応である.

In each example, a term ordering is specified as options. In the first example, a variable order, a sugar weight vector and a type of term ordering are specified by options v, sugarweight and order respectively. In the second example, an option order is used to set a matrix ordering. That is, the specified weight vectors are used from left to right for comparing terms. The third example shows a variant of specifying a weight vector, where each component of a weight vector is specified variable by variable, and unspecified components are set to zero. In this example, a term order is not determined only by the specified weight vector. In such a case a tie breaker by the graded reverse lexicographic ordering is set automatically. This type of a term ordering specification can be applied only to builtin functions such as dp_gr_main(), dp_gr_mod_main(), not to user defined functions such as gr().

有理式を係数とするグレブナ基底計算
=================

Groebner basis computation with rational function coefficients
==============================================================

gr() などのトップレベル函数は, いずれも, 入力多項式リストに現れる変数 (不定元) と, 変数リストに現れる変数を比較して, 変数リストにない変数が入力多項式に現れている場合には, 自動的に, その変数を, 係数体の元として扱う.

Such variables that appear within the input polynomials but not appearing in the input variable list are automatically treated as elements in the coefficient field by top level functions, such as gr().

     [64] gr([a*x+b*y-c,d*x+e*y-f],[x,y],2);
     [(-e*a+d*b)*x-f*b+e*c,(-e*a+d*b)*y+f*a-d*c]

この例では, a, b, c, d が係数体の元として扱われる. すなわち, 有理函数体 F = Q(a,b,c,d) 上の 2 変数多項式環 F[x,y] におけるグレブナ基底を求めることになる. 注意すべきことは, 係数が体として扱われていることである. すなわち, 係数の間に多項式としての共通因子があった場合には, 結果からその因子は除かれているため, 有理数体上の多項式環上の問題として考えた場合の結果とは一般には異なる. また, 主として計算効率上の問題のため, 分散表現多項式の係数として実際に許されるのは多項式までである. すなわち, 分母を持つ有理式は分散表現多項式の係数としては許されない.

In this example, variables a, b, c, and d are treated as elements in the coefficient field. In this case, a Groebner basis is computed on a bi-variate polynomial ring F[x,y] over rational function field F = Q(a,b,c,d). Notice that coefficients are considered as a member in a field. As a consequence, polynomial factors common to the coefficients are removed so that the result, in general, is different from the result that would be obtained when the problem is considered as a computation of Groebner basis over a polynomial ring with rational function coefficients. And note that coefficients of a distributed polynomial are limited to numbers and polynomials because of efficiency.

基底変換
====

Change of orderng
=================

辞書式順序のグレブナ基底を求める場合, 直接 gr() などを起動するより, 一旦他の順序 (例えば全次数逆辞書式順序) のグレブナ基底を計算して, それを入力として辞書式順序のグレブナ基底を計算する方が効率がよい場合がある. また, 入力が何らかの順序でのグレブナ基底になっている場合, 基底変換と呼ばれる方法により, Buchberger アルゴリズムによらずに効率良く辞書式順序のグレブナ基底が計算できる場合がある. このような目的のための函数が, ユーザ定義函数として gr にいくつか定義されている. 以下の 2 つの函数は, 変数順序 VLIST1, 項順序型 ORDER で既にグレブナ基底となっている多項式リスト GBASE を, 変数順序 VLIST2 における辞書式順序のグレブナ基底に変換する函数である.

When we compute a lex order Groebner basis, it is often efficient to compute it via Groebner basis with respect to another order such as degree reverse lex order, rather than to compute it directory by gr() etc. If we know that an input is a Groebner basis with respect to an order, we can apply special methods called change of ordering for a Groebner basis computation with respect to another order, without using Buchberger algorithm. The following two functions are ones for change of ordering such that they convert a Groebner basis GBASE with respect to the variable order VLIST1 and the order type ORDER into a lex Groebner basis with respect to the variable order VLIST2.

tolex(GBASE,VLIST1,ORDER,VLIST2)

     この函数は, GBASE が有理数体上のシステムの場合にのみ使用可能である. この函数は, 辞書式順序のグレブナ基底を, 有限体上で計算されたグレブナ基底を雛型として, 未定係数法および Hensel 構成により求めるものである.

     This function can be used only when GBASE is an ideal over the rationals.  The input GBASE must be a Groebner basis with respect to the variable order VLIST1 and the order type ORDER. Moreover the ideal generated by GBASE must be zero-dimensional. This computes the lex Groebner basis of GBASE by using the modular change of ordering algorithm. The algorithm first computes the lex Groebner basis over a finite field. Then each element in the lex Groebner basis over the rationals is computed with undetermined coefficient method and linear equation solving by Hensel lifting.

tolex_tl(GBASE,VLIST1,ORDER,VLIST2,HOMO)

     この函数は, 辞書式順序のグレブナ基底を Buchberger アルゴリズムにより求めるものであるが, 入力がある順序におけるグレブナ基底である場合の trace-liftingにおけるグレブナ基底候補の頭項, 頭係数の性質を利用して, 最終的なグレブナ基底チェック, イデアルメンバシップチェックを省略しているため, 単にBuchberger アルゴリズムを繰り返すより効率よく計算できる. 更に, 入力が 0 次元システムの場合, 自動的にもう 1 つの中間的な項順序を経由して辞書式順序のグレブナ基底を計算する. 多くの場合, この方法は, 直接辞書式順序の計算を行うより効率がよい. (もちろん例外あり. ) 引数 HOMO が 0 でない時, hgr() と同様に斉次化を経由して計算を行う.

     This function computes the lex Groebner basis of GBASE.  The input GBASE must be a Groebner basis with respect to the variable order VLIST1 and the order type ORDER. Buchberger algorithm with trace lifting is used to compute the lex Groebner basis, however the Groebner basis check and the ideal membership check can be omitted by using several properties derived from the fact that the input is a Groebner basis. So it is more efficient than simple repetition of Buchberger algorithm. If the input is zero-dimensional, this function inserts automatically a computation of Groebner basis with respect to an elimination order, which makes the whole computation more efficient for many cases. If HOMO is not equal to 0, homogenization is used in each step.

その他, 0 次元システムに対し, 与えられた多項式の最小多項式を求める函数, 0 次元システムの解を, よりコンパクトに表現するための函数などが gr で定義されている. これらについては個々の函数の説明を参照のこと.

For zero-dimensional systems, there are several fuctions to compute the minimal polynomial of a polynomial and or a more compact representation for zeros of the system. They are all defined in gr. Refer to the sections for each functions.

Weyl 代数
=======

Weyl algebra
============

これまでは, 通常の可換な多項式環におけるグレブナ基底計算について述べてきたが, グレブナ基底の理論は, ある条件を満たす非可換な環にも拡張できる. このような環の中で, 応用上も重要な, Weyl 代数, すなわち多項式環上の微分作用素環の演算およびグレブナ基底計算が Risa/Asir に実装されている.

体 K 上の n 次元 Weyl 代数 D=K<x1,...,xn,D1,...,Dn> は

So far we have explained Groebner basis computation in commutative polynomial rings. However Groebner basis can be considered in more general non-commutative rings. Weyl algebra is one of such rings and Risa/Asir implements fundamental operations in Weyl algebra and Groebner basis computation in Weyl algebra.

The n dimensional Weyl algebra over a field K, D=K<x1,...,xn,D1,...,Dn> is a non-commutative algebra which has the following fundamental relations:

xi*xj-xj*xi=0, Di*Dj-Dj*Di=0, Di*xj-xj*Di=0 (i!=j), Di*xi-xi*Di=1

という基本関係を持つ環である. D は 多項式環 K[x1,...,xn] を係数とする微分作用素環で,  Di は xi による微分を表す. 交換関係により, D の元は, x1^i1*...*xn^in*D1^j1*...*Dn^jn なる単項式の K 線形結合として書き表すことができる. Risa/Asir においては, この単項式を, 可換な多項式と同様に <<i1,...,in,j1,...,jn>> で表す. すなわち, D の元も分散表現多項式として表される. 加減算は, 可換の場合と同様に, +, - により実行できるが, 乗算は, 非可換性を考慮して dp_weyl_mul() という関数により実行する.

D is the ring of differential operators whose coefficients are polynomials in K[x1,...,xn] and Di denotes the differentiation with respect to  xi. According to the commutation relation, elements of D can be represented as a K-linear combination of monomials x1^i1*...*xn^in*D1^j1*...*Dn^jn. In Risa/Asir, this type of monomial is represented by <<i1,...,in,j1,...,jn>> as in the case of commutative polynomial. That is, elements of D are represented by distributed polynomials. Addition and subtraction can be done by +, -, but multiplication is done by calling dp_weyl_mul() because of the non-commutativity of D.

     [0] A=<<1,2,2,1>>;
     (1)*<<1,2,2,1>>
     [1] B=<<2,1,1,2>>;
     (1)*<<2,1,1,2>>
     [2] A*B;
     (1)*<<3,3,3,3>>
     [3] dp_weyl_mul(A,B);
     (1)*<<3,3,3,3>>+(1)*<<3,2,3,2>>+(4)*<<2,3,2,3>>+(4)*<<2,2,2,2>>
     +(2)*<<1,3,1,3>>+(2)*<<1,2,1,2>>

グレブナ基底計算についても, Weyl 代数専用の関数として, 次の関数が用意してある.

The following functions are avilable for Groebner basis computation in Weyl algebra:

dp_weyl_gr_main(), dp_weyl_gr_mod_main(), dp_weyl_gr_f_main(), dp_weyl_f4_main(), dp_weyl_f4_mod_main().

また, 応用として, global b 関数の計算が実装されている.

Computation of the global b function is implemented as an application.

グレブナ基底に関する函数
============

Functions for Groebner basis computation
========================================

gr, hgr, gr_mod, dgr
--------------------

gr(PLIST,VLIST,ORDER)
hgr(PLIST,VLIST,ORDER)
gr_mod(PLIST,VLIST,ORDER,P)
dgr(PLIST,VLIST,ORDER,PROCS)
     :: グレブナ基底の計算

     :: Groebner basis computation

return
     リスト

     list

plist  vlist  procs
     リスト

     list

order
     数, リストまたは行列

     number, list or matrix

p
     2^27 未満の素数

     prime less than 2^27

  * 標準ライブラリの gr で定義されている.

  * gr を名前に含む関数は現在メンテされていない. nd_gr系の関数を代わりに利用すべきである(nd_gr nd_gr_trace nd_f4 nd_f4_trace nd_weyl_gr nd_weyl_gr_trace).

  * いずれも, 多項式リスト PLIST の, 変数順序 VLIST, 項順序型 ORDER に関するグレブナ基底を求める. gr(), hgr() は 有理数係数, gr_mod() は GF(P) 係数として計算する.

  * VLIST は不定元のリスト. VLIST に現れない不定元は, 係数体に属すると見なされる.

  * gr(), trace-lifting (モジュラ演算を用いた高速化) および sugar strategy による計算, hgr() は trace-lifting および斉次化による 矯正された sugar strategy による計算を行う.

  * dgr() は, gr(), hgr() を子プロセスリスト PROCS の 2 つのプロセスにより同時に計算させ, 先に結果を返した方の結果を返す. 結果は同一であるが, どちらの方法が高速か一般には不明のため, 実際の経過時間を短縮するのに有効である.

  * dgr() で表示される時間は, この函数が実行されているプロセスでの CPU 時間であり, この函数の場合はほとんど通信のための時間である.

  * 多項式リスト PLIST の要素が分散表現多項式の場合は結果も分散表現多項式のリストである. この場合, 引数の分散多項式は与えられた順序に従い dp_sort でソートされてから計算される. 多項式リストの要素が分散表現多項式の場合も変数の数分の不定元のリストを VLIST 引数として与えないといけない (ダミー).

  * These functions are defined in gr in the standard library directory.

  * Functions of which names contains gr are obsolted. Functions of nd_gr families should be used (nd_gr nd_gr_trace nd_f4 nd_f4_trace nd_weyl_gr nd_weyl_gr_trace).

  * They compute a Groebner basis of a polynomial list PLIST with respect to the variable order VLIST and the order type ORDER. gr() and hgr() compute a Groebner basis over the rationals and gr_mod computes over GF(P).

  * Variables not included in VLIST are regarded as included in the ground field.

  * gr() uses trace-lifting (an improvement by modular computation) and sugar strategy. hgr() uses trace-lifting and a cured sugar strategy by using homogenization.

  * dgr() executes gr(), dgr() simultaneously on two process in a child process list PROCS and returns the result obtained first. The results returned from both the process should be equal, but it is not known in advance which method is faster. Therefore this function is useful to reduce the actual elapsed time.

  * The CPU time shown after an exection of dgr() indicates that of the master process, and most of the time corresponds to the time for communication.

  * When the elements of PLIST are distributed polynomials, the result is also a list of distributed polynomials. In this case, firstly  the elements of PLIST is sorted by dp_sort and the Grobner basis computation is started. Variables must be given in VLIST even in this case (these variables are dummy).

     [0] load("gr")$
     [64] load("cyclic")$
     [74] G=gr(cyclic(5),[c0,c1,c2,c3,c4],2);
     [c4^15+122*c4^10-122*c4^5-1,...]
     [75] GM=gr_mod(cyclic(5),[c0,c1,c2,c3,c4],2,31991)$
     24628*c4^15+29453*c4^10+2538*c4^5+7363
     [76] (G[0]*24628-GM[0])%31991;
     0

参照

References
     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, dp_ord.

lex_hensel, lex_tl, tolex, tolex_d, tolex_tl
--------------------------------------------

lex_hensel(PLIST,VLIST1,ORDER,VLIST2,HOMO)
lex_tl(PLIST,VLIST1,ORDER,VLIST2,HOMO)
     :: 基底変換による辞書式順序グレブナ基底の計算

     \EG:: Groebner basis computation with respect to a lex order by change of ordering

tolex(PLIST,VLIST1,ORDER,VLIST2)
tolex_d(PLIST,VLIST1,ORDER,VLIST2,PROCS)
tolex_tl(PLIST,VLIST1,ORDER,VLIST2,HOMO)
     :: グレブナ基底を入力とする, 基底変換による辞書式順序グレブナ基底の計算

     :: Groebner basis computation with respect to a lex order by change of ordering, starting from a Groebner basis

return
     リスト

     list

plist  vlist1  vlist2  procs
     リスト

     list

order
     数, リストまたは行列

     number, list or matrix

homo
     フラグ

     flag

  * 標準ライブラリの gr で定義されている.

  * lex_hensel(), lex_tl() は, 多項式リスト PLIST の, 変数順序 VLIST1, 項順序型 ORDER に関するグレブナ基底を求め, それを, 変数順序 VLIST2 の辞書式順序グレブナ基底に変換する.

  * tolex(), tolex_tl() は, 変数順序 VLIST1, 項順序型 ORDER に関するグレブナ基底である多項式リスト PLIST を変数順序 VLIST2 の辞書式順序グレブナ基底に変換する. tolex_d() は, tolex() における, 各基底の計算を, 子プロセスリスト PROCS の各プロセスに分散計算させる.

  * lex_hensel(), lex_tl() においては, 辞書式順序グレブナ基底の計算は次のように行われる. ([Noro,Yokoyama] 参照.)

      1. VLIST1, ORDER に関するグレブナ基底 G0 を計算する. (lex_hensel() のみ. )

      2. G0 の各元の VLIST2 に関する辞書式順序における頭係数を割らないような素数 P を選び, GF(P) 上での辞書式順序グレブナ基底 GP を計算する.

      3. GP に現れるすべての項の, G0 に関する正規形 NF を計算する.

      4. GP の各元 F につき, F の係数を未定係数で, F の各項を対応する NF の元で置き換え, 各項の係数を 0 と置いた, 未定係数に関する線形方程式系 LF を作る.

      5. LF が, 法 P で一意解を持つことを用いて LF の解を法 Pの解から Hensel 構成により求める.

      6. すべての GP の元につき線形方程式が解けたらその解全体が求める辞書式順序でのグレブナ基底. もしどれかの線形方程式の求解に失敗したら, P をとり直してやり直す.

  * lex_tl(), tolex_tl() においては, 辞書式順序グレブナ基底の計算は次のように行われる.

      1. VLIST1, ORDER に関するグレブナ基底 G0 を計算する. (lex_hensel() のみ. )

      2. G0 が 0 次元システムでないとき, G0 を入力として, G0 の各元の VLIST2 に関する辞書式順序における頭係数を割らないような素数 P を選び, P を用いた trace-lifting により辞書式順序のグレブナ基底候補を求め, もし求まったならチェックなしにそれが求めるグレブナ基底となる. もし失敗したら, P をとり直してやり直す.

      3. G0 が 0 次元システムのとき, G0 を入力として, まず, VLIST2 の最後の変数以外を消去する消去順序によりグレブナ基底 G1 を計算し, それから辞書式順序のグレブナ基底を計算する. その際, 各ステップでは, 入力の各元の, 求める順序における頭係数を割らない素数を用いた trace-lifting でグレブナ基底候補を求め, もし求まったらチェックなしにそれがその順序でのグレブナ基底となる.

  * 有理式係数の計算は, lex_tl(), tolex_tl() のみ受け付ける.

  * homo が 0 でない場合, 内部で起動される Buchberger アルゴリズムにおいて, 斉次化が行われる.

  * tolex_d() で表示される時間は, この函数が実行されているプロセスにおいて行われた計算に対応していて, 子プロセスにおける時間は含まれない.

  * These functions are defined in gr in the standard library directory.

  * lex_hensel() and lex_tl() first compute a Groebner basis with respect to the variable order VLIST1 and the order type ORDER. Then the Groebner basis is converted into a lex order Groebner basis with respect to the varable order VLIST2.

  * tolex() and tolex_tl() convert a Groebner basis PLIST with respect to the variable order VLIST1 and the order type ORDER into a lex order Groebner basis with respect to the varable order VLIST2. tolex_d() does computations of basis elements in tolex() in parallel on the processes in a child process list PROCS.

  * In lex_hensel() and tolex_hensel() a lex order Groebner basis is computed as follows.(Refer to [Noro,Yokoyama].)

      1. Compute a Groebner basis G0 with respect to VLIST1 and ORDER. (Only in lex_hensel(). )

      2. Choose a prime which does not divide head coefficients of elements in G0 with respect to VLIST1 and ORDER. Then compute a lex order Groebner basis GP over GF(P) with respect to VLIST2.

      3. Compute NF, the set of all the normal forms with respect to G0 of terms appearing in GP.

      4. For each element F in GP, replace coefficients and terms in F with undetermined coefficients and the corresponding polynomials in NF respectively, and generate a system of liear equation LF by equating the coefficients of terms in the replaced polynomial with 0.

      5. Solve LF by Hensel lifting, starting from the unique mod P solution.

      6. If all the linear equations generated from the elements in GP could be solved, then the set of solutions corresponds to a lex order Groebner basis. Otherwise redo the whole process with another P.

  * In lex_tl() and tolex_tl() a lex order Groebner basis is computed as follows.(Refer to [Noro,Yokoyama].)

      1. Compute a Groebner basis G0 with respect to VLIST1 and ORDER. (Only in lex_tl(). )

      2. If G0 is not zero-dimensional, choose a prime which does not divide head coefficients of elements in G0 with respect to VLIST1 and ORDER. Then compute a candidate of a lex order Groebner basis via trace lifting with P. If it succeeds the candidate is indeed a lex order Groebner basis without any check. Otherwise redo the whole process with another P.

      3. If G0 is zero-dimensional, starting from G0, compute a Groebner basis G1 with respect to an elimination order to eliminate variables other than the last varibale in VLIST2. Then compute a lex order Groebner basis stating from G1. These computations are done by trace lifting and the selection of a mudulus P is the same as in non zero-dimensional cases.

  * Computations with rational function coefficients can be done only by lex_tl() and tolex_tl().

  * If homo is not equal to 0, homogenization is used in Buchberger algorithm.

  * The CPU time shown after an execution of tolex_d() indicates that of the master process, and it does not include the time in child processes.

     [78] K=katsura(5)$
     30msec + gc : 20msec
     [79] V=[u5,u4,u3,u2,u1,u0]$
     0msec
     [80] G0=hgr(K,V,2)$
     91.558sec + gc : 15.583sec
     [81] G1=lex_hensel(K,V,0,V,0)$
     49.049sec + gc : 9.961sec
     [82] G2=lex_tl(K,V,0,V,1)$
     31.186sec + gc : 3.500sec
     [83] gb_comp(G0,G1);
     1
     10msec
     [84] gb_comp(G0,G2);
     1

参照

References
     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, dp_ord, 分散計算

     dp_ord, Distributed computation

lex_hensel_gsl, tolex_gsl, tolex_gsl_d
--------------------------------------

lex_hensel_gsl(PLIST,VLIST1,ORDER,VLIST2,HOMO)
     :: GSL 形式のイデアル基底の計算

     ::Computation of an GSL form ideal basis

tolex_gsl(PLIST,VLIST1,ORDER,VLIST2)
tolex_gsl_d(PLIST,VLIST1,ORDER,VLIST2,PROCS)
     :: グレブナ基底を入力とする, GSL 形式のイデアル基底の計算

     :: Computation of an GSL form ideal basis stating from a Groebner basis

return
     リスト

     list

plist  vlist1  vlist2  procs
     リスト

     list

order
     数, リストまたは行列

     number, list or matrix

homo
     フラグ

     flag

  * lex_hensel_gsl() は lex_hensel() の, tolex_gsl() は tolex() の変種で, 結果のみが異なる. tolex_gsl_d() は, 基底計算を, procs で指定される子プロセスに分散計算させる.

  * 入力が 0 次元システムで, その辞書式順序グレブナ基底が [f0,x1-f1,...,xn-fn] (f0,...,fn は x0 の 1 変数多項式) なる形 (これを SL 形式と呼ぶ) を持つ場合, [[x1,g1,d1],...,[xn,gn,dn],[x0,f0,f0']] なるリスト (これを GSL 形式と呼ぶ) を返す. ここで, gi は, di*f0'*fi-gi が f0 で割り切れるような x0 の1 変数多項式で, 解は f0(x0)=0 なる x0 に対し, [x1=g1/(d1*f0'),...,xn=gn/(dn*f0')] となる. 辞書式順序グレブナ基底が上のような形でない場合, tolex() による通常のグレブナ基底を返す.

  * GSL 形式により表される基底はグレブナ基底ではないが, 一般に係数が SL 形式のグレブナ基底より非常に小さいため計算も速く, 解も求めやすい. tolex_gsl_d() で表示される時間は, この函数が実行されているプロセスにおいて行われた計算に対応していて, 子プロセスにおける時間は含まれない.

  * lex_hensel_gsl() and lex_hensel() are variants of tolex_gsl() and tolex() respectively. The results are Groebner basis or a kind of ideal basis, called GSL form. tolex_gsl_d() does basis computations in parallel on child processes specified in procs.

  * If the input is zero-dimensional and a lex order Groebner basis has the form [f0,x1-f1,...,xn-fn] (f0,...,fn are univariate polynomials of x0; SL form), then this these functions return a list such as [[x1,g1,d1],...,[xn,gn,dn],[x0,f0,f0']] (GSL form).  In this list gi is a univariate polynomial of x0 such that di*f0'*fi-gi divides f0 and the roots of the input ideal is [x1=g1/(d1*f0'),...,xn=gn/(dn*f0')] for x0 such that f0(x0)=0. If the lex order Groebner basis does not have the above form, these functions return a lex order Groebner basis computed by tolex().

  * Though an ideal basis represented as GSL form is not a Groebner basis we can expect that the coefficients are much smaller than those in a Groebner basis and that the computation is efficient. The CPU time shown after an execution of tolex_gsl_d() indicates that of the master process, and it does not include the time in child processes.

     [103] K=katsura(5)$
     [104] V=[u5,u4,u3,u2,u1,u0]$
     [105] G0=gr(K,V,0)$
     [106] GSL=tolex_gsl(G0,V,0,V)$
     [107] GSL[0];
     [u1,8635837421130477667200000000*u0^31-...]
     [108] GSL[1];
     [u2,10352277157007342793600000000*u0^31-...]
     [109] GSL[5];
     [u0,11771021876193064124640000000*u0^32-...,
     376672700038178051988480000000*u0^31-...]

参照

References
     lex_hensel lex_tl tolex tolex_d tolex_tl, 分散計算

     Distributed computation

gr_minipoly, minipoly
---------------------

gr_minipoly(PLIST,VLIST,ORDER,POLY,V,HOMO)
     :: 多項式の, イデアルを法とした最小多項式の計算

     :: Computation of the minimal polynomial of a polynomial modulo an ideal

minipoly(PLIST,VLIST,ORDER,POLY,V)
     :: グレブナ基底を入力とする, 多項式の最小多項式の計算

     :: Computation of the minimal polynomial of a polynomial modulo an ideal

return
     多項式

     polynomial

plist  vlist
     リスト

     list

order
     数, リストまたは行列

     number, list or matrix

poly
     多項式

     polynomial

v
     不定元

     indeterminate

homo
     フラグ

     flag

  * gr_minipoly() はグレブナ基底の計算から行い, minipoly() は入力をグレブナ基底とみなす.

  * イデアル I が体 K 上の多項式環 K[X] の 0 次元イデアルの時, K[V] の元 f(V) に f(P) mod I を対応させる環準同型の核は 0 でない多項式により生成される. この生成元を P の, 法 I での最小多項式と呼ぶ.

  * gr_minipoly(), minipoly() は, 多項式 P の最小多項式を求め, V を変数とする多項式として返す.

  * 最小多項式は, グレブナ基底の 1 つの元として計算することもできるが, 最小多項式のみを求めたい場合, minipoly(), gr_minipoly() はグレブナ基底を用いる方法に比べて効率がよい.

  * gr_minipoly() に指定する項順序としては, 通常全次数逆辞書式順序を用いる.

  * gr_minipoly() begins by computing a Groebner basis. minipoly() regards an input as a Groebner basis with respect to the variable order VLIST and the order type ORDER.

  * Let K be a field. If an ideal I in K[X] is zero-dimensional, then, for a polynomial P in K[X], the kernel of a homomorphism from K[V] to K[X]/I which maps f(V) to f(P) mod I is generated by a polynomial. The generator is called the minimal polynomial of P modulo I.

  * gr_minipoly() and minipoly() computes the minimal polynomial of a polynomial P and returns it as a polynomial of V.

  * The minimal polynomial can be computed as an element of a Groebner basis. But if we are only interested in the minimal polynomial, minipoly() and gr_minipoly() can compute it more efficiently than methods using Groebner basis computation.

  * It is recommended to use a degree reverse lex order as a term order for gr_minipoly().

     [117] G=tolex(G0,V,0,V)$
     43.818sec + gc : 11.202sec
     [118] GSL=tolex_gsl(G0,V,0,V)$
     17.123sec + gc : 2.590sec
     [119] MP=minipoly(G0,V,0,u0,z)$
     4.370sec + gc : 780msec

参照

References
     lex_hensel lex_tl tolex tolex_d tolex_tl.

tolexm, minipolym
-----------------

tolexm(PLIST,VLIST1,ORDER,VLIST2,MOD)
     :: 法 MOD での基底変換によるグレブナ基底計算

     :: Groebner basis computation modulo MOD by change of ordering.

minipolym(PLIST,VLIST1,ORDER,POLY,V,MOD)
     :: 法 MOD でのグレブナ基底による多項式の最小多項式の計算

     :: Minimal polynomial computation modulo MOD the same method as

return
     tolexm() : リスト, minipolym() : 多項式

     tolexm() : list, minipolym() : polynomial

plist  vlist1  vlist2
     リスト

     list

order
     数, リストまたは行列

     number, list or matrix

mod
     素数

     prime

  * 入力 PLIST はいずれも 変数順序 VLIST1, 項順序型 ORDER, 法 MOD におけるグレブナ基底でなければならない.

  * minipolym() は minipoly に対応する計算を法 MODで行う.

  * tolexm() は FGLM 法による基底変換により VLIST2, 辞書式順序によるグレブナ基底を計算する.

  * An input PLIST must be a Groebner basis modulo MOD with respect to the variable order VLIST1 and the order type ORDER.

  * minipolym() executes the same computation as in minipoly.

  * tolexm() computes a lex order Groebner basis modulo MOD with respect to the variable order VLIST2, by using FGLM algorithm.

     [197] tolexm(G0,V,0,V,31991);
     [8271*u0^31+10435*u0^30+816*u0^29+26809*u0^28+...,...]
     [198] minipolym(G0,V,0,u0,z,31991);
     z^32+11405*z^31+20868*z^30+21602*z^29+...

参照

References
     lex_hensel lex_tl tolex tolex_d tolex_tl, gr_minipoly minipoly.

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
-------------------------------------------------------------------------------------------------

dp_gr_main(PLIST,VLIST,HOMO,MODULAR,ORDER)
dp_gr_mod_main(PLIST,VLIST,HOMO,MODULAR,ORDER)
dp_gr_f_main(PLIST,VLIST,HOMO,ORDER)
dp_weyl_gr_main(PLIST,VLIST,HOMO,MODULAR,ORDER)
dp_weyl_gr_mod_main(PLIST,VLIST,HOMO,MODULAR,ORDER)
dp_weyl_gr_f_main(PLIST,VLIST,HOMO,ORDER)
     :: グレブナ基底の計算 (組み込み函数)

     :: Groebner basis computation (built-in functions)

return
     リスト

     list

plist  vlist
     リスト

     list

order
     数, リストまたは行列

     number, list or matrix

homo
     フラグ

     flag

modular
     フラグまたは素数

     flag or prime

  * これらの函数は, グレブナ基底計算の基本的組み込み函数であり, gr(), hgr(), gr_mod() などはすべてこれらの函数を呼び出して計算を行っている. 関数名に weyl が入っているものは, Weyl 代数上の計算のための関数である.

  * dp_gr_f_main(), dp_weyl_f_main() は, 種々の有限体上のグレブナ基底を計算する場合に用いる. 入力は, あらかじめ, simp_ff() などで, 考える有限体上に射影されている必要がある.

  * フラグ HOMO が 0 でない時, 入力を斉次化してから Buchberger アルゴリズムを実行する.

  * dp_gr_mod_main() に対しては, MODULAR は, GF(MODULAR) 上での計算を意味する. dp_gr_main() に対しては, MODULAR は次のような意味を持つ.

      1. MODULAR が 1 の時, trace-lifting による計算を行う. 素数は lprime(0) から順に成功するまで lprime() を呼び出して生成する.

      2. MODULAR が 2 以上の自然数の時, その値を素数とみなして trace-lifting を行う. その素数で失敗した場合, 0 を返す.

      3. MODULAR が負の場合, -MODULAR に対して上述の規則が適用されるが, trace-lifting の最終段階のグレブナ基底チェックとイデアルメンバシップチェックが省略される.

  * gr(P,V,O) は dp_gr_main(P,V,0,1,O), hgr(P,V,O) は dp_gr_main(P,V,1,1,O), gr_mod(P,V,O,M) は dp_gr_mod_main(P,V,0,M,O) をそれぞれ実行する.

  * HOMO, MODULAR の他に, dp_gr_flags() で設定されるさまざまなフラグにより計算が制御される.

  * These functions are fundamental built-in functions for Groebner basis computation and gr(),hgr() and gr_mod() are all interfaces to these functions. Functions whose names contain weyl are those for computation in Weyl algebra.

  * dp_gr_f_main() and dp_weyl_gr_f_main() are functions for Groebner basis computation over various finite fields. Coefficients of input polynomials must be converted to elements of a finite field currently specified by setmod_ff().

  * If HOMO is not equal to 0, homogenization is applied before entering Buchberger algorithm

  * For dp_gr_mod_main(), MODULAR means a computation over GF(MODULAR). For dp_gr_main(), MODULAR has the following mean.

      1. If MODULAR is 1 , trace lifting is used. Primes for trace lifting are generated by lprime(), starting from lprime(0), until the computation succeeds.

      2. If MODULAR is an integer  greater than 1, the integer is regarded as a prime and trace lifting is executed by using the prime. If the computation fails then 0 is returned.

      3. If MODULAR is negative, the above rule is applied for -MODULAR but the Groebner basis check and ideal-membership check are omitted in the last stage of trace lifting.

  * gr(P,V,O), hgr(P,V,O) and gr_mod(P,V,O,M) execute dp_gr_main(P,V,0,1,O), dp_gr_main(P,V,1,1,O) and dp_gr_mod_main(P,V,0,M,O) respectively.

  * Actual computation is controlled by various parameters set by dp_gr_flags(), other then by HOMO and MODULAR.

参照

References
     dp_ord, dp_gr_flags dp_gr_print, gr hgr gr_mod, setmod_ff, 計算および表示の制御.

     Controlling Groebner basis computations

dp_f4_main, dp_f4_mod_main, dp_weyl_f4_main, dp_weyl_f4_mod_main
----------------------------------------------------------------

dp_f4_main(PLIST,VLIST,ORDER)
dp_f4_mod_main(PLIST,VLIST,ORDER)
dp_weyl_f4_main(PLIST,VLIST,ORDER)
dp_weyl_f4_mod_main(PLIST,VLIST,ORDER)
     :: F4 アルゴリズムによるグレブナ基底の計算 (組み込み函数)

     :: Groebner basis computation by F4 algorithm (built-in functions)

return
     リスト

     list

plist  vlist
     リスト

     list

order
     数, リストまたは行列

     number, list or matrix

  * F4 アルゴリズムによりグレブナ基底の計算を行う.

  * F4 アルゴリズムは, J.C. Faugere により提唱された新世代グレブナ基底算法であり, 本実装は, 中国剰余定理による線形方程式求解を用いた試験的な実装である.

  * 斉次化の引数がないことを除けば, 引数および動作はそれぞれ dp_gr_main(), dp_gr_mod_main(), dp_weyl_gr_main(), dp_weyl_gr_mod_main() と同様である.

  * These functions compute Groebner bases by F4 algorithm.

  * F4 is a new generation algorithm for Groebner basis computation invented by J.C. Faugere. The current implementation of dp_f4_main() uses Chinese Remainder theorem and not highly optimized.

  * Arguments and actions are the same as those of dp_gr_main(), dp_gr_mod_main(), dp_weyl_gr_main(), dp_weyl_gr_mod_main(), except for lack of the argument for controlling homogenization.

参照

References
     dp_ord, dp_gr_flags dp_gr_print, gr hgr gr_mod, 計算および表示の制御.

     Controlling Groebner basis computations

nd_gr, nd_gr_trace, nd_f4, nd_f4_trace, nd_weyl_gr, nd_weyl_gr_trace
--------------------------------------------------------------------

nd_gr(PLIST,VLIST,P,ORDER)
nd_gr_trace(PLIST,VLIST,HOMO,P,ORDER)
nd_f4(PLIST,VLIST,MODULAR,ORDER)
nd_f4_trace(PLIST,VLIST,HOMO,P,ORDER)
nd_weyl_gr(PLIST,VLIST,P,ORDER)
nd_weyl_gr_trace(PLIST,VLIST,HOMO,P,ORDER)
     :: グレブナ基底の計算 (組み込み函数)

     :: Groebner basis computation (built-in functions)

return
     リスト

     list

plist  vlist
     リスト

     list

order
     数, リストまたは行列

     number, list or matrix

homo
     フラグ

     flag

modular
     フラグまたは素数

     flag or prime

  * これらの函数は, グレブナ基底計算組み込み関数の新実装である.

  * nd_gr は, p が 0 のとき有理数体上の Buchberger アルゴリズムを実行する. p が 2 以上の自然数のとき, GF(p) 上の Buchberger アルゴリズムを実行する.

  * nd_gr_trace および nd_f4_trace は有理数体上で trace アルゴリズムを実行する. P が 0 または 1 のとき, 自動的に選ばれた素数を用いて, 成功するまで trace アルゴリズムを実行する. P が 2 以上のとき, trace はGF(p) 上で計算される. trace アルゴリズムが失敗した場合 0 が返される. P が負の場合, グレブナ基底チェックは行わない. この場合, P が -1 ならば自動的に選ばれた素数が, それ以外は指定された素数を用いてグレブナ基底候補の計算が行われる. nd_f4_trace は, 各全次数について, ある有限体上で F4 アルゴリズムで行った結果をもとに, その有限体上で 0 でない基底を与える S-多項式のみを用いて行列生成を行い, その全次数における基底を生成する方法である. 得られる多項式集合はやはりグレブナ基底候補であり, nd_gr_trace と同様のチェックが行われる.

  * nd_f4 は modular が 0 のとき有理数体上の, modular がマシンサイズ素数のとき有限体上の F4 アルゴリズムを実行する.

  * PLIST が多項式リストの場合, PLISTで生成されるイデアルのグレブナー基底が計算される. PLIST が多項式リストのリストの場合, 各要素は多項式環上の自由加群の元と見なされ, これらが生成する部分加群のグレブナー基底が計算される. 後者の場合, 項順序は加群に対する項順序を指定する必要がある. これは [S,ORD] の形で指定する. S が 0 ならば TOP (Term Over Position), 1 ならば POT (Position Over Term) を意味し, ORD は多項式環の単項式に対する項順序である.

  * nd_weyl_gr, nd_weyl_gr_trace は Weyl 代数用である.

  * f4 系関数以外はすべて有理関数係数の計算が可能である.

  * 一般に dp_gr_main, dp_gr_mod_main より高速であるが, 特に有限体上の場合顕著である.

  * These functions are new implementations for computing Groebner bases.

  * nd_gr executes Buchberger algorithm over the rationals if  p is 0, and that over GF(p) if p is a prime.

  * nd_gr_trace executes the trace algorithm over the rationals. If p is 0 or 1, the trace algorithm is executed until it succeeds by using automatically chosen primes. If p a positive prime, the trace is comuted over GF(p). If the trace algorithm fails 0 is returned. If p is negative, the Groebner basis check and ideal-membership check are omitted. In this case, an automatically chosen prime if p is 1, otherwise the specified prime is used to compute a Groebner basis candidate. Execution of nd_f4_trace is done as follows: For each total degree, an F4-reduction of S-polynomials over a finite field is done, and S-polynomials which give non-zero basis elements are gathered. Then F4-reduction over Q is done for the gathered S-polynomials. The obtained polynomial set is a Groebner basis candidate and the same check procedure as in the case of nd_gr_trace is done.

  * nd_f4 executes F4 algorithm over Q if modular is equal to 0, or over a finite field GF(modular) if modular is a prime number of machine size (<2^29). If PLIST is a list of polynomials, then a Groebner basis of the ideal generated by PLIST is computed. If PLIST is a list of lists of polynomials, then each list of polynomials are regarded as an element of a free module over a polynomial ring and a Groebner basis of the sub-module generated by PLIST in the free module. In the latter case a term order in the free module should be specified. This is specified by [S,ORD]. If S is 0 then it means TOP (Term Over Position). If S is 1 then it means POT 1 (Position Over Term). ORD is a term order in the base polynomial ring.

  * nd_weyl_gr, nd_weyl_gr_trace are for Weyl algebra computation.

  * Functions except for F4 related ones can handle rational coeffient cases.

  * In general these functions are more efficient than dp_gr_main, dp_gr_mod_main, especially over finite fields.

     [38] load("cyclic")$
     [49] C=cyclic(7)$
     [50] V=vars(C)$
     [51] cputime(1)$
     [52] dp_gr_mod_main(C,V,0,31991,0)$
     26.06sec + gc : 0.313sec(26.4sec)
     [53] nd_gr(C,V,31991,0)$
     ndv_alloc=1477188
     5.737sec + gc : 0.1837sec(5.921sec)
     [54] dp_f4_mod_main(C,V,31991,0)$
     3.51sec + gc : 0.7109sec(4.221sec)
     [55] nd_f4(C,V,31991,0)$
     1.906sec + gc : 0.126sec(2.032sec)

参照

References
     dp_ord, dp_gr_flags dp_gr_print, 計算および表示の制御.

     Controlling Groebner basis computations

dp_gr_flags, dp_gr_print
------------------------

dp_gr_flags([LIST])
dp_gr_print([I])
     :: 計算および表示用パラメタの設定, 参照

     \BEG :: Set and show various parameters for cotrolling computations and showing informations.

return
     設定値

     value currently set

list
     リスト

     list

i
     整数

     integer

  * dp_gr_main(), dp_gr_mod_main(), dp_gr_f_main()  実行時におけるさまざまなパラメタを設定, 参照する.

  * 引数がない場合, 現在の設定が返される.

  * 引数は, ["Print",1,"NoSugar",1,...] なる形のリストで, 左から順に設定される. パラメタ名は文字列で与える必要がある.

  * dp_gr_print() は, 特にパラメタ Print, PrintShort の値を直接設定, 参照できる. 設定される値は次の通りである。

     i=0
          Print=0, PrintShort=0

     i=1
          Print=1, PrintShort=0

     i=2
          Print=0, PrintShort=1

     これは, dp_gr_main() などをサブルーチンとして用いるユーザ函数において, そのサブルーチンが中間情報の表示を行う際に, 迅速にフラグを見ることができるように用意されている.

  * dp_gr_flags() sets and shows various parameters for Groebner basis computation.

  * If no argument is specified the current settings are returned.

  * Arguments must be specified as a list such as ["Print",1,"NoSugar",1,...]. Names of parameters must be character strings.

  * dp_gr_print() is used to set and show the value of a parameter Print and PrintShort.

     i=0
          Print=0, PrintShort=0

     i=1
          Print=1, PrintShort=0

     i=2
          Print=0, PrintShort=1

     This functions is prepared to get quickly the value when a user defined function calling dp_gr_main() etc. uses the value as a flag for showing intermediate informations.

参照

References

     計算および表示の制御

     Controlling Groebner basis computations

dp_ord
------

dp_ord([ORDER])
     :: 変数順序型の設定, 参照

     :: Set and show the ordering type.

return
     変数順序型 (数, リストまたは行列)

     ordering type (number, list or matrix)

order
     数, リストまたは行列

     number, list or matrix

  * 引数がある時, 変数順序型を ORDER に設定する. 引数がない時, 現在設定されている変数順序型を返す.

  * 分散表現多項式に関する函数, 演算は引数として変数順序型をとるものととらないものがあり, とらないものに関しては, その時点で設定されている値を用いて計算が行われる.

  * gr() など, 引数として変数順序型をとるものは, 内部で dp_ord() を呼び出し, 変数順序型を設定する. この設定は, 計算終了後も生き残る.

  * 分散表現多項式の四則演算も, 設定されている値を用いて計算される. 従って, その多項式が生成された時点における変数順序型が, 四則演算時に正しく設定されていなければならない. また, 演算対象となる多項式は, 同一の変数順序型に基づいて生成されたものでなければならない.

  * トップレベル函数以外の函数を直接呼び出す場合には, この函数により変数順序型を正しく設定しなければならない.

  * If an argument is specified, the function sets the current ordering type to ORDER. If no argument is specified, the function returns the ordering type currently set.

  * There are two types of functions concerning distributed polynomial, functions which take a ordering type and those which don't take it. The latter ones use the current setting.

  * Functions such as gr(), which need a ordering type as an argument, call dp_ord() internally during the execution. The setting remains after the execution.

     Fundamental arithmetics for distributed polynomial also use the current setting. Therefore, when such arithmetics for distributed polynomials are done, the current setting must coincide with the ordering type which was used upon the creation of the polynomials. It is assumed that such polynomials were generated under the same ordering type.

  * Type of term ordering must be correctly set by this function when functions other than top level functions are called directly.

     [19] dp_ord(0)$
     [20] <<1,2,3>>+<<3,1,1>>;
     (1)*<<1,2,3>>+(1)*<<3,1,1>>
     [21] dp_ord(2)$
     [22] <<1,2,3>>+<<3,1,1>>;
     (1)*<<3,1,1>>+(1)*<<1,2,3>>

参照

References

     項順序の設定

     Setting term orderings

dp_set_weight, dp_set_top_weight, dp_weyl_set_weight
----------------------------------------------------

dp_set_weight([WEIGHT])
     :: sugar weight の設定, 参照

     :: Set and show the sugar weight.

dp_set_top_weight([WEIGHT])
     :: top weight の設定, 参照

     :: Set and show the top weight.

dp_weyl_set_weight([WEIGHT])
     :: weyl weight の設定, 参照

     :: Set and show the weyl weight.

return
     ベクトル

     a vector

weight
     整数のリストまたはベクトル

     a list or vector of integers

  * dp_set_weight は sugar weight を WEIGHT に設定する. 引数がない時, 現在設定されている sugar weight を返す. sugar weight は正整数を成分とするベクトルで, 各変数の重みを表す. 次数つき順序において, 単項式の次数を計算する際に用いられる. 斉次化変数用に, 末尾に 1 を付け加えておくと安全である.

  * dp_set_top_weight は top weight を WEIGHT に設定する. 引数がない時, 現在設定されている top weight を返す. top weight が設定されているとき, まず top weight による単項式比較を先に行う. tie breaker として現在設定されている項順序が用いられるが, この比較には top weight は用いられない.

  * dp_weyl_set_weight は weyl weight を WEIGHT に設定する. 引数がない時, 現在設定されている weyl weight を返す. weyl weight w を設定すると, 項順序型 11 での計算において, (-w,w) を top weight, tie breaker を graded reverse lex とした項順序が設定される.

  * dp_set_weight sets the sugar weight=WEIGHT. It returns the current sugar weight. A sugar weight is a vector with positive integer components and it represents the weights of variables. It is used for computing the weight of a monomial in a graded ordering. It is recommended to append a component 1 at the end of the weight vector for a homogenizing variable.

  * dp_set_top_weight sets the top weight=WEIGHT. It returns the current top weight. It a top weight is set, the weights of monomials under the top weight are firstly compared. If the the weights are equal then the current term ordering is applied as a tie breaker, but the top weight is not used in the tie breaker.

  * dp_weyl_set_weight sets the weyl weigh=WEIGHT. It returns the current weyl weight. If a weyl weight w is set, in the comparsion by the term order type 11, a term order with the top weight=(-w,w) and the tie breaker=graded reverse lex is applied.

参照

References
     Weight

dp_ptod
-------

dp_ptod(POLY,VLIST)
     :: 多項式を分散表現多項式に変換する.

     :: Converts an ordinary polynomial into a distributed polynomial.

return
     分散表現多項式

     distributed polynomial

poly
     多項式

     polynomial

vlist
     リスト

     list

  * 変数順序 VLIST および現在の変数順序型に従って分散表現多項式に変換する.

  * VLIST に含まれない不定元は, 係数体に属するとして変換される.

  * According to the variable ordering VLIST and current type of term ordering, this function converts an ordinary polynomial into a distributed polynomial.

  * Indeterminates not included in VLIST are regarded to belong to the coefficient field.

     [50] dp_ord(0);
     1
     [51] dp_ptod((x+y+z)^2,[x,y,z]);
     (1)*<<2,0,0>>+(2)*<<1,1,0>>+(1)*<<0,2,0>>+(2)*<<1,0,1>>+(2)*<<0,1,1>>
     +(1)*<<0,0,2>>
     [52] dp_ptod((x+y+z)^2,[x,y]);
     (1)*<<2,0>>+(2)*<<1,1>>+(1)*<<0,2>>+(2*z)*<<1,0>>+(2*z)*<<0,1>>
     +(z^2)*<<0,0>>

参照

References
     dp_dtop, dp_ord.

dp_dtop
-------

dp_dtop(DPOLY,VLIST)
     :: 分散表現多項式を多項式に変換する.

     :: Converts a distributed polynomial into an ordinary polynomial.

return
     多項式

     polynomial

dpoly
     分散表現多項式

     distributed polynomial

vlist
     リスト

     list

  * 分散表現多項式を, 与えられた不定元リストを用いて多項式に変換する.

  * 不定元リストは, 長さ分散表現多項式の変数の個数と一致していれば何でもよい.

  * This function converts a distributed polynomial into an ordinary polynomial according to a list of indeterminates VLIST.

  * VLIST is such a list that its length coincides with the number of variables of DPOLY.

     [53] T=dp_ptod((x+y+z)^2,[x,y]);
     (1)*<<2,0>>+(2)*<<1,1>>+(1)*<<0,2>>+(2*z)*<<1,0>>+(2*z)*<<0,1>>
     +(z^2)*<<0,0>>
     [54] P=dp_dtop(T,[a,b]);
     z^2+(2*a+2*b)*z+a^2+2*b*a+b^2

dp_mod, dp_rat
--------------

dp_mod(P,MOD,SUBST)
     :: 有理数係数分散表現多項式の有限体係数への変換

     :: Converts a disributed polynomial into one with coefficients in a finite field.

dp_rat(P)
     :: 有限体係数分散表現多項式の有理数係数への変換

     :: Converts a distributed polynomial with coefficients in a finite field into one with coefficients in the rationals.

return
     分散表現多項式

     distributed polynomial

p
     分散表現多項式

     distributed polynomial

mod
     素数

     prime

subst
     リスト

     list

  * dp_nf_mod(), dp_true_nf_mod() は, 入力として有限体係数の分散表現多項式を必要とする. このような場合, dp_mod() により有理数係数分散表現多項式を変換して用いることができる. また, 得られた結果は, 有限体係数多項式とは演算できるが, 有理数係数多項式とは演算できないため, dp_rat() により変換する必要がある.

  * 有限体係数の演算においては, あらかじめ setmod() により有限体の元の個数を指定しておく必要がある.

  * SUBST は, 係数が有理式の場合, その有理式の変数にあらかじめ数を代入した後有限体係数に変換するという操作を行う際の, 代入値を指定するもので, [[VAR,VALUE],...] の形のリストである.

  * dp_nf_mod() and dp_true_nf_mod() require distributed polynomials with coefficients in a finite field as arguments. dp_mod() is used to convert distributed polynomials with rational number coefficients into appropriate ones. Polynomials with coefficients in a finite field cannot be used as inputs of operations with polynomials with rational number coefficients. dp_rat() is used for such cases.

  * The ground finite field must be set in advance by using setmod().

  * SUBST is such a list as [[VAR,VALUE],...]. This is valid when the ground field of the input polynomial is a rational function field. VAR's are variables in the ground field and the list means that VALUE is substituted for VAR before converting the coefficients into elements of a finite field.

参照

References
     dp_nf dp_nf_mod dp_true_nf dp_true_nf_mod dp_weyl_nf dp_weyl_nf_mod, subst psubst, setmod.

dp_homo, dp_dehomo
------------------

dp_homo(DPOLY)
     :: 分散表現多項式の斉次化

     :: Homogenize a distributed polynomial

dp_dehomo(DPOLY)
     :: 斉次分散表現多項式の非斉次化

     :: Dehomogenize a homogenious distributed polynomial

return
     分散表現多項式

     distributed polynomial

dpoly
     分散表現多項式

     distributed polynomial

  * dp_homo() は, DPOLY の 各項 T について, 指数ベクトルの長さを 1 伸ばし, 最後の成分の値を D-deg(T) (D は DPOLY の全次数) とした分散表現多項式を返す.

  * dp_dehomo() は, DPOLY の各項について, 指数ベクトルの最後の成分を取り除いた分散多項式を返す.

  * いずれも, 生成された多項式を用いた演算を行う場合, それらに適合する項順序を正しく設定する必要がある.

  * hgr() などにおいて, 内部的に用いられている.

  * dp_homo() makes a copy of DPOLY, extends the length of the exponent vector of each term T in the copy by 1, and sets the value of the newly appended component to D-deg(T), where D is the total degree of DPOLY.

  * dp_dehomo() make a copy of DPOLY and removes the last component of each terms in the copy.

  * Appropriate term orderings must be set when the results are used as inputs of some operations.

  * These are used internally in hgr() etc.

     [202] X=<<1,2,3>>+3*<<1,2,1>>;
     (1)*<<1,2,3>>+(3)*<<1,2,1>>
     [203] dp_homo(X);
     (1)*<<1,2,3,0>>+(3)*<<1,2,1,2>>
     [204] dp_dehomo(@);
     (1)*<<1,2,3>>+(3)*<<1,2,1>>

参照

References
     gr hgr gr_mod.

dp_ptozp, dp_prim
-----------------

dp_ptozp(DPOLY)
     :: 定数倍して係数を整数係数かつ係数の整数 GCD を 1 にする.

     :: Converts a distributed polynomial POLY with rational coefficients into an integral distributed polynomial such that GCD of all its coefficients is 1.

dp_prim(DPOLY)
     :: 有理式倍して係数を整数係数多項式係数かつ係数の多項式 GCD を 1 にする.

     :: Converts a distributed polynomial POLY with rational function coefficients into an integral distributed polynomial such that polynomial GCD of all its coefficients is 1.

return
     分散表現多項式

     distributed polynomial

dpoly
     分散表現多項式

     distributed polynomial

  * dp_ptozp() は,  ptozp() に相当する操作を分散表現多項式に対して行う. 係数が多項式を含む場合, 係数に含まれる多項式共通因子は取り除かない.

  * dp_prim() は, 係数が多項式を含む場合, 係数に含まれる多項式共通因子を取り除く.

  * dp_ptozp() executes the same operation as ptozp() for a distributed polynomial. If the coefficients include polynomials, polynomial contents included in the coefficients are not removed.

  * dp_prim() removes polynomial contents.

     [208] X=dp_ptod(3*(x-y)*(y-z)*(z-x),[x]);
     (-3*y+3*z)*<<2>>+(3*y^2-3*z^2)*<<1>>+(-3*z*y^2+3*z^2*y)*<<0>>
     [209] dp_ptozp(X);
     (-y+z)*<<2>>+(y^2-z^2)*<<1>>+(-z*y^2+z^2*y)*<<0>>
     [210] dp_prim(X);
     (1)*<<2>>+(-y-z)*<<1>>+(z*y)*<<0>>

参照

References
     ptozp.

dp_nf, dp_nf_mod, dp_true_nf, dp_true_nf_mod
--------------------------------------------

dp_nf(INDEXLIST,DPOLY,DPOLYARRAY,FULLREDUCE)

dp_weyl_nf(INDEXLIST,DPOLY,DPOLYARRAY,FULLREDUCE)

dp_nf_mod(INDEXLIST,DPOLY,DPOLYARRAY,FULLREDUCE,MOD)

dp_weyl_nf_mod(INDEXLIST,DPOLY,DPOLYARRAY,FULLREDUCE,MOD)
     :: 分散表現多項式の正規形を求める. (結果は定数倍されている可能性あり)

     :: Computes the normal form of a distributed polynomial. (The result may be multiplied by a constant in the ground field.)

dp_true_nf(INDEXLIST,DPOLY,DPOLYARRAY,FULLREDUCE)

dp_true_nf_mod(INDEXLIST,DPOLY,DPOLYARRAY,FULLREDUCE,MOD)
     :: 分散表現多項式の正規形を求める. (真の結果を [分子, 分母] の形で返す)

     :: Computes the normal form of a distributed polynomial. (The true result is returned in such a list as [numerator, denominator])

return
     dp_nf() : 分散表現多項式, dp_true_nf() : リスト

     dp_nf() : distributed polynomial, dp_true_nf() : list

indexlist
     リスト

     list

dpoly
     分散表現多項式

     distributed polynomial

dpolyarray
     配列

     array of distributed polynomial

fullreduce
     フラグ

     flag

mod
     素数

     prime

  * 分散表現多項式 DPOLY の正規形を求める.

  * 名前に weyl を含む関数はワイル代数における正規形計算を行う. 以下の説明は weyl を含むものに対しても同様に成立する.

  * dp_nf_mod(), dp_true_nf_mod() の入力は, dp_mod() などにより, 有限体上の分散表現多項式になっていなければならない.

  * 結果に有理数, 有理式が含まれるのを避けるため, dp_nf() は真の値の定数倍の値を返す. 有理式係数の場合の dp_nf_mod() も同様であるが, 係数体が有限体の場合 dp_nf_mod() は真の値を返す.

  * dp_true_nf(), dp_true_nf_mod() は, [NM,DN] なる形のリストを返す. ただし, NM は係数に分数, 有理式を含まない分散表現多項式, DN は数または多項式で NM/DN が真の値となる.

  * DPOLYARRAY は分散表現多項式を要素とするベクトル, INDEXLIST は正規化計算に用いる DPOLYARRAY の要素のインデックスのリスト.

  * FULLREDUCE が 0 でないとき全ての項に対して簡約を行う. FULLREDUCE が 0 のとき頭項のみに対して簡約を行う.

  * INDEXLIST で指定された多項式は, 前の方のものが優先的に使われる.

  * 一般には INDEXLIST の与え方により函数の値は異なる可能性があるが, グレブナ基底に対しては一意的に定まる.

  * 分散表現でない固定された多項式集合による正規形を多数求める必要がある場合に便利である. 単一の演算に関しては, p_nf, p_true_nf を用いるとよい.

  * Computes the normal form of a distributed polynomial.

  * Functions whose name contain weyl compute normal forms in Weyl algebra. The description below also applies to the functions for Weyl algebra.

  * dp_nf_mod() and dp_true_nf_mod() require distributed polynomials with coefficients in a finite field as arguments.

  * The result of dp_nf() may be multiplied by a constant in the ground field in order to make the result integral. The same is true for dp_nf_mod(), but it returns the true normal form if the ground field is a finite field.

  * dp_true_nf() and dp_true_nf_mod() return such a list as [NM,DN]. Here NM is a distributed polynomial whose coefficients are integral in the ground field, DN is an integral element in the ground field and NM/DN is the true normal form.

  * DPOLYARRAY is a vector whose components are distributed polynomials and INDEXLIST is a list of indices which is used for the normal form computation.

  * When argument FULLREDUCE has non-zero value, all terms are reduced. When it has value 0, only the head term is reduced.

  * As for the polynomials specified by INDEXLIST, one specified by an index placed at the preceding position has priority to be selected.

  * In general, the result of the function may be different depending on INDEXLIST.  However, the result is unique for Groebner bases.

  * These functions are useful when a fixed non-distributed polynomial set is used as a set of reducers to compute normal forms of many polynomials. For single computation p_nf and p_true_nf are sufficient.

     [0] load("gr")$
     [64] load("katsura")$
     [69] K=katsura(4)$
     [70] dp_ord(2)$
     [71] V=[u0,u1,u2,u3,u4]$
     [72] DP1=newvect(length(K),map(dp_ptod,K,V))$
     [73] G=gr(K,V,2)$
     [74] DP2=newvect(length(G),map(dp_ptod,G,V))$
     [75] T=dp_ptod((u0-u1+u2-u3+u4)^2,V)$
     [76] dp_dtop(dp_nf([0,1,2,3,4],T,DP1,1),V);
     u4^2+(6*u3+2*u2+6*u1-2)*u4+9*u3^2+(6*u2+18*u1-6)*u3+u2^2
     +(6*u1-2)*u2+9*u1^2-6*u1+1
     [77] dp_dtop(dp_nf([4,3,2,1,0],T,DP1,1),V);
     -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
     [78] dp_dtop(dp_nf([0,1,2,3,4],T,DP2,1),V);
     -11380879768451657780886122972730785203470970010204714556333530492210
     456775930005716505560062087150928400876150217079820311439477560587583
     488*u4^15+...
     [79] dp_dtop(dp_nf([4,3,2,1,0],T,DP2,1),V);
     -11380879768451657780886122972730785203470970010204714556333530492210
     456775930005716505560062087150928400876150217079820311439477560587583
     488*u4^15+...
     [80] @78==@79;
     1

参照

References
     dp_dtop, dp_ord, dp_mod dp_rat, p_nf p_nf_mod p_true_nf p_true_nf_mod.

dp_hm, dp_ht, dp_hc, dp_rest
----------------------------

dp_hm(DPOLY)
     :: 頭単項式を取り出す.

     :: Gets the head monomial.

dp_ht(DPOLY)
     :: 頭項を取り出す.

     :: Gets the head term.

dp_hc(DPOLY)
     :: 頭係数を取り出す.

     :: Gets the head coefficient.

dp_rest(DPOLY)
     :: 頭単項式を取り除いた残りを返す.

     :: Gets the remainder of the polynomial where the head monomial is removed.

return
     dp_hm(), dp_ht(), dp_rest() : 分散表現多項式, dp_hc() : 数または多項式

dpoly
     分散表現多項式

return
     dp_hm(), dp_ht(), dp_rest() : distributed polynomial dp_hc() : number or polynomial

dpoly
     distributed polynomial

  * これらは, 分散表現多項式の各部分を取り出すための函数である.

  * 分散表現多項式 P に対し次が成り立つ.

  * These are used to get various parts of a distributed polynomial.

  * The next equations hold for a distributed polynomial P.

     P = dp_hm(P) + dp_rest(P)

     dp_hm(P) = dp_hc(P) dp_ht(P)

     [87] dp_ord(0)$
     [88] X=ptozp((a46^2+7/10*a46+7/48)*u3^4-50/27*a46^2-35/27*a46-49/216)$
     [89] T=dp_ptod(X,[u3,u4,a46])$
     [90] dp_hm(T);
     (2160)*<<4,0,2>>
     [91] dp_ht(T);
     (1)*<<4,0,2>>
     [92] dp_hc(T);
     2160
     [93] dp_rest(T);
     (1512)*<<4,0,1>>+(315)*<<4,0,0>>+(-4000)*<<0,0,2>>+(-2800)*<<0,0,1>>
     +(-490)*<<0,0,0>>

dp_td, dp_sugar
---------------

dp_td(DPOLY)
     :: 頭項の全次数を返す.

     :: Gets the total degree of the head term.

dp_sugar(DPOLY)
     :: 多項式の sugar を返す.

     :: Gets the sugar of a polynomial.

return
     自然数

     non-negative integer

dpoly
     分散表現多項式

     distributed polynomial

onoff
     フラグ

     flag

  * dp_td() は, 頭項の全次数, すなわち各変数の指数の和を返す.

  * 分散表現多項式が生成されると, sugar と呼ばれるある整数が付与される. この値は 仮想的に斉次化して計算した場合に結果が持つ全次数の値となる.

  * sugar は, グレブナ基底計算における正規化対の選択のストラテジを決定するための重要な指針となる.

  * Function dp_td() returns the total degree of the head term, i.e., the sum of all exponent of variables in that term.

  * Upon creation of a distributed polynomial, an integer called sugar is associated.  This value is the total degree of the virtually homogenized one of the original polynomial.

  * The quantity sugar is an important guide to determine the selection strategy of critical pairs in Groebner basis computation.

     [74] dp_ord(0)$
     [75] X=<<1,2>>+<<0,1>>$
     [76] Y=<<1,2>>+<<1,0>>$
     [77] Z=X-Y;
     (-1)*<<1,0>>+(1)*<<0,1>>
     [78] dp_sugar(T);
     3

dp_lcm
------

dp_lcm(DPOLY1,DPOLY2)
     :: 最小公倍項を返す.

     :: Returns the least common multiple of the head terms of the given two polynomials.

return
     分散表現多項式

     distributed polynomial

dpoly1  dpoly2
     分散表現多項式

     distributed polynomial

  * それぞれの引数の頭項の最小公倍項を返す. 係数は 1 である.

  * Returns the least common multiple of the head terms of the given two polynomials, where coefficient is always set to 1.

     [100] dp_lcm(<<1,2,3,4,5>>,<<5,4,3,2,1>>);
     (1)*<<5,4,3,4,5>>

参照

References
     p_nf p_nf_mod p_true_nf p_true_nf_mod.

dp_redble
---------

dp_redble(DPOLY1,DPOLY2)
     :: 頭項どうしが整除可能かどうか調べる.

     :: Checks whether one head term is divisible by the other head term.

return
     整数

     integer

dpoly1  dpoly2
     分散表現多項式

     distributed polynomial

  * DPOLY1 の頭項が DPOLY2 の頭項で割り切れれば 1, 割り切れなければ 0 を返す.

  * 多項式の簡約を行う際, どの項を簡約できるかを探すのに用いる.

  * Returns 1 if the head term of DPOLY2 divides the head term of DPOLY1; otherwise 0.

  * Used for finding candidate terms at reduction of polynomials.

     [148] C;
     (1)*<<1,1,1,0,0>>+(1)*<<0,1,1,1,0>>+(1)*<<1,1,0,0,1>>+(1)*<<1,0,0,1,1>>
     [149] T;
     (3)*<<2,1,0,0,0>>+(3)*<<1,2,0,0,0>>+(1)*<<0,3,0,0,0>>+(6)*<<1,1,1,0,0>>
     [150] for ( ; T; T = dp_rest(T)) print(dp_redble(T,C));
     0
     0
     0
     1

参照

References
     dp_red dp_red_mod.

dp_subd
-------

dp_subd(DPOLY1,DPOLY2)
     :: 頭項の商単項式を返す.

     :: Returns the quotient monomial of the head terms.

return
     分散表現多項式

     distributed polynomial

dpoly1  dpoly2
     分散表現多項式

     distributed polynomial

  * dp_ht(DPOLY1)/dp_ht(DPOLY2) を求める. 結果の係数は 1 である.

  * 割り切れることがあらかじめわかっている必要がある.

  * Gets dp_ht(DPOLY1)/dp_ht(DPOLY2). The coefficient of the result is always set to 1.

  * Divisibility assumed.

     [162] dp_subd(<<1,2,3,4,5>>,<<1,1,2,3,4>>);
     (1)*<<0,1,1,1,1>>

参照

References
     dp_red dp_red_mod.

dp_vtoe, dp_etov
----------------

dp_vtoe(VECT)
     :: 指数ベクトルを項に変換

     :: Converts an exponent vector into a term.

dp_etov(DPOLY)
     :: 頭項を指数ベクトルに変換

     :: Convert the head term of a distributed polynomial into an exponent vector.

return
     dp_vtoe : 分散表現多項式, dp_etov : ベクトル

     dp_vtoe : distributed polynomial, dp_etov : vector

vect
     ベクトル

     vector

dpoly
     分散表現多項式

     distributed polynomial

  * dp_vtoe() は, ベクトル VECT を指数ベクトルとする項を生成する.

  * dp_etov() は, 分散表現多項式 dpoly の頭項の指数ベクトルをベクトルに変換する.

  * dp_vtoe() generates a term whose exponent vector is VECT.

  * dp_etov() generates a vector which is the exponent vector of the head term of dpoly.

     [211] X=<<1,2,3>>;
     (1)*<<1,2,3>>
     [212] V=dp_etov(X);
     [ 1 2 3 ]
     [213] V[2]++$
     [214] Y=dp_vtoe(V);
     (1)*<<1,2,4>>

dp_mbase
--------

dp_mbase(DPLIST)
     :: monomial 基底の計算

     :: Computes the monomial basis

return
     分散表現多項式のリスト

     list of distributed polynomial

dplist
     分散表現多項式のリスト

     list of distributed polynomial

  * ある順序でグレブナ基底となっている多項式集合の, その順序に関する分散表現である DPLIST について, DPLIST が K[X] 中で生成するイデアル I が 0 次元の時, K 上有限次元線形空間である K[X]/I の monomial による基底を求める.

  * 得られた基底の個数が, K[X]/I の K-線形空間としての次元に等しい.

  * Assuming that DPLIST is a list of distributed polynomials which is a Groebner basis with respect to the current ordering type and that the ideal I generated by DPLIST in K[X] is zero-dimensional, this function computes the monomial basis of a finite dimenstional K-vector space K[X]/I.

  * The number of elements in the monomial basis is equal to the K-dimenstion of K[X]/I.

     [215] K=katsura(5)$
     [216] V=[u5,u4,u3,u2,u1,u0]$
     [217] G0=gr(K,V,0)$
     [218] H=map(dp_ptod,G0,V)$
     [219] map(dp_ptod,dp_mbase(H),V)$
     [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,
     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,
     u1*u2,u1^2,u4*u0,u3*u0,u2*u0,u1*u0,u0^2,u4,u3,u2,u1,u0,1]

参照

References
     gr hgr gr_mod.

dp_mag
------

dp_mag(P)
     :: 係数のビット長の和を返す

     :: Computes the sum of bit lengths of coefficients of a distributed polynomial.

return
     数

     integer

p
     分散表現多項式

     distributed polynomial

  * 分散表現多項式の係数に現れる有理数につき, その分母分子 (整数の場合は分子) のビット長の総和を返す.

  * 対象となる多項式の大きさの目安として有効である. 特に, 0 次元システムにおいては係数膨張が問題となり, 途中生成される多項式が係数膨張を起こしているかどうかの判定に役立つ.

  * dp_gr_flags() で, ShowMag, Print を on にすることにより途中生成される多項式にたいする dp_mag() の値を見ることができる.

  * This function computes the sum of bit lengths of coefficients of a distributed polynomial P. If a coefficient is non integral, the sum of bit lengths of the numerator and the denominator is taken.

  * This is a measure of the size of a polynomial. Especially for zero-dimensional system coefficient swells are often serious and the returned value is useful to detect such swells.

  * If ShowMag and Print for dp_gr_flags() are on, values of dp_mag() for intermediate basis elements are shown.

     [221] X=dp_ptod((x+2*y)^10,[x,y])$
     [222] dp_mag(X);
     115

参照

References
     dp_gr_flags dp_gr_print.

dp_red, dp_red_mod
------------------

dp_red(DPOLY1,DPOLY2,DPOLY3)

dp_red_mod(DPOLY1,DPOLY2,DPOLY3,MOD)
     :: 一回の簡約操作

     :: Single reduction operation

return
     リスト

     list

dpoly1  dpoly2  dpoly3
     分散表現多項式

     distributed polynomial

vlist
     リスト

     list

mod
     素数

     prime

  * DPOLY1 + DPOLY2 なる分散表現多項式を DPOLY3 で 1 回簡約する.

  * dp_red_mod() の入力は, 全て有限体係数に変換されている必要がある.

  * 簡約される項は DPOLY2 の頭項である. 従って, DPOLY2 の頭項が DPOLY3 の頭項で割り切れることがあらかじめわかっていなければならない.

  * 引数が整数係数の時, 簡約は, 分数が現れないよう, 整数 A, B, 項 T により A(DPOLY1 + DPOLY2)-BT DPOLY3 として計算される.

  * 結果は, [A DPOLY1,A DPOLY2 - BT DPOLY3] なるリストである.

  * Reduces a distributed polynomial, DPOLY1 + DPOLY2, by DPOLY3 for single time.

  * An input for dp_red_mod() must be converted into a distributed polynomial with coefficients in a finite field.

  * This implies that the divisibility of the head term of DPOLY2 by the head term of DPOLY3 is assumed.

  * When integral coefficients, computation is so carefully performed that no rational operations appear in the reduction procedure. It is computed for integers A and B, and a term T as: A(DPOLY1 + DPOLY2)-BT DPOLY3.

  * The result is a list [A DPOLY1,A DPOLY2 - BT DPOLY3].

     [157] D=(3)*<<2,1,0,0,0>>+(3)*<<1,2,0,0,0>>+(1)*<<0,3,0,0,0>>;
     (3)*<<2,1,0,0,0>>+(3)*<<1,2,0,0,0>>+(1)*<<0,3,0,0,0>>
     [158] R=(6)*<<1,1,1,0,0>>;
     (6)*<<1,1,1,0,0>>
     [159] C=12*<<1,1,1,0,0>>+(1)*<<0,1,1,1,0>>+(1)*<<1,1,0,0,1>>;
     (12)*<<1,1,1,0,0>>+(1)*<<0,1,1,1,0>>+(1)*<<1,1,0,0,1>>
     [160] dp_red(D,R,C);
     [(6)*<<2,1,0,0,0>>+(6)*<<1,2,0,0,0>>+(2)*<<0,3,0,0,0>>,
     (-1)*<<0,1,1,1,0>>+(-1)*<<1,1,0,0,1>>]

参照

References
     dp_mod dp_rat.

dp_sp, dp_sp_mod
----------------

dp_sp(DPOLY1,DPOLY2)

dp_sp_mod(DPOLY1,DPOLY2,MOD)
     :: S-多項式の計算

     :: Computation of an S-polynomial

return
     分散表現多項式

     distributed polynomial

dpoly1  dpoly2
     分散表現多項式

     distributed polynomial

mod
     素数

     prime

  * DPOLY1, DPOLY2 の S-多項式を計算する.

  * dp_sp_mod() の入力は, 全て有限体係数に変換されている必要がある.

  * 結果に有理数, 有理式が入るのを避けるため, 結果が定数倍, あるいは多項式倍されている可能性がある.

  * This function computes the S-polynomial of DPOLY1 and DPOLY2.

  * Inputs of dp_sp_mod() must be polynomials with coefficients in a finite field.

  * The result may be multiplied by a constant in the ground field in order to make the result integral.

     [227] X=dp_ptod(x^2*y+x*y,[x,y]);
     (1)*<<2,1>>+(1)*<<1,1>>
     [228] Y=dp_ptod(x*y^2+x*y,[x,y]);
     (1)*<<1,2>>+(1)*<<1,1>>
     [229] dp_sp(X,Y);
     (-1)*<<2,1>>+(1)*<<1,2>>

参照

References
     dp_mod dp_rat.

p_nf, p_nf_mod, p_true_nf, p_true_nf_mod
----------------------------------------

p_nf(POLY,PLIST,VLIST,ORDER)
p_nf_mod(POLY,PLIST,VLIST,ORDER,MOD)
     :: 表現多項式の正規形を求める. (結果は定数倍されている可能性あり)

     :: Computes the normal form of the given polynomial. (The result may be multiplied by a constant.)

p_true_nf(POLY,PLIST,VLIST,ORDER)
p_true_nf_mod(POLY,PLIST,VLIST,ORDER,MOD)
     :: 表現多項式の正規形を求める. (真の結果を [分子, 分母] の形で返す)

     :: Computes the normal form of the given polynomial. (The result is returned as a form of [numerator, denominator])

return
     p_nf : 多項式, p_true_nf : リスト

     p_nf : polynomial, p_true_nf : list

poly
     多項式

     polynomial

plist vlist
     リスト

     list

order
     数, リストまたは行列

     number, list or matrix

mod
     素数

     prime

  * gr で定義されている.

  * 多項式の, 多項式リストによる正規形を求める.

  * dp_nf(), dp_true_nf(), dp_nf_mod(), dp_true_nf_mod に対するインタフェースである.

  * POLY および PLIST は, 変数順序 VLIST および変数順序型 OTYPE に従って分散表現多項式に変換され, dp_nf(), dp_true_nf(), dp_nf_mod(), dp_true_nf_mod() に渡される.

  * dp_nf(), dp_true_nf(), dp_nf_mod(), dp_true_nf_mod() は FULLREDUCE が 1 で呼び出される.

  * 結果は多項式に変換されて出力される.

  * p_true_nf(), p_true_nf_mod() の出力に関しては, dp_true_nf(), dp_true_nf_mod() の項を参照.

  * Defined in the package gr.

  * Obtains the normal form of a polynomial by a polynomial list.

  * These are interfaces to dp_nf(), dp_true_nf(), dp_nf_mod(), dp_true_nf_mod

  * The polynomial POLY and the polynomials in PLIST is converted, according to the variable ordering VLIST and type of term ordering OTYPE, into their distributed polynomial counterparts and passed to dp_nf().

  * dp_nf(), dp_true_nf(), dp_nf_mod() and dp_true_nf_mod() is called with value 1 for FULLREDUCE.

  * The result is converted back into an ordinary polynomial.

  * As for p_true_nf(), p_true_nf_mod() refer to dp_true_nf() and dp_true_nf_mod().

     [79] K = katsura(5)$
     [80] V = [u5,u4,u3,u2,u1,u0]$
     [81] G = hgr(K,V,2)$
     [82] p_nf(K[1],G,V,2);
     0
     [83] L = p_true_nf(K[1]+1,G,V,2);
     [-1503...,-1503...]
     [84] L[0]/L[1];
     1

参照

References
     dp_ptod, dp_dtop, dp_ord, dp_nf dp_nf_mod dp_true_nf dp_true_nf_mod dp_weyl_nf dp_weyl_nf_mod.

p_terms
-------

p_terms(POLY,VLIST,ORDER)
     :: 多項式にあらわれる単項をリストにする.

     :: Monomials appearing in the given polynomial is collected into a list.

return
     リスト

     list

poly
     多項式

     polynomial

vlist
     リスト

     list

order
     数, リストまたは行列

     number, list or matrix

  * gr で定義されている.

  * 多項式を単項に展開した時に現れる項をリストにして返す. VLIST および ORDER により定まる項順序により, 順序の高いものがリストの先頭に来るようにソートされる.

  * グレブナ基底はしばしば係数が巨大になるため, 実際にどの項が現れているのかを見るためなどに用いる.

  * Defined in the package gr.

  * This returns a list which contains all non-zero monomials in the given polynomial.  The monomials are ordered according to the current type of term ordering and VLIST.

  * Since polynomials in a Groebner base often have very large coefficients, examining a polynomial as it is may sometimes be difficult to perform. For such a case, this function enables to examine which term is really exists.

     [233] G=gr(katsura(5),[u5,u4,u3,u2,u1,u0],2)$
     [234] p_terms(G[0],[u5,u4,u3,u2,u1,u0],2);
     [u5,u0^31,u0^30,u0^29,u0^28,u0^27,u0^26,u0^25,u0^24,u0^23,u0^22,
     u0^21,u0^20,u0^19,u0^18,u0^17,u0^16,u0^15,u0^14,u0^13,u0^12,u0^11,
     u0^10,u0^9,u0^8,u0^7,u0^6,u0^5,u0^4,u0^3,u0^2,u0,1]

gb_comp
-------

gb_comp(PLIST1, PLIST2)
     :: 多項式リストが, 符号を除いて集合として等しいかどうか調べる.

     :: Checks whether two polynomial lists are equal or not as a set

return 0 または 1

return 0 or 1

plist1  plist2

  * PLIST1, PLIST2 について, 符号を除いて集合として等しいかどうか調べる.

  * 異なる方法で求めたグレブナ基底は, 基底の順序, 符号が異なる場合があり, それらが等しいかどうかを調べるために用いる.

  * This function checks whether PLIST1 and PLIST2 are equal or not as a set .

  * For the same input and the same term ordering different functions for Groebner basis computations may produce different outputs as lists. This function compares such lists whether they are equal as a generating set of an ideal.

     [243] C=cyclic(6)$
     [244] V=[c0,c1,c2,c3,c4,c5]$
     [245] G0=gr(C,V,0)$
     [246] G=tolex(G0,V,0,V)$
     [247] GG=lex_tl(C,V,0,V,0)$
     [248] gb_comp(G,GG);
     1

katsura, hkatsura, cyclic, hcyclic
----------------------------------

katsura(N)

hkatsura(N)

cyclic(N)

hcyclic(N)
     :: 多項式リストの生成

     :: Generates a polynomial list of standard benchmark.

return
     リスト

     list

n
     整数

     integer

  * katsura() は katsura, cyclic() は cyclic で定義されている.

  * グレブナ基底計算でしばしばテスト, ベンチマークに用いられる katsura, cyclic およびその斉次化を生成する.

  * cyclic は Arnborg, Lazard, Davenport などの名で呼ばれることもある.

  * Function katsura() is defined in katsura, and function cyclic() in  cyclic.

  * These functions generate a series of polynomial sets, respectively, which are often used for testing and bench marking: katsura, cyclic and their homogenized versions.

  * Polynomial set cyclic is sometimes called by other name: Arnborg, Lazard, and Davenport.

     [74] load("katsura")$
     [79] load("cyclic")$
     [89] katsura(5);
     [u0+2*u4+2*u3+2*u2+2*u1+2*u5-1,2*u4*u0-u4+2*u1*u3+u2^2+2*u5*u1,
     2*u3*u0+2*u1*u4-u3+(2*u1+2*u5)*u2,2*u2*u0+2*u2*u4+(2*u1+2*u5)*u3
     -u2+u1^2,2*u1*u0+(2*u3+2*u5)*u4+2*u2*u3+2*u1*u2-u1,
     u0^2-u0+2*u4^2+2*u3^2+2*u2^2+2*u1^2+2*u5^2]
     [90] hkatsura(5);
     [-t+u0+2*u4+2*u3+2*u2+2*u1+2*u5,
     -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,
     -u2*t+2*u2*u0+2*u2*u4+(2*u1+2*u5)*u3+u1^2,
     -u1*t+2*u1*u0+(2*u3+2*u5)*u4+2*u2*u3+2*u1*u2,
     -u0*t+u0^2+2*u4^2+2*u3^2+2*u2^2+2*u1^2+2*u5^2]
     [91] cyclic(6);
     [c5*c4*c3*c2*c1*c0-1,
     ((((c4+c5)*c3+c5*c4)*c2+c5*c4*c3)*c1+c5*c4*c3*c2)*c0+c5*c4*c3*c2*c1,
     (((c3+c5)*c2+c5*c4)*c1+c5*c4*c3)*c0+c4*c3*c2*c1+c5*c4*c3*c2,
     ((c2+c5)*c1+c5*c4)*c0+c3*c2*c1+c4*c3*c2+c5*c4*c3,
     (c1+c5)*c0+c2*c1+c3*c2+c4*c3+c5*c4,c0+c1+c2+c3+c4+c5]
     [92] hcyclic(6);
     [-c^6+c5*c4*c3*c2*c1*c0,
     ((((c4+c5)*c3+c5*c4)*c2+c5*c4*c3)*c1+c5*c4*c3*c2)*c0+c5*c4*c3*c2*c1,
     (((c3+c5)*c2+c5*c4)*c1+c5*c4*c3)*c0+c4*c3*c2*c1+c5*c4*c3*c2,
     ((c2+c5)*c1+c5*c4)*c0+c3*c2*c1+c4*c3*c2+c5*c4*c3,
     (c1+c5)*c0+c2*c1+c3*c2+c4*c3+c5*c4,c0+c1+c2+c3+c4+c5]

参照

References
     dp_dtop.

primadec, primedec
------------------

primadec(PLIST,VLIST)

primedec(PLIST,VLIST)
     :: イデアルの分解

     :: Computes decompositions of ideals.

return
plist
     多項式リスト

     list of polynomials

vlist
     変数リスト

     list of variables

  * primadec(), primedec は primdec で定義されている.

  * primadec(), primedec() はそれぞれ有理数体上でのイデアルの準素分解, 根基の素イデアル分解を行う.

  * 引数は多項式リストおよび変数リストである. 多項式は有理数係数のみが許される.

  * primadec は [準素成分, 付属素イデアル] のリストを返す.

  * primadec は 素因子のリストを返す.

  * 結果において, 多項式リストとして表示されている各イデアルは全てグレブナ基底である. 対応する項順序は, それぞれ変数 PRIMAORD, PRIMEORD に格納されている.

  * primadec は [Shimoyama,Yokoyama] の準素分解アルゴリズムを実装している.

  * もし素因子のみを求めたいなら, primedec を使う方がよい. これは, 入力イデアルが根基イデアルでない場合に, primadec の計算に余分なコストが必要となる場合があるからである.

  * Function primadec() and primedec are defined in primdec.

  * primadec(), primedec() are the function for primary ideal decomposition and prime decomposition of the radical over the rationals respectively.

  * The arguments are a list of polynomials and a list of variables. These functions accept ideals with rational function coefficients only.

  * primadec returns the list of pair lists consisting a primary component and its associated prime.

  * primedec returns the list of prime components.

  * Each component is a Groebner basis and the corresponding term order is indicated by the global variables PRIMAORD, PRIMEORD respectively.

  * primadec implements the primary decompostion algorithm in [Shimoyama,Yokoyama].

  * If one only wants to know the prime components of an ideal, then use primedec because primadec may need additional costs if an input ideal is not radical.

     [84] load("primdec")$
     [102] primedec([p*q*x-q^2*y^2+q^2*y,-p^2*x^2+p^2*x+p*q*y,
     (q^3*y^4-2*q^3*y^3+q^3*y^2)*x-q^3*y^4+q^3*y^3,
     -q^3*y^4+2*q^3*y^3+(-q^3+p*q^2)*y^2],[p,q,x,y]);
     [[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]]
     [103] primadec([x,z*y,w*y^2,w^2*y-z^3,y^3],[x,y,z,w]);
     [[[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]]]

参照

References
     fctr sqfr, 項順序の設定.

     Setting term orderings.

primedec_mod
------------

primedec_mod(PLIST,VLIST,ORD,MOD,STRATEGY)
     :: イデアルの分解

     :: Computes decompositions of ideals over small finite fields.

return
plist
     多項式リスト

     list of polynomials

vlist
     変数リスト

     list of variables

ord
     数, リストまたは行列

     number, list or matrix

mod
     正整数

     positive integer

strategy
     整数

     integer

  * primedec_mod() は primdec_mod で定義されている. [Yokoyama] の素イデアル分解アルゴリズムを実装している.

  * primedec_mod() は有限体上でのイデアルの根基の素イデアル分解を行い, 素イデアルのリストを返す.

  * primedec_mod() は, GF(MOD) 上での分解を与える. 結果の各成分の生成元は, 整数係数多項式である.

  * 結果において, 多項式リストとして表示されている各イデアルは全て [VLIST,ORD] で指定される項順序に関するグレブナ基底である.

  * STRATEGY が 0 でないとき, incremental に component の共通部分を計算することによる early termination を行う. 一般に, イデアルの次元が高い場合に有効だが, 0 次元の場合など, 次元が小さい場合には overhead が大きい場合がある.

  * 計算途中で内部情報を見たい場合には、前もって dp_gr_print(2) を実行しておけばよい.

  * Function primedec_mod() is defined in primdec_mod and implements the prime decomposition algorithm in [Yokoyama].

  * primedec_mod() is the function for prime ideal decomposition of the radical of a polynomial ideal over small finite field, and they return a list of prime ideals, which are associated primes of the input ideal.

  * primedec_mod() gives the decomposition over GF(MOD). The generators of each resulting component consists of integral polynomials.

  * Each resulting component is a Groebner basis with respect to a term order specified by [VLIST,ORD].

  * If STRATEGY is non zero, then the early termination strategy is tried by computing the intersection of obtained components incrementally. In general, this strategy is useful when the krull dimension of the ideal is high, but it may add some overhead if the dimension is small.

  * If you want to see internal information during the computation, execute dp_gr_print(2) in advance.

     [0] load("primdec_mod")$
     [246] PP444=[x^8+x^2+t,y^8+y^2+t,z^8+z^2+t]$
     [247] primedec_mod(PP444,[x,y,z,t],0,2,1);
     [[y+z,x+z,z^8+z^2+t],[x+y,y^2+y+z^2+z+1,z^8+z^2+t],
     [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],
     [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],
     [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],
     [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]]
     [248]

参照

References
     modfctr, 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, 項順序の設定.

     Setting term orderings,

     dp_gr_flags dp_gr_print.

bfunction, bfct, generic_bfct, ann, ann0
----------------------------------------

bfunction(F)
bfct(F)
generic_bfct(PLIST,VLIST,DVLIST,WEIGHT)
     :: B 関数の計算

     :: Computes the global B function of a polynomial or an ideal

ann(F)
ann0(F)
     :: 多項式のベキの annihilator の計算

     :: Computes the annihilator of a power of polynomial

return
     多項式またはリスト

     polynomial or list

f
     多項式

     polynomial

plist
     多項式リスト

     list of polynomials

vlist dvlist
     変数リスト

     list of variables

  * bfct で定義されている.

  * bfunction(F), bfct(F) は多項式 F の global B 関数 b(s) を計算する. b(s) は, Weyl 代数 D 上の一変数多項式環 D[s] の元 P(x,s) が存在して, P(x,s)f^(s+1)=b(s)f^s を満たすような多項式 b(s) の中で, 次数が最も低いものである.

  * generic_bfct(F,VLIST,DVLIST,WEIGHT) は, PLIST で生成される D の左イデアル I の, ウェイト WEIGHT に関する global B 関数を計算する. VLIST は x-変数, VLIST は対応する D-変数を順に並べる.

  * bfunction と bfct では用いているアルゴリズムが異なる. どちらが高速かは入力による.

  * ann(F) は, F^s の annihilator ideal の生成系を返す. ann(F) は, [A,LIST] なるリストを返す. ここで, A は F の B 関数の最小整数根, LIST は ann(F) の結果の s$ に, A を代入したものである.

  * 詳細については, [Saito,Sturmfels,Takayama] を見よ.

  * These functions are defined in bfct.

  * bfunction(F) and bfct(F) compute the global B-function b(s) of a polynomial F. b(s) is a polynomial of the minimal degree such that there exists P(x,s) in D[s], which is a polynomial ring over Weyl algebra D, and P(x,s)f^(s+1)=b(s)f^s holds.

  * generic_bfct(F,VLIST,DVLIST,WEIGHT) computes the global B-function of a left ideal I in D generated by PLIST, with respect to WEIGHT. VLIST is the list of x-variables, VLIST is the list of corresponding D-variables.

  * bfunction(F) and bfct(F) implement different algorithms and the efficiency depends on inputs.

  * ann(F) returns the generator set of the annihilator ideal of F^s. ann(F) returns a list [A,LIST], where A is the minimal integral root of the global B-function of F, and LIST is a list of polynomials obtained by substituting s in ann(F) with A.

  * See [Saito,Sturmfels,Takayama] for the details.

     [0] load("bfct")$
     [216] bfunction(x^3+y^3+z^3+x^2*y^2*z^2+x*y*z);
     -9*s^5-63*s^4-173*s^3-233*s^2-154*s-40
     [217] fctr(@);
     [[-1,1],[s+2,1],[3*s+4,1],[3*s+5,1],[s+1,2]]
     [218] F = [4*x^3*dt+y*z*dt+dx,x*z*dt+4*y^3*dt+dy,
     x*y*dt+5*z^4*dt+dz,-x^4-z*y*x-y^4-z^5+t]$
     [219] generic_bfct(F,[t,z,y,x],[dt,dz,dy,dx],[1,0,0,0]);
     20000*s^10-70000*s^9+101750*s^8-79375*s^7+35768*s^6-9277*s^5
     +1278*s^4-72*s^3
     [220] P=x^3-y^2$
     [221] ann(P);
     [2*dy*x+3*dx*y^2,-3*dx*x-2*dy*y+6*s]
     [222] ann0(P);
     [-1,[2*dy*x+3*dx*y^2,-3*dx*x-2*dy*y-6]]

参照

References

     Weyl 代数.

     Weyl algebra.