1 変数多項式に対する割算アルゴリズムは, initial term に注目する
ことにより多変数に拡張できる. すなわち, 多項式 のある項
が,
多項式
の initial term で割り切れるとき, 適当な単項式
を選んで
に
が現れないようにできる. この操作を
reduction と呼ぶ. reduction を繰り返して,
それ以上 reduction できない多項式を得たとき, それを割算による
剰余とする.
def multi_degree(F) { F = in(F); T = F[2]; return([deg(T,x),deg(T,y), deg(T,z),F[1]]); }
|
![]() 各変数の次数および, initial term の係数をリストに して返す |
def is_reducible(F,G) { DF = multi_degree(F); DG = multi_degree(G); if (DF[0] >= DG[0] && DF[1] >= DG[1] && DF[2] >= DG[2]) return red(DF[3]/DG[3]) *x^(DF[0]-DG[0]) *y^(DF[1]-DG[1]) *z^(DF[2]-DG[2]); else return 0; }
|
F が G で redubible でないとき (reduction できないとき)
![]() |
def division(F,G) { Q = 0; R = F; D = is_reducible(R,G); while (type(D) != 0) { Q = Q+D; R = R-D*G; D = is_reducible(R,G); } return [Q,R]; }
|
G の initial term が F の initial term を
割り切る限り, F から G の単項式倍を引いて
F initial term を消去する.
この関数の出力は, initial term が G の initial term で割り切れないことは保証される. |
いくつかの元を含む集合 G による剰余計算も可能である. どの項を reduction するかに任意性があるため, 一般には 結果は 1 通りとは限らないことに注意しておく.
プログラム
def reduction(F,G) { Rem = 0; while ( F ) { for ( U = 0, L = G; L != []; L = cdr(L) ) { Red = car(L); Mono = is_reducible(F,Red); if ( Mono != 0 ) { U = F-Mono*Red; if ( !U ) return Rem; break; } } if ( U ) F = U; else { H = in(F); Rem += H[0]; F -= H[0]; } } return Rem; }
|
G は多項式のリストである. この関数では, F の先頭項
が, G のどの要素の initial term によっても割り切れない
場合に, F から先頭項をとりはずし, Rem に追加される.
この関数の出力は, どの項も, G のどの要素の initial term
によっても割り切れないような多項式である.
実行例 [216] reduction(x^2+y^2+z^2, [x-y*z,y-z*x,z-x*y]); 2*x^2+y^2 [217] reduction(x^2+y^2+z^2, [z-x*y,y-z*x,x-y*z]); (y^2+1)*x^2+y^2この例では, G の要素の並び方により, 結果が異なっている. |