割算アルゴリズム

1 変数多項式に対する割算アルゴリズムは, initial term に注目する ことにより多変数に拡張できる. すなわち, 多項式 $f$ のある項 $t$ が, 多項式 $g$ の initial term で割り切れるとき, 適当な単項式 $m$ を選んで $f-mg$ に $t$ が現れないようにできる. この操作を reduction と呼ぶ. reduction を繰り返して, それ以上 reduction できない多項式を得たとき, それを割算による 剰余とする.

3 変数 $x,y,z$ の場合のプログラム.

def multi_degree(F) {
  F = in(F);
  T = F[2];
  return([deg(T,x),deg(T,y),
          deg(T,z),F[1]]);
}

    

$x > y > z$ なる辞書式順序での initial termを取り出す
各変数の次数および, 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 できないとき) $0$ を戻す. F が G で redubible のとき (reduction できるとき) M G が F の initial term に等しいような, M を戻す. 別の言い方をすると, in(F) = in(M) in(G) となるモノミアル M を戻す.

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 の要素の並び方により, 結果が異なっている.