割り算アルゴリズム その2
割り算アルゴリズム その2
- 単項式を消していく事で、割り算を実現
- 多項式の割り算は、単項式を少しずつ消していく
- (順序が重要)
はじめに?
「割り算アルゴリズム」で一記事にしようとしていましたが、長くなってしまったので分割しました。この記事では、多項式の割り算を扱っていきます。
理論
準備(前提知識)
目標(理論)
複雑な例への準備
もし、多項式の余りをさらに割ることができるならば、割り算アルゴリズムはどうなるか考えます。 これは、例えば式 を、 と で割るときに重要となります。もしF3で割り切ってしまって、さらにF4で割れるなら、F4でも割る必要があります。
これを式にして表現してみます。
- は、割られる式です。
- は、商です。
- は、割る式です。
- は、余りです。
上の式では、1行目で計算した余り がさらに割れるとします。 なので、余りをさらに割ります。また余りが割れるなら・・・という計算です。
とても頭の悪い例で同じ計算をしてみます。 を で割る事を考えます。
この例のように、もし余りがさらに割れるならさらに割る、ダメなら終了という流れが想像できると嬉しいです。
多項式の割り算はどうなるか(本題)
ここでようやく本題ですが、多項式と多項式で割り算することを考えます。 今までのことを使います。つまり、
- 割るには、(次数と係数を揃えて)引いて消す操作が必要
- 余りが出て、余りがさらに(他の式でも)割れるなら割る
つまり、多項式中の単項式を引いて消し、余りが出たら、他の単項式を引いてさらに消す。ということです。単項式を消していけば、いずれ割れなくなるはずです(※本当は停止性について考える必要があります)。
では具体的な例を考えます。 を で割るとします。
説明都合上F4から割ります。すなわち、 としたいです。 なので、 でそのままが消せそうです。
余りの はまだ割れそうです()。
は割れそうにないです。ということで計算終了です。
ん?本当に計算終了なの?
には が含まれるから割れる(消せる)のでは? となります。が、消せないようです。 仮に、消したとすると、新しい式ができ、また消すことができ・・・と無限に操作できてしまいます。答えがあったとしても、答えかどうか判定もできないですし、答えに到達できるかも不明になります。
ここで、順序および単項式の大きさが重要になるはずです。あらかじめ大きさがわかっていて、大きいもので消していけば、この点が解決されるはずです(このあたりの話は、停止性に関連します。するはずです。)。
割り算結果が一意でない
先ほどの例ですが、実はF3から割ると、F4から割るときと結果が異なります。 F3で割ると、
となり、結果が異なります。はこれ以上F3、F4では割れません。
このように一般には複数の多項式で割ると、結果が一意に定まらないです。 この結果を一意に定めるには、F3、F4がグレブナ基底である必要があります。 また、結果を一意に定める多項式の集合がグレブナ基底です。
自信の無い事(理論)
私自身、書き出したはいいものの、よく理解できてないことです。 すなわち勉強不足な点です。
係数がなぜ重要なのか
また、このタイプのアルゴリズムでは、おそらく、係数が重要です。 というのも、係数が固定されてないと無理やり割っても何とかなるためだと思います。 上記説明のアルゴリズムでなければ、無理やり とかみたいに計算できてしまいます。 このとき、係数に着目すると、整数から有理数に係数が変化しています。
上記の割り算アルゴリズムなら、その心配はないはずです(整数-整数=整数となるはずです)。 なぜ係数を固定する必要があるのか?という点は理解が足りてないですが、問題設定上係数を固定することが多いように見られます。係数を固定しているならば、無理やり割る事ができない、というわけだと思います。
プログラム
今回はプログラムというより電卓です。足し算引き算して、理論の内容が実装できているように見えれば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$
割り算アルゴリズム その1
割り算アルゴリズム その1
- 単項式を消していく事で、割り算を実現
- 多項式の割り算は、単項式を少しずつ消していく
- (順序が重要)
はじめに?
「割り算アルゴリズム」で一記事にしようとしていましたが、長くなってしまったので分割しました。この記事では、割り算アルゴリズムの簡単な例を扱っていきます。後述の目標である多項式の割り算は次の記事に書きます。
理論
準備(前提知識)
- 単項式、多項式
- 係数
- 順序
目標(理論)
最終的には、多項式と多項式で割り算をすることが目標です。 まずは、簡単な問題から考えます。
簡単な例(理論)
簡単な問題として、単項式の割り算を考えます。 具体的には、, とし、 を考えます。
ここで扱う割り算アルゴリズムは、いわゆる/による割り算ではなく、足し算(引き算)、掛け算で計算していきます。
割り算とは何か?次の式を考えます。
- は、割られる式です。具体例ではF1に相当します。
- は、商です。
- は、割る式です。具体例ではF2に相当します。
- は、余りです。
この式に乗っ取って計算をしてみます。
答えとしては、 すなわち、答え 余り となります。
ここで、式を変形してみます。
このように考えると、 を消す操作(引き算)になります。 つまり、割り算を引き算で実行できることがわかります。 この式が、割り算アルゴリズムの基本的な考え方になります。
ではどうするか
ここまでの話から、割り算は引き算で実行できそうなことがわかりました。 では、アルゴリズムとしてどうするべきかを考えます。
引くには、
を実行すればよく、F1を消す操作がしたいというわけです。
F1を引くには、のときは、 まず、 と考えます。 これは言い換えると、F1とF2 の次数を合わせていると考えます。
そして、 でした。 これは言い換えると、F1とF2 の係数を合わせていると考えます。
つまり、引いて消す操作をするには、次数と係数を合わせてやる必要があります。
プログラム
今回はプログラムというより電卓です。足し算引き算して、理論の内容が実装できているように見えればOKという感じです。
まずは、単項式での割り算を計算しています。
単項式の割り算
// 割り算アルゴリズム print("コード見ながらの実行を推奨します。")$ print("もしくは、対話モードで実行を推奨します。")$ // example1 F1 = 3*x^2$ F2 = x$ /* 3x^2 - yx = 0 [...yは適当な値、変数(つまりyは単項式)] これを、割り切りたい! y = 3x なら割り切れる */ R1 = F1 - 3*x*F2; // R1 = 0 end$
イデアル説明
イデアルとは何か、全く数学に触れてない人間からすると、イデアルは意味不明な対象に見えます。 なんで必要なのか、いったい何なのか、どういう風に求まるのかよくわからないものだと思います。
ということで、数学よりの説明、定義を簡単に説明し、 別の説明をしてみようと思います。
理論の説明
理論の準備【蛇足】
は, をまとめたものとします。 多項式 なら変数 で作られる多項式 と考えます。 は多項式環を示します。和と積と変数、係数で定義される式すべてです。 よくある式みたいなもの([tex: x+y2] みたいな)を想定していただければいいと思います。
例えば、なら、 といった感じです。
定義
多項式環 の部分集合で、次を満たすものを のイデアル とする。 は次を満たす。、
- ならば、
- 、 ならば
と書いて、 で生成されるイデアルと呼びます。 また、多項式 を の生成元、または基底と呼びます。
説明
イデアルってなに?というと、ある式を足し算、掛け算して新たにできる式すべての集合、というイメージです。 つまり、イデアルの要素全体は、ものすごい量の式を含む集合です。
ただし、コアとなる部分は、ある式(生成元、基底)であるので、ある式が [x2 + 2x + 1] とかなら、 を代入すると、 イデアルの要素すべてが0になるはずです。
つまり大雑把に、誤解を含むかもしれない言い方をすれば、コアとなる、ある式(生成元、基底)と同等の特性を持つ式の集合と考えられます。
例えば、イデアル として、全く同じイデアル[ tex: I] を生成する別の生成元 が得られるとします(つまり )。 に対して計算することと、 に対して計算することで同じ解が得られるということです。
この別の生成元 は、グレブナ基底に相当します。変数を消去したり、連立方程式を解く、というのはこの辺りから出てくるということですね。
では、情報系よりの、別の説明を書いてみます。
イデアルとは何か(情報系むけの別説明)
イデアルって何?というと、例えばイデアルは、HTMLソースであると考えます。 イデアルは、HTMLで書かれたソースすべてです。いろんなソースがあって当然ですし、その枠で考えるとすごく広いですね。
さらに、イデアルがHTMLソースなら、基底はタグとし、文章を、任意の多項式とします。文章はタグを含む文章であってもよいとします。
HTMLならHTMLタグは共通して書かれていますし、タグと任意の文章でHTMLソースは作られています。
例えば、HTMLで文章を書くとすると、
<p>ここに文章</p> <p><a href="hogehoge.html">たとえばリンクとか!</a></p> <p><strong>文章を強調してみたり!</strong></p>
といった形で書かれますね。
「ここに文章」や「たとえばリンクとか!」、「<strong>文章を強調してみたり!</strong>
」が文章に相当します。
同じタグのところは同じ特性を持つ、と考えると、例えば <a></a>
タグなら、リンクを示します。
もっと言うなら、href というようなあらかじめ決められたパラメータを持つこともわかります。
仮に、<a></a>
タグだけ集めた集合(イデアル)を考えます。
この集合に含まれる文章はみんなリンクですし、hrefの後にURLが続きますね。
全く同じことが、イデアルでも起きる、と考えるとわかりやすいと思います。 ある生成元(基底)だけでできた集合があるなら、みんな同じ性質や、同じ操作をすることができる、ということですね。
ここで、「 タグ と 文章 で書かれたもの を集めたものが HTMLソース」であると考えます。 これを用語で置き換えるならば、「 (基底) 任意の多項式 を集めて、足し合わせたものが イデアル」です。
HTMLタグで書かれている以上はみんな同じ「HTMLソース」という大まかな集合に属しますね。 同様に、生成元(基底)で作られる以上は、「イデアル」という大まかな集合に属す、という感じです。
対比してまとめてみる
「 基底 * 任意の多項式 を足し合わせたものが イデアル」=「 タグ と 文章で書かれたコード を集めたものが HTMLソース」
ということで、結構強引でしたが、なんとなくイデアルが何か、イデアルを考えると何が起きるか、 がわかって頂けるとうれしいです。
2017/06/29 作成 2017/11/01 ブログ移行に際して更新
単項式、多項式、イデアル
単項式、多項式、イデアル
方程式とか、中学や高校でならう変数と基本は同じです。 未知数を で置いて計算できます。
単項式
単項式を集めることで式が構成されると考えます。 単項式=最小構成、ブロックのようなものをイメージすると良いかもしれません。
単項式を構成する要素(ルール)は3つです。
- 変数
- 係数
- 掛け算(次数)
要素を一つずつみていきます。
どれも見たこと聞いたことがある内容だと思います。 教科書や参考書では、これらを明確に定義することが多いです。
ざっくりした理解で良ければ、余り意識する必要はないかもしれません。
単項式の例
一応、単項式の例を挙げます。係数は有理数、変数は です。
2x, 2/3x, 4xy, 4/5x2 y, 7/9x4 y8 z3
【蛇足】プログラムから考える(単項式)
プログラムから考えるなら、単項式は以下のような制約をもつとします。
- 変数を使える
- 整数(or 実数)を使える
- 使える演算子は, * だけ
ここでは、forとかifはとりあえず忘れましょう。使える制御文とか演算は、掛け算のみだと考えます。
当然ですが、これだけでは何もできません。 ただ、「ルールが明確に定められる。」という発想は、いろんな書物を読むうえで重要なように思います。
Asir での記述
Asirで変数を定義するには、最初が大文字であることが求められます。 一般的な言語では、最初の文字が数字だったりは不可能なのですが、Asirではさらに小文字もダメです。 関数と差別するための仕様らしいです。
後々のために、変数のリスを定義しておくと便利です。
VL = [x1,x2,x3]; // 変数のリスト T1 = x1 * x2 * x3; // 単項式 T2 = 2*x1^2*x2; end# // ファイル読み込み用
多項式
いわゆる式です。方程式とかを思い浮かべると良いかもしれません。
構成する要素(ルール)は2つです。
- 単項式
- 足し算
つまり、単項式を足し算でつなぎ合わせたものが多項式と考えます。 ブロックを足し合わせて作できるのが多項式と考えられます。
ここで初めて、和と積が扱えるようになります。 和と積が扱えると、よく知った四則演算に近くなるため、イメージしやすいと思います。
ただし、和と積=四則演算、と短絡的に考えるのは良くないです。 あくまでも、和と積が使えると考えましょう。 後々、グレブナ基底に近づくほど「割り算」の特殊さに触れることになります。
多項式の例
今回も係数は有理数で、変数は です。
3x + y, x2 y + 4y, 4/5 x6 y + 4
プログラムから考える(多項式)
プログラムから考えるなら、多項式は以下のように考えられます。
- 単項式というオブジェクトが使える
- 使える演算子は + だけ
単項式が内部で、積しか使えないオブジェクトだとすると、単項式と和しか使えないのが多項式。 積は単項式オブジェクトの内部としては存在するが、演算子として使えないと考えます。
と、書くと面倒に見えますね。 普通の方程式とかを想定していただければ大丈夫でしょう。 ただ、要素をよく観察すると、単項式を足し算で集めたものが多項式になっていて、積は単項式の一部になっているように見えます。
Asir 出の記述(多項式)
Asirでは単項式と同じく、特に準備はありません。
VL = [x1,x2,x3]; // 変数のリスト T1 = x1 * x2 * x3; // 単項式 T2 = 2*x1^2*x2; F1 = 3*T1 + T2; // 多項式 F2 = 3*x1*x2*x3 + 2*x1^2*x2; end# // ファイル読み込み用
イデアル
すごく簡素な説明でイデアルは、
多項式どうしを、和、積してできるすべての式がイデアルです。 例えばがあったとして、となんでもいい何かを足し掛けしてできるすべてがイデアルです。
これは、同じイデアルに含まれる要素が、同じ特性を持つということです。
例えば、3の倍数を考えます。 イデアルは「3の倍数」になるので、「3の倍数」という性質が変わらないということは、 3で割った余り はどの要素も同じ値になります。
もっと理想的なものを考えると、すべて 3 の和と積でできる集合を考えます。 6とか、18とかですね。 これは、3で割ると、余りは必ず0となります。 つまり、「3で割ると余りは0」という同じ性質を、6や18は共有しているということです。 このように、同じ特性をまとめることができるということですね。
もう少し拡張して、方程式で考えます。 例えば、[tex: x2 + 2x + 1] だけを和と積した集合を考えます。 これは、因数分解すると [tex: (x+1)2] ということで、が解になります。 もし、この式だけを足し掛けした集合があるなら、必ずを解に持つことが想像できますでしょうか。 つまり、「同じ解をもつ」という集合になりますね。
このように、イデアルとして考えることで、性質をより見やすく、まとめやすくしている、と思われます。
プログラムとして考える
プログラムとして考えるなら、次のような構造を持つと考えれます。
だんだん扱える範囲が広くなってきました。 なんとなくですが、ものすごく様々な多項式を書くことが可能であるように思っていただければ良いと思います。
多項式オブジェクトAとBがあるとします。ただし、メソッドやメンバなどは A!=B であるとします。 AとBだけで作るなら、メソッドはAかBのどちらかが必ず使えます。 それは、AとBを使っている限り守られるはずです。
つまり、イデアルでまとめられるなら、使えるメソッドが限定できる。と考えられます。 似たようなシステムとして、JAVAなんかは近いかもしれません。 JAVAオブジェクトは、すべてのオブジェクトがObjectクラスからできているので、同じメソッド「toString」を持ちます。 これによって、文字列への変換は非常に楽になってますね。
「同じ性質であるものをまとめる」ことが有効であることが納得していただければ嬉しいです。
VL = [x1,x2,x3]; // 変数のリスト T1 = x1 * x2 * x3; // 単項式 T2 = 2*x1^2*x2; F1 = 3*T1 + T2; // 多項式 F2 = 3*x1*x2*x3 + 2*x1^2*x2; I1 = F1*F1 + F1*F2 + F1; // イデアル I2 = F1 + F2; end# // ファイル読み込み用
メモ?雑記
ひょっとして、JAVAのObjectはイデアルなのではないだろうか? つまり、同イデアルの性質として、同じメソッドを持つ。 同じメソッドを持つオブジェクトなら、同じイデアルを生成する。
考えは似ているかもしれないが、式にできないと計算できないので、そのままは使えないですね。 説明としては、プログラムに詳しい人ならわかりやすいのかもしれないです。
2017/06/25 作成 2017/10/31 はてブロ移行に伴い更新
プログラムではじめるグレブナ基底 はじめに?
はじめに?
経緯
- 訓練されていない人間が、最初からWikipediaを見ると死ねる
- 訓練されていない人間が、最初から難しい資料や本を見ると死ねる
- 教訓:数学の基礎は重要、何事も理解には時間が必要
「数学なんてつかわないよー」とかだまされてはいけない。基礎くらいは知らないと厳しすぎる。
方針としては、理論を紹介し、プログラムを書く。という流れで、どちらかもしくは両方を読む(実行)することで、 少しでも理解を早めることができればよいと思っています。 とにかく「動くことは大正義」ということで、動かす中で理解を深めていけると良いと思っています。
内容は逐次更新予定です。わからないところは指摘あるとありがたいです。
また、数学的な厳密さは本に譲ります。これは、能力的に数学的厳密さを理解できないためです。
タイトル通り,プログラムによる計算を中心としていきます。情報系なら動くプログラムが手掛かりになる・・・かもしれません。
グレブナ基底とは何か
どういう使い方をするか、いくつか挙げてみます。
と、広い応用範囲をもつことが知られています。 工学系としてはまだ応用が少なく、現状では多項式の連立方程式の解を求める、というのが一般的でしょうか。
比較的解きやすい連立方程式を解かせたり、変数消去して計算といったような単純な使い方をすると、 計算速度がネックとなってきます。というのも、計算可能な他アルゴリズムが早いからですね。 グレブナ基底は、基本的なアルゴリズムで計算すると、計算回数が多くなりやすいです。 おそらく、工学系(暗号は除きます)で流行らない理由の一つはここにあると思います。 あとは、理解が結構大変ということだと信じたいです。
ともかく、計算してみましょう。
プログラム編
ソフトウェア,環境
プログラムで代数計算するには、専用の言語を用いる方が良いと思います。 フルスクラッチで作れないこともないですが、優秀なソフトウェアを使うほうが楽です。 無料の物も多くあるので、特に理由がなければ使うべきだと思います。
自分が調べた限りではありますが、いくつか代数計算のソフトウェアを挙げます。せっかくなので、簡単にレビューもしてみます。
- Macauley2
- 導入:〇 無料で、Linuxならインストールは楽
- 使用感:? ちゃんと使いこなせてないので不明
- Maple
- 導入:高価
- 使用感:〇 ドキュメント、関数共に豊富で使いやすい
- 備考:Mapleのドキュメントは大変わかりやすく、本でよくわからない説明とかあるとき確認するとよいと思います。
- Singular
- 導入:〇 無料で、Linuxならインストールは楽
- 使用感:〇 比較的使いやすいかと、超初心者は少し学習コスト高めかも
- Risa/Asir
- Sympy(Python)
- Sage
- MAGMA
- 導入:高価
- 使用感:? 使ったことないです
- 備考:あるセミナーではMAGMAを薦められました。もちろん使用できる環境であれば、使ってみましょう
個人的には、Sageのクラウドサービスがおすすめです。環境構築も特に必要なく、無料で使えます。 機能、使いやすさの面から見ても優秀なサービス、ソフトだと思います。
ですが、ここでは,Risa/Asir を使います。 といのも、日本語の資料が多く、やりたいことを1から実装している資料が多かったためです。 日本語の本ではもっぱらRisa/AsirかSingular、Macauley2を使ってます。自分の持つ資料では、Risa/Asirが多いと思います。 なので、敷居は低い方のソフトウェアだと思います。
しかし、自分も最初はRisa/Asirの使い方がわからず苦労しました。それでも使う理由としては。
- 使い方がわかればちゃんと使える
- グレブナ基底計算に関連する関数が多い
- インストールが楽
だからです。 と、ここまで書いておいてですが、SageもしくはSympy向けのプログラミングもしてみるべきかと思いました。 時間ができ次第作ってみます(2017/10/29)。
環境設定
グレブナ基底の計算
簡単な例として、次の計算をしてみます。
- F = x3-2xy, x2 y-2y2+x のグレブナ基底 G を計算
- G = [x-2y2,yx,x2]
// グレブナ基底の関数を読み込み load("gr")$ // 多項式 F を用意 F = [x^3-2*x*y, x^2*y-2*y^2+x]; // 変数リスト VL を用意 VL = [x, y]; // グレブナ基底 G を計算 G = gr(F, VL, 1); // ファイルから読み込むとき用 end$
実行方法(Win)
- Asir GUIを起動
- コマンドを実行
- ファイルを読み込む
- 左上のファイルマークから開く
もしくは、一行ずつ実行して良いです。短いプログラムでは、一行ずつ実行したほうが楽ですね。 また、プログラム実行後に、
G;
のように入力すると、変数に格納されている値を見ることができます。
今回は、とにかくグレブナ基底を計算してみよう。ということで、あっさり計算できました。 細かい内容については、別の回に譲ろうとおもいます。
おまけ
環境設定Linux
環境
手順 1. OpenXMのパッケージをDL + 現在(2017/06/22)のファイル名は,openxm_1.3.2-3_amd64.deb + 最新バージョンはOpenXMのパッケージ一覧を確認 1. ターミナルを開く 1. sudo dpkg install -f openxm_1.3.2-3_amd64.deb + 入らなかったら続けて sudo apt-get install -f 1. 実行は openxm -fep asir
2017/06/22 メモ書き
2017/10/29 はてなブログ移行に合わせて更新