「数学ソフトウェア紹介」in Hakata Workshop 2013

基本情報

• 開催日時
2013-01-26(12:10~15:10)
• 開催場所
リファレンス駅東ビル セミナー室I (福岡市博多駅筑紫口より徒歩4分)
• アクセス
こちらをご覧ください
• 目的

　数学においても定理や理論をコンピュータ言語で実装する必要性が増しています. 社会への数学理論の還元だけでなく, 実装により数学理論が可視化できさらに数学理論が進化することがしばしばあるからです.

　今回の組合せセミナーでは, セミナー参加者の交流をさらに深めるために, 研究をする上で作製した数学ソフトウェアを発表・展示する機会を設けようと思います.

　「数学ソフトウェア」と聞くとMathematicaやMatlabのような完成度の高く汎用性のあるものを想像するかもしれませんが, ここではそういったものでなくてもかまいません. 著作権違反のコピーではだめですが, 新規性や独創性等も要求しません. 「○○という数学分野を研究するために, △△というコンピュータ言語でプログラムを書いてみました」や「卒論・修論を書くためにこんな数学に関するプログラムを書きました」といった軽い気持ちで書いたものでもかまいません. この企画では, 素晴らしい数学ソフトウェアを紹介するというよりは, いろんなバリエーションの数学ソフトウェアとその開発者が集まることで生まれる相乗効果を期待しています.

• 発表形式

　ポスター発表の形式です. ただし, ポスターではなくA4用紙4~5枚程度でプログラムの詳細を記載したものを用意して張っていただきます. また, 発表者にはこちらからプロジェクターを貸し出しますので, プロジェクターに自分のプログラムやその出力を映して発表してください. パワーポイント等のプレゼンテーションソフトを使いながら説明してもかまいません.

• Call for Presenters
• 会場風景
　　
　　
　
• 主催
九州大学 組合せ数学セミナー 世話人一同
九州大学 マス・フォア・インダストリ研究所 数学理論先進ソフトウェア開発室

発表者(Aグループ: 13:00 ~ 14:00)

