[3Win5] Poster session 3

[3Win5-15] Machine Learning for Monomial Ordering Optimization in Accelerating Gröbner Basis Computation

〇Shun Arakawa¹, Kazuhiko Kawamoto¹, Hiroshi Kera¹ (1.Chiba University)

Keywords:Gröbner basis, Transformer, Differential evolution

多項式系の特性の把握や解の導出には，解空間を変化させずに，解くことが容易な構造へ多項式系を変換する必要がある．この変換はグレブナー基底計算によって実現される．グレブナー基底計算はこれまで，代数，画像，暗号，制御，統計などの幅広い分野で利用されてきた．しかし，その計算コストは膨大であり，最悪の場合には変数の数に対して二重指数時間を要することが知られている．本研究では，グレブナー基底計算の高速化を目的として，単項式順序と変数順序の最適化に取り組んだ．単項式順序に関しては，これを規定する重み行列を差分進化アルゴリズムによって最適化する手法を提案した．この手法により得られた単項式順序は，評価データセットにおいて，経験上効率が良いとされる次数付き逆辞書式順序を上回る性能を示した．また，変数順序の最適化に関しては，次数付き逆辞書式順序での計算効率の良い変数順序を Transformer モデルに学習させた．その結果，訓練された Transformer モデルは，多項式系のみから計算効率の良い変数順序を予測できることを示した．