Learning to Compute Gröbner Bases

• URL: http://arxiv.org/abs/2311.12904v3
• Date: Wed, 06 Nov 2024 15:39:05 GMT
• Title: Learning to Compute Gröbner Bases
• Authors: Hiroshi Kera, Yuki Ishihara, Yuta Kambe, Tristan Vaccon, Kazuhiro Yokoyama,
• Abstract summary: This paper is the first to address the learning of Gr"obner basis with Transformers. The training requires many pairs of a system and the associated Gr"obner basis. We propose a hybrid input to handle tokens with continuity bias and avoid the growth of the vocabulary set.
• Score: 3.8214695776749013
• 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 notorious doubly exponential time complexity in the number of variables in the worst case. This paper is the first to address the learning of Gr\"obner basis computation with Transformers. 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 transforming them into non-Gr\"obner ones, termed as backward Gr\"obner problem. We resolve these problems with 0-dimensional radical ideals, the ideals appearing in various applications. Further, we propose a hybrid input embedding to handle coefficient tokens with continuity bias and avoid the growth of the vocabulary set. The experiments show that our dataset generation method is a few orders of magnitude faster than a naive approach, overcoming a crucial challenge in learning to compute Gr\"obner bases, and Gr\"obner computation is learnable in a particular class.

Related papers

• HATSolver: Learning Groebner Bases with Hierarchical Attention Transformers [0.9722250595763385]
  At NeurIPS 2024, Kera et al. introduced the use of transformers for computing Groebner bases.<n>In this paper, we improve this approach by applying Hierarchical Attention Transformers (HATs) to solve systems of equations via Groebner bases.
  arXiv  Detail & Related papers  (2025-12-09T11:34:28Z)
• Computational Algebra with Attention: Transformer Oracles for Border Basis Algorithms [22.546453748805025]
  We design and train a Transformer-based oracle that identifies and eliminates computationally expensive reduction steps.<n>We achieve substantial speedup factors of up to 3.5x compared to the base algorithm.<n>Our learning approach is data efficient, stable, and a practical enhancement to traditional computer algebra algorithms and symbolic computation.
  arXiv  Detail & Related papers  (2025-05-29T17:35:25Z)
• Geometric Generality of Transformer-Based Gröbner Basis Computation [0.0]
  In this paper, we address the computation of Gr"obner basis using Transformers. We prove that datasets generated by the previously proposed algorithm are sufficiently general. We also propose an extended and generalized algorithm to systematically construct datasets of ideal generators.
  arXiv  Detail & Related papers  (2025-04-16T20:01:00Z)
• Explicit Solution Equation for Every Combinatorial Problem via Tensor Networks: MeLoCoToN [55.2480439325792]
  We show that every computation problem has an exact explicit equation that returns its solution. We present a method to obtain an equation that solves exactly any problem, both inversion, constraint satisfaction and optimization.
  arXiv  Detail & Related papers  (2025-02-09T18:16:53Z)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP) We generalize the SDP-inspired quantum algorithm to sum-of-squares. Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
  arXiv  Detail & Related papers  (2024-08-14T19:04:13Z)
• Gröbner Basis Cryptanalysis of Ciminion and Hydra [0.0]
  quadratic system solving attacks pose a serious threat to symmetric key primitives like Ciminion and Hydra. For Ciminion we construct a degree reverse lexicographic (DRL) Gr"obner basis for the iterated model via affine transformations. For Hydra we provide a computer-aided proof in Sage that a quadratic DRL Gr"obner basis is already contained within the iterated system for the Hydra heads.
  arXiv  Detail & Related papers  (2024-05-08T13:14:04Z)
• Online Stability Improvement of Groebner Basis Solvers using Deep Learning [29.805408457645886]
  We show that different variable or monomial orderings lead to different elimination templates. We then prove that the original set of coefficients may contain sufficient information to train a selection of a good solver.
  arXiv  Detail & Related papers  (2024-01-17T16:51:28Z)
• Predicting the cardinality and maximum degree of a reduced Gr\"obner basis [0.0]
  We construct neural network regression models to predict key metrics of complexity for Gr"obner bases of binomial ideals. This work illustrates why predictions with neural networks from Gr"obner computations are not a straightforward process.
  arXiv  Detail & Related papers  (2023-02-10T16:33:58Z)
• A Strongly Polynomial Algorithm for Approximate Forster Transforms and its Application to Halfspace Learning [56.86097988183311]
  The Forster transform is a method of regularizing a dataset by placing it in em radial isotropic position while maintaining some of its essential properties.
  arXiv  Detail & Related papers  (2022-12-06T14:32:02Z)
• Transformers Learn Shortcuts to Automata [52.015990420075944]
  We find that a low-depth Transformer can represent the computations of any finite-state automaton. We show that a Transformer with $O(log T)$ layers can exactly replicate the computation of an automaton on an input sequence of length $T$. We further investigate the brittleness of these solutions and propose potential mitigations.
  arXiv  Detail & Related papers  (2022-10-19T17:45:48Z)
• JiuZhang: A Chinese Pre-trained Language Model for Mathematical Problem Understanding [74.12405417718054]
  This paper aims to advance the mathematical intelligence of machines by presenting the first Chinese mathematical pre-trained language model(PLM) Unlike other standard NLP tasks, mathematical texts are difficult to understand, since they involve mathematical terminology, symbols and formulas in the problem statement. We design a novel curriculum pre-training approach for improving the learning of mathematical PLMs, consisting of both basic and advanced courses.
  arXiv  Detail & Related papers  (2022-06-13T17:03:52Z)
• Learning Polynomial Transformations [41.30404402331856]
  We consider the problem of learning high dimensional quadratic transformations of Gaussians. Our results extend to any-invariant input distribution, not just Gaussian. We also give the first decomposition-time algorithms with provable guarantees for tensor ring decomposition.
  arXiv  Detail & Related papers  (2022-04-08T17:59:31Z)
• Learning Algebraic Recombination for Compositional Generalization [71.78771157219428]
  We propose LeAR, an end-to-end neural model to learn algebraic recombination for compositional generalization. Key insight is to model the semantic parsing task as a homomorphism between a latent syntactic algebra and a semantic algebra. Experiments on two realistic and comprehensive compositional generalization demonstrate the effectiveness of our model.
  arXiv  Detail & Related papers  (2021-07-14T07:23:46Z)
• Learning a performance metric of Buchberger's algorithm [2.1485350418225244]
  We try to predict, using just the starting input, the number of additions that take place during one of Buchberger's algorithm runs. Our work serves as a proof of concept, demonstrating that predicting the number of additions in Buchberger's algorithm is a problem from the point of machine learning.
  arXiv  Detail & Related papers  (2021-06-07T14:57:57Z)
• Recognizing and Verifying Mathematical Equations using Multiplicative Differential Neural Units [86.9207811656179]
  We show that memory-augmented neural networks (NNs) can achieve higher-order, memory-augmented extrapolation, stable performance, and faster convergence. Our models achieve a 1.53% average improvement over current state-of-the-art methods in equation verification and achieve a 2.22% Top-1 average accuracy and 2.96% Top-5 average accuracy for equation completion.
  arXiv  Detail & Related papers  (2021-04-07T03:50:11Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.