1. 岩淵 勇樹 (面白法人カヤック)
• プログラム名: GraphiCalPad (発表資料)
• プログラムの概要:
画像処理ソフトのような操作性を求めて、テキストベースでない新たな数式処理システムを作りたい、という理念を基にこのアプリケーションを作りました。表計算やグラフとの連動で新たな操作感を創り出すことが目標です。e-Learningの補助ツールとして活用できるほか、Mathematicaなどにはない操作性で研究ツールとしても実力を発揮できると思われます。以下のURLからデモプログラムを実行できます。 http://butchi.jp/documents/graphicalpad ■使い方 1. 数値をドラッグして配置する 2. 数値を選択する 3. ボタンをクリックして計算を実行する 今後の展望としては ・関数電卓 ・数式処理 ・画像処理 ・グラフ描画 ・ビジュアルプログラミング などの機能を拡充しようと考えています。
2. 久保 浩平(九州大学理学部物理学科)
• プログラム名: 正規圧縮距離を用いたクラスタリング (発表資料) (ポスター)
• プログラムの概要:
本プログラムは、（テキスト）データの集合の分類を目的とする。テキストデータ間の類似度を正規圧縮距離を用いて定め、この距離を木距離に近似して埋め込むことで、系統樹を作成し、クラスタリングを得る。
3. 島袋 修(崇城大学 工学部)
• プログラム名: フュージョンスキームの探索 (発表資料)
• プログラムの概要:
代数計算ソフトMAGMAを用いてアソシエーションスキームの部分構造であるフュージョンスキームを探索するプログラムを作成した。アソシエーションスキームとは完全グラフの辺に色付けされた構造で、色がd種類のとき、それぞれの色によって得られる有向グラフから作られる隣接行列達と単位行列も含めて代数(隣接代数)になるときクラスdのアソシエーションスキームという。いくつかの色を同一視してアソシエーションスキームの条件を満たすときフュージョンスキームとよぶ．隣接代数が可換な場合の指標表のプログラムとそれを用いてフュージョンスキームを求めるプログラムを紹介する。また、それらに関連するアソシエーションスキームの基本的なプログラムも紹介する。 URL http://www.ed.sojo-u.ac.jp/~osamu/magma/
4. 野崎 寛(愛知教育大学)
• プログラム名: Magmaによる極大2距離集合の分類(Classification of maximal 2-distance sets by Magma) (発表資料)
• プログラムの概要:
ユークリッド空間上の有限集合において，その互いに異なる2点間の距離の種類が，2種類のものを2距離集合と呼ぶ． Lisonek(1997)は7次元以下の元の個数が最大となる2距離集合を，あるアルゴリズムを用いて分類している。 Lisonek(1997)が与えたアルゴリズムに基づき，6次元以下のユークリッド空間上の極大な2距離集合の分類を，Magmaを利用して行った． ここで2距離集合が極大であるとは，2距離集合に新たな点を，同次元の2距離集合としての性質を保ったままでは加えられないときを言う。 2距離集合の分類は，ある性質を満たすグラフの分類と同値であり，グラフや行列の組み込み関数が多数準備されているMagmaは非常に使い勝手が良い。 特に，頂点数の少ないグラフの分類はすでにMagmaに組み込まれており，アルゴリズムはそこから出発することが出来る。
5. 松下 昂平(九州大学大学院数理学府)
• プログラム名: アフィン写像を用いた補間による2次元アニメーション作成ソフトウェア (発表資料)
• プログラムの概要:
モーフィングと呼ばれる2次元アニメーションの自動生成において, 2000年に Alexaらは, As-rigid-as possible shape interpolation (ARAP) と呼ばれるアフィン写像を用いることでオブジェクトの形状をなるべく保つような補間手法を考案した. 2012年には鍛冶らによって, 指数補間を用いて, さらに回転不変性をもつようなエラー関数を導入した新しい手法が提案されている [1]. 本ソフトウェアは, これらの補間手法の特徴を解析したり, アニメーションの生成結果を確認できるようにGUI を備えたソフトウェアとして Python 言語で実現したものである. 例えば, 補間手法や使用するエラー関数を変更したり, 回転角や平行移動成分などのウェイトを設定することができ, 同じ入力データから異なった補間手法による結果を比較することができる. 共同開発者: 井慶喜（九大理）, 池田有希, 松田元輝, 濱田裕康（九大数理）, 溝口佳寛（九大IMI） [1] S. Kaji, S. Hirose, S. Sakata, Y. Mizoguchi and K. Anjyo, Mathematical Analysis on Affine Maps for 2D Shape Interpolation, Proceedings of ACM SIGGRAPH 2012 (SCA2012), pp.71-76, 2012. http://dl.acm.org/citation.cfm?id=2422368
6. 鹿間 章宏(大阪大学大学院 情報科学研究科)
• プログラム名: トーリックイデアルの二次生成判定法 (発表資料)
• プログラムの概要:
有限連結グラフから生起するトーリックイデアルが二次生成であるとき,それが二次グレブナー基底を持つか否かを判定することは一般に容易ではない. また, 二次生成であるが二次グレブナー基底を持たないようなグラフの例が既に一例知られている. それ以外にもこの性質を持つグラフが存在するかどうかという問題はとても興味深い. そこで, 頂点数が少ないものから順に, 付随するトーリックイデアルが二次生成であるようなグラフを列挙するプログラムを実装した. このプログラムは, グラフを列挙する NAUTY, サイクルやパスを列挙する cypath, 数式処理システム Macaulay2, グレブナー扇を計算する TiGERSなど, 複数の数学ソフトウェアをスクリプト言語 Ruby で統率することで実現されている. これにより, 6頂点のグラフでは既に知られている一例のみであることを示し, 更に, 7頂点のグラフについては14種類のみ存在することを示した.

発表者(Bグループ: 14:00 ~ 15:00)

