すするすするる

主にグレブナ基底の話です。

割り算アルゴリズム　その2

プログラムからはじめるグレブナ基底

割り算アルゴリズム その2

  • 単項式を消していく事で、割り算を実現
  • 多項式の割り算は、単項式を少しずつ消していく
  • （順序が重要）

はじめに？

「割り算アルゴリズム」で一記事にしようとしていましたが、長くなってしまったので分割しました。この記事では、多項式の割り算を扱っていきます。

理論

準備（前提知識）

目標（理論）

最終的には、多項式と多項式で割り算をすることが目標です。

複雑な例への準備

もし、多項式の余り rをさらに割ることができるならば、割り算アルゴリズムはどうなるか考えます。 これは、例えば式 F = xyz を、 F3 = xy + yz と F4 = xyz + xy で割るときに重要となります。もしF3で割り切ってしまって、さらにF4で割れるなら、F4でも割る必要があります。

これを式にして表現してみます。

y = q1 \times x1 + r1

r1 = q2 \times x2 + r2

r2 = q3 \times x3 + r3

\vdots

  • y は、割られる式です。
  • q1、q2、\cdots は、商です。
  • x1、x2、\cdots は、割る式です。
  • r1、r2、\cdots は、余りです。

上の式では、1行目で計算した余り r1 がさらに割れるとします。 なので、余りをさらに割ります。また余りが割れるなら・・・という計算です。

とても頭の悪い例で同じ計算をしてみます。 y = 10 を 3、2 で割る事を考えます。

10 = 3 + 7

7 = 3 + 4

4 = 2 + 2

2 = 2 + 0

この例のように、もし余りがさらに割れるならさらに割る、ダメなら終了という流れが想像できると嬉しいです。

多項式の割り算はどうなるか（本題）

ここでようやく本題ですが、多項式と多項式で割り算することを考えます。 今までのことを使います。つまり、

  • 割るには、（次数と係数を揃えて）引いて消す操作が必要
  • 余りが出て、余りがさらに（他の式でも）割れるなら割る

つまり、多項式中の単項式を引いて消し、余りが出たら、他の単項式を引いてさらに消す。ということです。単項式を消していけば、いずれ割れなくなるはずです（※本当は停止性について考える必要があります）。

では具体的な例を考えます。 F = xyz を F3 = xy + yz、 F4 = xyz + xy で割るとします。

説明都合上F4から割ります。すなわち、 F - q1 \times F4 = r としたいです。 F = xyz、 F4 = xyz + xy なので、 q1 = 1 でそのまま xyzが消せそうです。

F - F4 = xyz - (xyz + xy) = -xy

余りの -xy はまだ割れそうです( F3 = xy + yz)。

-xy - (-1)(xy + yz) = yz

yz は割れそうにないです。ということで計算終了です。

ん？本当に計算終了なの？

F3 = xy + yz には yz が含まれるから割れる（消せる）のでは？ となります。が、消せないようです。 仮に、消したとすると、新しい式ができ、また消すことができ・・・と無限に操作できてしまいます。答えがあったとしても、答えかどうか判定もできないですし、答えに到達できるかも不明になります。

ここで、順序および単項式の大きさが重要になるはずです。あらかじめ大きさがわかっていて、大きいもので消していけば、この点が解決されるはずです（このあたりの話は、停止性に関連します。するはずです。）。

割り算結果が一意でない

先ほどの例ですが、実はF3から割ると、F4から割るときと結果が異なります。 F3で割ると、

F - z \times F3 = xyz - (xyz + yz^{2}) = -yz^{2}

となり、結果が異なります。 -yz^{2}はこれ以上F3、F4では割れません。

このように一般には複数の多項式で割ると、結果が一意に定まらないです。 この結果を一意に定めるには、F3、F4がグレブナ基底である必要があります。 また、結果を一意に定める多項式の集合がグレブナ基底です。

自信の無い事（理論）

私自身、書き出したはいいものの、よく理解できてないことです。 すなわち勉強不足な点です。

係数がなぜ重要なのか

また、このタイプのアルゴリズムでは、おそらく、係数が重要です。 というのも、係数が固定されてないと無理やり割っても何とかなるためだと思います。 上記説明のアルゴリズムでなければ、無理やり 4x^{2}/3xy = 4x/3y とかみたいに計算できてしまいます。 このとき、係数に着目すると、整数から有理数に係数が変化しています。

上記の割り算アルゴリズムなら、その心配はないはずです（整数-整数=整数となるはずです）。 なぜ係数を固定する必要があるのか？という点は理解が足りてないですが、問題設定上係数を固定することが多いように見られます。係数を固定しているならば、無理やり割る事ができない、というわけだと思います。

プログラム

今回はプログラムというより電卓です。足し算引き算して、理論の内容が実装できているように見えればOKという感じです。

次に、多項式での割り算、割る順序で結果が異なる例を計算しています。

多項式の割り算

// 割り算アルゴリズム2

print("コード見ながらの実行を推奨します。")$
print("もしくは、対話モードで実行を推奨します。")$

F1 = x*y + y*z$
F2 = x*y*z + x*y$
F  = x*y*z$

/*
// example1
 F = xyz を割る
 F1 = xy + yzから割り始める

 xyz - (w)*(xy + yz)
  [...wは適当な値、変数（つまりwは単項式）]
 w = z
 とすれば、
 xyz - (xyz + yz^2) = -yz^2
 となって、F = xyz を消せそう
 
 また、-yz^2をF1、F2で消せない。計算終了となる。
*/

R1 = F - z*F1;
// R1 = -y*z^2

/*
// example2
 同じく、F = xyz を割る
 ただし、F2 = xyz + xyから割り始める
 
 xyz - (w)*(xyz + xy)
  [...wは適当な値、変数（つまりwは単項式）]
  w = 1
  とすれば、
  xyz - (xyz + xy) = -xy
*/

R2 = F - F2;
// R2 = -xy


/*
  ここでさらに、F1 = xy + yz なので、まだ割れる
  -xy - (v)*(xy + yz)
  [...vは適当な値、変数（つまりvは単項式）]
  v = -1
  とすれば、
  -xy + xy + yz = yz
  となって、-xy が消せそう
*/

R3 = R2 - (-1)*F1;
// R3 = yz

end$