プログラムではじめるグレブナ基底 はじめに？

はじめに?

経緯

• 訓練されていない人間が、最初からWikipediaを見ると死ねる
• 訓練されていない人間が、最初から難しい資料や本を見ると死ねる
• 教訓：数学の基礎は重要、何事も理解には時間が必要

「数学なんてつかわないよー」とかだまされてはいけない。基礎くらいは知らないと厳しすぎる。

方針としては、理論を紹介し、プログラムを書く。という流れで、どちらかもしくは両方を読む（実行）することで、 少しでも理解を早めることができればよいと思っています。 とにかく「動くことは大正義」ということで、動かす中で理解を深めていけると良いと思っています。

内容は逐次更新予定です。わからないところは指摘あるとありがたいです。

また、数学的な厳密さは本に譲ります。これは、能力的に数学的厳密さを理解できないためです。

タイトル通り，プログラムによる計算を中心としていきます。情報系なら動くプログラムが手掛かりになる・・・かもしれません。

---

グレブナ基底とは何か

どういう使い方をするか、いくつか挙げてみます。

• 変数消去
• 多項式の連立方程式の解を求める
• イデアルに関する問題（記述問題，所属問題）
• 統計
• 微分方程式?
• 整数計画問題
• 幾何学
• ロボティクス（工学的応用）

と、広い応用範囲をもつことが知られています。 工学系としてはまだ応用が少なく、現状では多項式の連立方程式の解を求める、というのが一般的でしょうか。

比較的解きやすい連立方程式を解かせたり、変数消去して計算といったような単純な使い方をすると、 計算速度がネックとなってきます。というのも、計算可能な他アルゴリズムが早いからですね。 グレブナ基底は、基本的なアルゴリズムで計算すると、計算回数が多くなりやすいです。 おそらく、工学系（暗号は除きます）で流行らない理由の一つはここにあると思います。 あとは、理解が結構大変ということだと信じたいです。

ともかく、計算してみましょう。

---

プログラム編

ソフトウェア，環境

プログラムで代数計算するには、専用の言語を用いる方が良いと思います。 フルスクラッチで作れないこともないですが、優秀なソフトウェアを使うほうが楽です。 無料の物も多くあるので、特に理由がなければ使うべきだと思います。

自分が調べた限りではありますが、いくつか代数計算のソフトウェアを挙げます。せっかくなので、簡単にレビューもしてみます。

• Macauley2
  • 導入：〇　無料で、Linuxならインストールは楽
  • 使用感：？　ちゃんと使いこなせてないので不明
• Maple
  • 導入：高価
  • 使用感：〇　ドキュメント、関数共に豊富で使いやすい
  • 備考：Mapleのドキュメントは大変わかりやすく、本でよくわからない説明とかあるとき確認するとよいと思います。
• Singular
  • 導入：〇　無料で、Linuxならインストールは楽
  • 使用感：〇　比較的使いやすいかと、超初心者は少し学習コスト高めかも
• Risa/Asir
  • 導入：〇　無料で、Windows、Linuxともにインストールは楽
  • 使用感：△　C言語がわかるなら問題なし。GUIがやや使いずらいかも？
  • 備考：ドキュメント、関数共に豊富で、たいていのグレブナ計算はこれ一つで十分です。
• Sympy(Python)
  • 導入：〇　Pythonライブラリを導入したことある人なら楽です
  • 使用感：〇　Pythonが使える人はなんら問題ありません
  • 備考：やや関数が物足りないかも？ドキュメントも英語でかつ分かりにくいかもしれません。
• Sage
  • 導入：×　無料ですが、なんだかうまく入らない印象です
  • 使用感：〇　Pythonが使える人はなんら問題ありません
  • 備考：個人的にはSympyより高機能で使いやすいです。もし使うならば、Sageのクラウドサービスがインストール不要でおすすめです（無料）。
• MAGMA
  • 導入：高価
  • 使用感：？　使ったことないです
  • 備考：あるセミナーではMAGMAを薦められました。もちろん使用できる環境であれば、使ってみましょう

個人的には、Sageのクラウドサービスがおすすめです。環境構築も特に必要なく、無料で使えます。 機能、使いやすさの面から見ても優秀なサービス、ソフトだと思います。

ですが、ここでは，Risa/Asir を使います。 といのも、日本語の資料が多く、やりたいことを1から実装している資料が多かったためです。 日本語の本ではもっぱらRisa/AsirかSingular、Macauley2を使ってます。自分の持つ資料では、Risa/Asirが多いと思います。 なので、敷居は低い方のソフトウェアだと思います。

しかし、自分も最初はRisa/Asirの使い方がわからず苦労しました。それでも使う理由としては。

• 使い方がわかればちゃんと使える
• グレブナ基底計算に関連する関数が多い
• インストールが楽

だからです。 と、ここまで書いておいてですが、SageもしくはSympy向けのプログラミングもしてみるべきかと思いました。 時間ができ次第作ってみます（2017/10/29）。

---

環境設定

• Windows
  1. 公式サイト神戸版からインストーラをDL
  2. インストーラを実行
  3. Asir GUIを実行

グレブナ基底の計算

簡単な例として、次の計算をしてみます。

• F = x³-2xy, x² y-2y²+x のグレブナ基底 G を計算
• G = [x-2y²,yx,x²]

// グレブナ基底の関数を読み込み
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)

1. Asir GUIを起動
2. コマンドを実行
3. ファイルを読み込む
4. 左上のファイルマークから開く

もしくは、一行ずつ実行して良いです。短いプログラムでは、一行ずつ実行したほうが楽ですね。 また、プログラム実行後に、

G;

のように入力すると、変数に格納されている値を見ることができます。

今回は、とにかくグレブナ基底を計算してみよう。ということで、あっさり計算できました。 細かい内容については、別の回に譲ろうとおもいます。

---

おまけ

環境設定Linux

環境

• Ubuntu 16.04
• Bash on Uuntu on Windows(Ubuntu 14.04)

手順 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 はてなブログ移行に合わせて更新