1. 照本 直敏(九州大学数理学府)
• プログラム名: Q-det (発表資料)
• プログラムの概要:
本研究ではq-determinantの最小化を行うことでq-determinantの構造を解析している．しかしながら，本研究で扱っている最小化問題はよい構造を持っていないため効率的に解くことが難しい．そこで，半正定値計画緩和を適用することでその難しさを回避している．実際，半正定値計画問題に対して効率的に解くアルゴリズムとそれを実装したソフトウェアが公開されている． 本研究で開発したプログラムはMATLABで実装されており，半正定値計画問題を解くことで得られたq毎の最小値のグラフを表示する．それによりn=3,4についてのq-determinantの最小値について，いくつかの予想を得ることができた．
2. 喜友名 朝也(九州大学大学院数理学府)
• プログラム名: PARI/GPによるE_8 lattice の部分集合の生成
• プログラムの概要:
ベクトル値ジーゲル保型形式の構成法として、多重調和多項式ベクトル付テータ関数による構成法が知られている。この構成法は、行列式ウェイトが偶数でも奇数でも利用できるのでとても強力なのだが、そのフーリエ係数を具体的に計算しようとすると、even unimodular latticeといわれる特別な格子の部分集合が必要になる。今回の発表では、数式処理ソフトPARI/GPを利用したeven unimodular latticeの1つであるE_8 latticeの部分集合を生成するプログラムを紹介する。
3. 谷口哲至(松江高専数理科学科)
• プログラム名: スターコンプリメントテクニックと最小固有値が−２以上のグラフの生成 (発表資料)
• プログラムの概要:
最小固有値が−２以上のグラフの生成には、ルート系の部分集合（ノルム 2 のベクトルからなるユークリッド空間の部分集合）が用いられる。その様なグラフの隣接行列はそれらベクトルの部分集合のなす行列Dによるグラム行列で表される。グラフの最小固有値研究の場面では、こようなグラフを生成する必要に（頻繁に）駆られる。D. Cvetkovic, P. Rowlinson, S.K. Simic氏達によって、スターコンプリメントテクニックを用いた極大例外型グラフの分類が成された(cf. [1])。このテクニックを紹介する。 [1] Star complements and exceptional graphs. Linear Algebra and its Applications (2007), 423(1), 146--154.
4. ダハン　グザヴィエ(九州大学数理学研究院)
• プログラム名: MAGMAによるRamanujan graphチェッカー
• プログラムの概要:
Some families of Cayley graphs based on quaternions have led to famous graphs the "Ramanujan graphs". They have a small 2nd largest eigenvalue and have a large girth. Using octonions is a quite promising idea in order to improve the girth, but more challenging. A similar construction of Caylay graphs remains possible. However due to the non-associativity, whether the same remarkable properties hold or not is not easy to proof or disprove. In order to check this, a package in MAGMA that computes the girth and the 2nd largest eigenvalue was written. It was possible to check that the graphs based on octonions have a surprisingly small girth and have not a small 2nd eigenvalue (therefore are not Ramanujan).
5. 古川 貴司(九州大学大学院数理学府)
• プログラム名: SSD Problem (発表資料)
• プログラムの概要:
Flash SSD ( Flash Solid State Drive ) はコンピュータに用いられる補助記憶装置の一種である。SSDを使用するときはPage UpdateとGarbage Collectionの操作を行うが、本研究ではSSDモデルをMarkov Chainとして考え、定常状態における各ブロックのvalidなページの個数を考えることを目的としている。一様にデータを選択してPage Updateを行う場合については、Werner Bux,Ilias Iliadisらの先行研究があるが、その考えを拡張するため2種類の異なる確率で選択されるvalid なデータが存在するモデルをMathematicaを用い実装した。
6. 高妻倫太郎(立命館アジア太平洋大学)
• プログラム名: Truffe（トリュフ） (発表資料)
• プログラムの概要:
代数体上の楕円曲線の階数の上限を与えるセルマー群は、その計算可能性が理論的に保障されている重要な数論的対象であり、現在、代数系処理ソフトMagmaをはじめとした様々な数学ソフトウェアに計算アルゴリズムが実装されている。今回、有理数体上の位数３の有理点をもつ任意の楕円曲線に対して、論文（R.Kozuma, Rocky Mountain J. Math., Vol.40, No.4 (2010), 1227--1255.）の“公式”を応用したセルマー群の計算アルゴリズムを、コンソールアプリとしてVisual C++2010で実装した。この“公式”では、セルマー群の計算に必要となるガロアコホモロジーの局所連結準同型の像を、約４回の単純な条件分岐（数値の大小比較、剰余計算）のみで決定することが可能であり、既存のアルゴリズムを高速化すると期待される。
7. 秦攀(九州大学 マス・フォア・インダストリ研究所)
• プログラム名: 非線形時系列に対するモデル推定と選択のソフト (発表資料)
• プログラムの概要:
本ソフトは、時系列データを対象とし、統計モデルを推定と 選択するものである。MATLAB を用いて作成し、時系列モデルの推定、評価および選択の三つの部分より構成する。 時系列解析、システム制御、信号処理などの領域に適用 できる。現在、太陽風と地球磁場の相互関係に関する解 析に応用されている。
8. Kim, Kyoung-Tark(Pusan National University)
• プログラム名: Parallel mpi-c program for computation on Butson-type Hadamard matrices (発表資料)
• プログラムの概要:
Our program is written by c language with MPI(massage passing interfaces) whose purpose is to compute all possible Butson-type Hadamard matrices of given prime order. To this end, our program is executed on super computer (tatara in kyushu university). The result is that for order p less than or equal to 17, there is a unique Butson-type Hadamard matrix H(p,p), namely, the Fourier matrix of order p. We will show how this program executed and how our algorithm works.