論文の概要: Learning to Compute Gr\"obner Bases
- arxiv url: http://arxiv.org/abs/2311.12904v1
- Date: Tue, 21 Nov 2023 11:54:21 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-23 17:20:01.094228
- Title: Learning to Compute Gr\"obner Bases
- Title(参考訳): gr\"obner基底を計算するための学習
- Authors: Hiroshi Kera, Yuki Ishihara, Yuta Kambe, Tristan Vaccon, Kazuhiro
Yokoyama
- Abstract要約: Gr"obnerベースは、非常に高価な計算コストで知られている。
本稿では,変換器のトレーニングにより,初めてGr"オブザーバベースを実現する。
- 参考スコア(独自算出の注目度): 4.0998481751764
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Solving a polynomial system, or computing an associated Gr\"obner basis, has
been a fundamental task in computational algebra. However, it is also known for
its notoriously expensive computational cost -- doubly exponential time
complexity in the number of variables in the worst case. In this paper, we
achieve for the first time Gr\"obner basis computation through the training of
a transformer. The training requires many pairs of a polynomial system and the
associated Gr\"obner basis, thus motivating us to address two novel algebraic
problems: random generation of Gr\"obner bases and the transformation of them
into non-Gr\"obner polynomial systems, termed as \textit{backward Gr\"obner
problem}. We resolve these problems with zero-dimensional radical ideals, the
ideals appearing in various applications. The experiments show that in the
five-variate case, the proposed dataset generation method is five orders of
magnitude faster than a naive approach, overcoming a crucial challenge in
learning to compute Gr\"obner bases.
- Abstract(参考訳): 多項式系を解くこと、あるいは関連するGr\"オブナー基底を計算することは、計算代数学の基本的な課題である。
しかし、計算コストが悪名高いことでも知られており、最悪の場合の変数数の2倍の指数関数的な時間複雑性がある。
本稿では,変圧器の訓練により,初めて「オブナー基底計算」を実現する。
学習には多項式系と関連する gr\"obner 基底の多くの対が必要となるので、gr\"obner 基底のランダム生成とそれらの非gr\"obner多項式系への変換という2つの新しい代数的問題に対処する動機付けとなる。
我々は、これらの問題をゼロ次元根基イデアル(様々な応用に現れるイデアル)で解決する。
実験の結果, 5変量の場合, 提案したデータセット生成手法は, 単純アプローチよりも5桁高速であり, Gr\"オーバナーベースを計算する上で重要な課題を克服していることがわかった。
関連論文リスト
- Gröbner Basis Cryptanalysis of Ciminion and Hydra [0.0]
二次システム解決攻撃は、CiminionやHydraのような対称鍵プリミティブに対して深刻な脅威となる。
シミニオンに対しては、アフィン変換による反復モデルに対する次数逆レキシコグラフィ(DRL)Gr"オブナー基底を構築する。
Hydra に対して、Sage のコンピュータ支援による証明として、2次 DRL Gr" 基底が Hydra ヘッドの反復系にすでに含まれていることを示す。
論文 参考訳(メタデータ) (2024-05-08T13:14:04Z) - The solving degrees for computing Gröbner bases of affine semi-regular polynomial sequences [0.9208007322096533]
本研究では,アフィン半正則配列の解度とその均質化配列について検討する。
これらの結果は,Gr"オブザーバー基底の計算方法の正確性に関する数学的に厳密な証明を与えると考えられる。
論文 参考訳(メタデータ) (2024-04-04T15:35:41Z) - The Complexity of Algebraic Algorithms for LWE [0.0]
我々は、LWEシステム上でのGr"オブナー基底計算の複雑さを研究するために、Arora-Geモデルを再検討する。
我々は、Semaev & TentiのGr"obner基底アルゴリズムを有限の正則性を持つ任意の系に一般化する。
論文 参考訳(メタデータ) (2024-02-12T17:59:26Z) - Online Stability Improvement of Groebner Basis Solvers using Deep
Learning [29.805408457645886]
異なる変数や単項順序が異なる消去テンプレートにつながることを示す。
次に、元の係数の集合が、優れた解法の選択を訓練するのに十分な情報を含むことを証明した。
論文 参考訳(メタデータ) (2024-01-17T16:51:28Z) - A Strongly Polynomial Algorithm for Approximate Forster Transforms and
its Application to Halfspace Learning [56.86097988183311]
フォースター変換(フォースターりゅう、英: Forster transform)は、データセットを放射等方性位置に配置し、その性質のいくつかを維持しながら、データセットを正規化する方法である。
論文 参考訳(メタデータ) (2022-12-06T14:32:02Z) - Average-Case Complexity of Tensor Decomposition for Low-Degree
Polynomials [93.59919600451487]
多くの統計的推論タスクにおいて「統計計算ギャップ」が発生する。
1つの成分が他の成分よりもわずかに大きいランダムオーダー3分解モデルを考える。
テンソルエントリは$ll n3/2$のとき最大成分を正確に推定できるが、$rgg n3/2$のとき失敗する。
論文 参考訳(メタデータ) (2022-11-10T00:40:37Z) - Transformers Learn Shortcuts to Automata [52.015990420075944]
低深度変換器は任意の有限状態オートマトンを計算できる。
我々は,$O(log T)$レイヤを持つ変換器が,長さ$T$の入力シーケンス上で,オートマトンを正確に再現可能であることを示す。
さらに、これらの解の脆性について検討し、潜在的な緩和を提案する。
論文 参考訳(メタデータ) (2022-10-19T17:45:48Z) - Learning a performance metric of Buchberger's algorithm [2.1485350418225244]
Buchbergerのアルゴリズムが実行されている間に発生する加算の数を、開始入力だけで予測しようと試みる。
我々の研究は概念実証として機能し、Buchbergerのアルゴリズムの加算数を予測することは機械学習の観点からの問題であることを示した。
論文 参考訳(メタデータ) (2021-06-07T14:57:57Z) - A Practical Method for Constructing Equivariant Multilayer Perceptrons
for Arbitrary Matrix Groups [115.58550697886987]
行列群の同変層を解くための完全一般的なアルゴリズムを提供する。
他作品からのソリューションを特殊ケースとして回収するだけでなく、これまで取り組んだことのない複数のグループと等価な多層パーセプトロンを構築します。
提案手法は, 粒子物理学および力学系への応用により, 非同変基底線より優れる。
論文 参考訳(メタデータ) (2021-04-19T17:21:54Z) - Recognizing and Verifying Mathematical Equations using Multiplicative
Differential Neural Units [86.9207811656179]
メモリ拡張ニューラルネットワーク(NN)は、高次、メモリ拡張外挿、安定した性能、より高速な収束を実現することができることを示す。
本モデルでは,現在の手法と比較して1.53%の精度向上を達成し,2.22%のtop-1平均精度と2.96%のtop-5平均精度を達成している。
論文 参考訳(メタデータ) (2021-04-07T03:50:11Z) - On Function Approximation in Reinforcement Learning: Optimism in the
Face of Large State Spaces [208.67848059021915]
強化学習のコアにおける探索・探索トレードオフについて検討する。
特に、関数クラス $mathcalF$ の複雑さが関数の複雑さを特徴づけていることを証明する。
私たちの後悔の限界はエピソードの数とは無関係です。
論文 参考訳(メタデータ) (2020-11-09T18:32:22Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。