Software in Mathematics Demonstration Track in Hakata Workshop 2019
Hakata Workshop(博多ワークショップ)~Discrete Mathematics and its Applications
九州大学 マス・フォア・インダストリ研究所
数学理論先進ソフトウェア開発室
九州大学 数理・データサイエンス教育研究センター
Software in Mathematics Demonstration Track in Hakata Workshop 2019
Hakata Workshop(博多ワークショップ)~Discrete Mathematics and its Applications
九州大学 マス・フォア・インダストリ研究所
数学理論先進ソフトウェア開発室
九州大学 数理・データサイエンス教育研究センター
グラフの辺に変数を対応させたキルヒホッフ多項式と呼ばれる多項式のヘシアンを計算するためにCoCalc (SageMathCloud)を使用した. キルヒホッフ多項式のヘッセ行列の成分は特定の2辺を含むspanning treeの母関数である. キルヒホッフ多項式のヘッセ行列を直接計算することは困難なので, 各変数に1を代入した値を考える. このとき, ヘッセ行列の各成分は特定の2辺を含むspanning treeの個数である. ある集合Eのランダムに選ばれる部分集合Tが, Eの任意の部分集合E'を含む確率を行列式として表せるとき, TはE上の行列式点過程であるという. Spanning treeはグラフの辺上の行列式点過程であることが知られている. これを応用して特定の2辺を含むspanning treeの個数を計算した. これによりキルヒホッフ多項式のヘッセ行列の各変数に1を代入した行列の固有値および行列式が計算機によって求められる.
In this program, we only consider finite simple graphs.An automorphism $\sigma$ of given graph $\Gamma$ is said a unique maximal fixed point automorphism (UFA) of $\Gamma$ if every automorphism fixing all fixed points of $\sigma$ is equal to $\sigma$ or the identity.If an automorphism $\sigma$ is a UFA then the order of $\sigma$ is two, i.e., $\sigma$ is an involution.So, every involution-free graph is UFA-free.An involution-free graph $\Gamma$ is said minimal involution-free if every proper induced subgraph of $\Gamma$ has an involution.In 2017, minimal involution-free graphs are completely classified.We call a UFA-free graph $\Gamma$ minimal UFA-free if every proper induced subgraph of $\Gamma$ has a UFA.We show a SageMath code for finding minimal UFA-free graphs with small order.In fact, the calculation result is the same as the classification of the minimal UFA-free graphs.
We developed a software package named DriverGenePathway in R program language, and Windows operating system. The main goal of DriverGenePathway is to identify significantly important mutation genes and gene sets (pathways) that are responsible for cancer, called driver genes and driver pathways. It provides various methods, including “preprocessing” for input raw files, and three different specific driver genes and gene sets detecting functions, i.e. “2D projection”, “sigGenes”, and “AWRMP”. Specifically, the “2D projection” function projects two mutation categories with the highest priorities into a two-dimensional space. The S score is calculated in that space to give the significance level of each gene. The “sigGenes” function can search significant genes with different hypothesis testing methods, such as binomial distribution test, beta-binomial distribution test, Fisher combined p-value test, likelihood ratio test, and convolution test. To find a driver gene set, the “AWRMP” function models an optimal submatrix function based on coverage and mutual exclusivity, which are the basic characteristics of driver pathways. Finally, the submatrix optimization problem (a quadratic programming problem) is solved by the genetic algorithm.
現実問題を数理最適化問題に落とし込むことが出来たとしても，その解探索にはしばしば大きな困難を伴う．実際の計算には膨大な時間を要したり，誤った（局所）解へ収束することすらあり得る．一方で効率的な探索法の考案については，純粋数学のみならず多分野から様々な試みが行われており，進化計算などの各分野が発展している．本研究では数理統計学における非負値行列因子分解（NMF）を用いた，多峰性を持つ目的関数の（複数の）単峰関数への分解を試みる．NMF は因子分解における因子行列の各要素に非負性を条件として課すもので，得られる解がスパースとなる傾向にあることが知られている．なお研究のアイデアは進化計算学者である高木英行（九州大芸工）氏によるものであり，先行研究における画像や音声などの分離の成功例を動機としている．多峰関数の分解の試みについて本報告では，統計分析ソフトウェアＲにおけるパッケージ「NMF」を利用した数値実験による検証結果を中心に紹介する．
正多面体を種数 g に一般化したものを一般化正多面体と呼ぶ。小島定吉氏（東京工業大学）の定義したペンタゴンなど、これまでに幾つかの例が知られ ている。本研究では、種数が小さい場合に対して、幾つかの一般化正多面体を構成した。また、正多面体は「対称性、t-design、距離集合」という「美しさ」 を計る概念が存在する。本研究では、一般化正多面体の「美しさ」を計る「仮想的対称性」という概念を定義した。それを用いて、ペ ンタゴンやそれに類する一般化正多面体の美しさを計ることができる。その研究過程で用いた、Maple を用いた t-design の計算プログラムなどを紹介する。
KEKが茨城県の後援で開発しJ-PARCユーザに配布している粉末回折パターンの解析用ソフトウェアです。具体的には、粉末回折パターンと呼ばれる実 験データから格子点間距離の情報がピーク探索によって得られるので、これを入力と して、ab-initio indexingと呼ばれる結晶格子(=3次元格子, を表現する２次形式)の 決定を行います。私は中の解析コードの手法（ピーク探索、ab-initio indexing, 観 測誤差下でのブラベー格子決定、解の一意性の判定）を開発し、数学的に得られた方 法をC++とOpenMPを用いて実装するまでを担当しました。GUIはWindows版とMac版があ ります。CONOGRAPHの方法自体は粉末以外の回折実験にも応用されています。また、 解の一意性の判定プログラムは、整数論の２次形式分野のKaplansky予想を具体的に 定式化するのにも使用されました。
線形独立やグラフを一般化した概念に、マトロイドがある。マトロイドは多くの数学概念の一般化と考えられ、マトロイドを分類することは重要な問題である。分類の手法に、マトロイド不変量であるタット多項式を用いるものがある。しかしタット多項式は完全不変量ではない。つまり、非同型マトロイドだが、タット多項式が等しいマトロイドが存在する。最近、タット多項式を一般化した高種数タット多項式が定義された。(Miezaki-Oura-Sakuma-Shinohara, 2019。)高種数タット多項式はマトロイドの完全不変量である。したがって、通常のタット多項式よりもマトロイドの分類に役立つことが期待される。本研究では種数 2,3 の高種数タット多項式の計算プログラムを、Maple で実装した。非同型マトロイドだが、タット多項式が等しいマトロイド、しかし種数 2 のタット多項式が異なる例を紹介する。
点群が与えられたときにその点群をクラスタリングする手法について発表する。入力は点群から構成されるグラフである。グラフの各頂点には実数が割り当てられており、スーパーレベルセットを考えることによりグラフに関するフィルトレーションが得られる。各レベルセットにおいて、頂点を中心とする半径δの円板を考え、円盤どうしの共通部分がある場合には頂点を辺で結ぶというルールでグラフを構成する。グラフが新たにできるときに生成、他のグラフに吸収されるときに消滅と呼ぶことにすると、各フィルトレーションにおいてグラフは生成と消滅を繰り返している。１つのグラフが生成して消滅するまでの長さを存続時間という。今回紹介するプログラムは、全てのフィルトレーションを通して、与えられた実数τ以上の存続時間を持つグラフを１つのクラスターとして返すものである。δとτの選び方によって結果が大きく異なるので、その様子についても紹介したい。
As a cross-platform programming language, JavaScript can deliver high- performance IoT implementation of post-quantum cryptography. In this study, we aim to speed up the JavaScript implementation of lattice-based cryptosystems by using parallel computing. We design the processes of multi-threaded implementation for a lattice-based key exchange protocol called "Ding Key Exchange" on a dual-core smartwatch. We use the concurrency and parallelism in HTML5 to improve the implementation performance. We also investigate the JavaScript implementation of other recent post-quantum key exchange protocols Frodo and NewHope and report the performance comparison. The result shows that our implementation runs about 30% faster compared with single-threaded execution.
超特異楕円曲線に関する同種写像問題の求解法のうち， 現在最も有効とされているものは同種写像のグラフ構造を 用いた衝突探索法を用いたアルゴリズムである。本研究では， より同種写像の代数的な性質を活用した求解アルゴリズムを 二つ提案する。一つ目は，modular多項式を用いて連立方程式を 立式し，同種写像列の途中に現れる楕円曲線のj-不変量を 計算する方法である。二つ目は，二つに分解された同種写像 それぞれの核に対応する多項式を用いて連立方程式を立式し， 同種写像列の途中に現れる楕円曲線の係数を計算する方法である。 今回は，それぞれのアルゴリズムを数式処理ソフトMagmaで実装し， 衝突探索法を用いた求解アルゴリズムとの求解時間比較を 行った結果を報告する。
A knot is an embedding of the circle $S^1$ into $\mathbb{R}^3$ and a link is a disjoint union of knots.A link $L$ is called $p$- periodic if there exists a diagram of $L$ which has $\frac{360^\circ}{p} $-rotational symmetry.The fundamental problem is then, for a given link $L$ and a number $p$, to determine whether or not $L$ is $p$-periodic.In general, it is not easy to show that a given link $L$ is $p$-periodic because we have to construct a concrete diagram which has the desired rotational symmetry.However, it is more difficult to show that a given link $L$ is not $p$-periodic because we have to prove that it cannot have a rotational symmetric diagram.Usually, it can be done by capturing the property of link invariants for $p$-periodic links.We use the quantum SU(N)-invariant (Homfly polynomial) of oriented links.We will give our theorem and computer program (SAGE, based on Python) to give a criterion to determine the non-periodicity of a link.