Software in Mathematics Demonstration Track in Hakata Workshop 2020
Hakata Workshop(博多ワークショップ)~Discrete Mathematics and its Applications
九州大学 マス・フォア・インダストリ研究所
数学理論先進ソフトウェア開発室
九州大学 数理・データサイエンス教育研究センター
Software in Mathematics Demonstration Track in Hakata Workshop 2020
Hakata Workshop(博多ワークショップ)~Discrete Mathematics and its Applications
九州大学 マス・フォア・インダストリ研究所
数学理論先進ソフトウェア開発室
九州大学 数理・データサイエンス教育研究センター
グラフGにおいて，次数2の頂点を持たないspanning treeをGのHISTとよぶ．定義よりHISTはHamilton cycle(Gの全ての頂点を含むcycle)と対極の構造であることがわかる．Hamilton cycleの存在性について，Diracの定理では最小次数条件が，Oreの定理では非隣接2頂点の次数和条件がそれぞれ与えられている．一方，HISTの存在性を保証する最小次数条件は1990年にAlbertsonたちによって示されたが，同様の非隣接2頂点の次数和条件は知られていなかった．本研究では，HISTの非隣接2頂点の次数和条件を与える以下の定理が得られた．
定理.
Gをn頂点のグラフとする(nは8以上)．
Gの任意の非隣接2頂点の次数和がn-1以上であれば，GはHISTを持つ．
この発表では，上記の定理の証明の概要や最善性などを紹介する．また，7頂点以下のグラフについて，同様の次数和条件におけるHISTの存在性の特徴づけも紹介する．
3Dプリンタでは3次元の対象物を造形することが可能であり, 数学的観点では幾何学的対象の造形やグラフの可視化等を行うことができる. 九州大学の数理学府, 数理学研究院, マス・フォア・インダストリー研究所では3DプリンターGuiderを導入しており, 計算機相談員はGuiderを用いた研究に対するサポートも行っている. 本講演では3Dプリンターの利用方法を紹介するとともに, サポート業務で培った3Dプリンター利用に関連するテクニックを紹介したい. 特に, 大学や研究機関等でライセンスを購入されていることが多い数式処理システムMathematicaで作成したグラフの可視化方法を紹介する予定である. Mathematicaで作成したグラフをSTL形式に変換し, 3Dプリンタ対応のアプリケーション (今回はGuiderの付属アプリケーションFlashPrintを用いる) から拡大・縮小等の編集を行うことで、グラフを可視化できる. 一方で, 大きなモデル（例えば, 15 平方センチメートルの二変数正規分布）の作成を試みる場合には情報量が多くなってしまい, 印刷に失敗してしまったり、印刷に時間がかかってしまうといった問題も発生する. 本講演ではそうした問題を回避するためのテクニックを紹介する.
一般に, 有理数係数の多項式環上の計算で, 時間がかかる問題の１つとして「中間係数膨張」がある. 中間係数膨張とは, 入力と出力に出てくる多項式の係数が小さいのにも関わらず, 入力から出力を計算する中間過程で巨大な係数の多項式が登場してしまう現象である. この解決策の１つとして, 複数の有限体上の並列計算を利用した「Modular Techniques」という手法が研究されてきている. 本発表では, その手法を（二重）イデアル商や飽和イデアルなどの「局所化操作」に適用した例を紹介する. 局所化操作はイデアルから特定の情報のみを抽出するような操作である. これらの計算の基礎としてはグレブナー基底の理論が使われている. 実装は数式処理ソフト「Singular」上で行った. Singularは代数幾何や可換環論の計算を行うことができる著名な数式処理ソフトである. 発表者は, その組み込みライブラリmodular.libを利用して, イデアル商などへのModular Techniquesを実装した.
干渉ブラウン運動とは, 粒子が互いに影響を与えながら空間の中を動き回る現象であり, 遠距離相互作用をもつ無限次元確率微分方程式の系として構成される. 典型例としては, ランダム行列の固有値のスケール極限として現れる点過程を定常状態とするモデルが知られている. そのうち, 1次元の例としてsine（Dysonモデル）, Airy, Bessel干渉ブラウン運動, 2次元の例としてGinibre 干渉ブラウン運動が挙げられる. 長田博文氏（九大数理）の一連の研究で構築された一般論によって, ランダム行列理論に関係するこれらの干渉ブラウン運動を表す確率微分方程式の形状が明らかになり, 解の存在も示された. この発表では, 長田氏による講演でのデモンストレーションのために作成した1次元干渉ブラウン運動の図表, 及び2次元のGinibre干渉ブラウン運動の動画を紹介する.
私は大学3年次のゼミで数学の圏論を勉強してきました. その中で圏論を用いて作られたとされるプログラミング言語Haskellに興味をもち, 卒業論文として研究を続けてきました. 内容は, 圏論における圏・関手・自然変換をHaskellに相当するものは何かを考えました. 次に, Haskellが大きなデータを扱えることを使って, n次元ベクトルの演算である和・内積・スカラー倍ができるプログラムを作成しました. そして, プログラムに対象と一つの射を与えたときに圏になっているかどうかを判別するプログラムをつくりました.
スリザーリンクとは, マスごとに指定された数の辺をそのマスの周囲に引くという条件を満たしながら１つの閉路を作成するパズルである. 基本的なルールをもとにした手筋があり, それに従って辺を引き, 解くことが一般的である. しかし, スリザーリンクはNP困難であり, 問題規模が大きくなると解の導出が困難になる. 一方で, 近年フロンティア法と呼ばれる解を列挙する手法が注目を集めており, この手法を用いたスリザーリンクを解くアルゴリズムがある. このアルゴリズムでは基本ルールに基づいてマスの数字を満たす閉路の列挙を単純に行うだけで, 解くために使われている手筋を適用していない. 本研究では, この既存のアルゴリズムに対し, 複数の手筋を組み込むことにより高速化を図り, 24x14の問題について既存のものより約2倍の速さで解を導出することが可能になった.
格子上の計算問題として，最短ベクトル問題や最近ベクトル問題などが代表的である．これらの問題の計算量困難性は現代の格子暗号方式の安全性を支えている．一般に，格子を生成する基底の各ベクトルが短くかつ互いに直交に近いほど格子問題は解きやすく，このような基底に取り換える操作を格子基底簡約と呼ぶ．本発表では，元の格子上と双対格子上の基底簡約を組み合わせた自己双対型の基底簡約アルゴリズムを紹介する．特に，NTLライブラリを利用したC++言語でプログラムした．
位相的データ解析とは, トポロジーの概念を用いてデータ解析する手法の総称です. 一般のデータ解析の多くは, 解析したいデータを既知の分布に当てはめて重要な情報を抽出します. しかし, データが既知の分布に当てはめることのできない場合も数多く存在します. そこで, データが持つ「形」に着目し, 定量的にその「形」を抽出できる位相的データ解析が活躍します. 現在までの位相的データ解析は高分子タンパク質の立体構造解析などで効果を発揮することが知られています. 本発表では位相的データ解析のうち, 複体としてRips複体を用いたパーシステントホモロジー群について発表します. また, R言語による実装についても簡単に紹介いたします.
Domineeringと呼ばれる, 二人のプレイヤーが交互に手を打ち勝敗を競う組み合わせゲームが存在する. このゲームは盤面のサイズを変更しても成立し, サイズの小さな盤面であれば, 必勝となる手を打ち続けることも可能である. 今回は, 深層強化学習によるAIプレイヤーを作成し, それを様々なプレイヤーと競わせてみた結果とそのプログラムを紹介する. 盤面のサイズ変更や, 特徴ある学習相手への変更を通じてニューラルネットを用いた深層学習の性能の向上につながる特徴を探したい.
2次体の整数環上の素数の規則性をTDA(Topological Data Analysis)と呼ばれる方法で解析を行った. TDAとはデータの持つ数字の規則性ではなく, データの持つ形の規則性に焦点を当てた解析方法である. 今回はTDAの中でもパーシステントホモロジー群と言われるものとMapper解析と呼ばれるものを使用し, 2次体の整数環はガウス整数環を使用している, ガウス整数環の元を取り出すためにMatlabで条件に合うものを抽出, Excelデータに保存を行う. TDA解析にはRと呼ばれる統計分析のフリーソフトを使用した. Rには様々なパッケージがダウンロード出来, 今回行ったパーシステントホモロジー群とMapper解析のパッケージも用意されている.