論文の概要: Learning to Compute Gr\"obner Bases

• arxiv url: http://arxiv.org/abs/2311.12904v2
• Date: Tue, 13 Feb 2024 01:30:19 GMT
• ステータス: 処理完了
• システム内更新日: 2024-02-14 19:07:27.048836
• Title: Learning to Compute Gr\"obner Bases
• Title（参考訳）: gr\"obner基底を計算するための学習
• Authors: Hiroshi Kera, Yuki Ishihara, Yuta Kambe, Tristan Vaccon, Kazuhiro Yokoyama
• Abstract要約: Gr"obnerベースは、非常に高価な計算コストで知られている。 本稿では,トランスフォーマーのトレーニングにより,初めて複雑性を実現する。
• 参考スコア（独自算出の注目度）: 4.0998481751764
• License: http://creativecommons.org/licenses/by/4.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, raising two novel algebraic problems: random generation of Gr\"obner bases and the transformation of them into non-Gr\"obner polynomial systems, termed as backward Gr\"obner problem. We resolve these problems with zero-dimensional radical ideals, the ideals appearing in various applications. The experiments show that the proposed dataset generation method is three to six 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つの新しい代数的問題を引き起こす。 我々は、これらの問題をゼロ次元根基イデアル(様々な応用に現れるイデアル)で解決する。 実験の結果,提案手法はnaiveアプローチよりも3桁から6桁高速であり,gr\"obner基底の計算における重要な課題を克服していることがわかった。

関連論文リスト

• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。 この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
  論文  参考訳（メタデータ） (2024-08-14T19:04:13Z)
• 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)
• Online Stability Improvement of Groebner Basis Solvers using Deep Learning [29.805408457645886]
  異なる変数や単項順序が異なる消去テンプレートにつながることを示す。 次に、元の係数の集合が、優れた解法の選択を訓練するのに十分な情報を含むことを証明した。
  論文  参考訳（メタデータ） (2024-01-17T16:51:28Z)
• Predicting the cardinality and maximum degree of a reduced Gr\"obner basis [0.0]
  ニューラルネットワーク回帰モデルを構築し、二項イデアルの「オブナーベース」の複雑性の鍵となる指標を予測する。 この研究は、Gr"オブザーバ計算によるニューラルネットワークによる予測が簡単なプロセスではない理由を説明している。
  論文  参考訳（メタデータ） (2023-02-10T16:33:58Z)
• A Strongly Polynomial Algorithm for Approximate Forster Transforms and its Application to Halfspace Learning [56.86097988183311]
  フォースター変換(フォースターりゅう、英: Forster transform)は、データセットを放射等方性位置に配置し、その性質のいくつかを維持しながら、データセットを正規化する方法である。
  論文  参考訳（メタデータ） (2022-12-06T14:32:02Z)
• Transformers Learn Shortcuts to Automata [52.015990420075944]
  低深度変換器は任意の有限状態オートマトンを計算できる。 我々は,$O(log T)$レイヤを持つ変換器が,長さ$T$の入力シーケンス上で,オートマトンを正確に再現可能であることを示す。 さらに、これらの解の脆性について検討し、潜在的な緩和を提案する。
  論文  参考訳（メタデータ） (2022-10-19T17:45:48Z)
• JiuZhang: A Chinese Pre-trained Language Model for Mathematical Problem Understanding [74.12405417718054]
  本稿では,中国初の数学的事前学習言語モデル(PLM)を提示することにより,機械の数学的知性向上を目指す。 他の標準のNLPタスクとは異なり、数学的テキストは問題文に数学的用語、記号、公式を含むため理解が難しい。 基礎課程と上級課程の両方からなる数学PLMの学習を改善するための新しいカリキュラム事前学習手法を設計する。
  論文  参考訳（メタデータ） (2022-06-13T17:03:52Z)
• Learning Polynomial Transformations [41.30404402331856]
  ガウスの高次元二次変換を学習する問題を考察する。 我々の結果はガウス分布だけでなく、任意の不変な入力分布にまで拡張される。 また、テンソル環分解の証明可能な保証を持つ最初の分解時間アルゴリズムを与える。
  論文  参考訳（メタデータ） (2022-04-08T17:59:31Z)
• Learning Algebraic Recombination for Compositional Generalization [71.78771157219428]
  合成一般化のための代数的組換え学習のためのエンドツーエンドニューラルモデルLeARを提案する。 主要な洞察は、意味解析タスクを潜在構文代数学と意味代数学の間の準同型としてモデル化することである。 2つの現実的・包括的構成一般化の実験は、我々のモデルの有効性を実証している。
  論文  参考訳（メタデータ） (2021-07-14T07:23:46Z)
• Learning a performance metric of Buchberger's algorithm [2.1485350418225244]
  Buchbergerのアルゴリズムが実行されている間に発生する加算の数を、開始入力だけで予測しようと試みる。 我々の研究は概念実証として機能し、Buchbergerのアルゴリズムの加算数を予測することは機械学習の観点からの問題であることを示した。
  論文  参考訳（メタデータ） (2021-06-07T14:57:57Z)
• 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)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。