Learning to Compute Gröbner Bases

2023-11-21 · Hiroshi Kera, Yuki Ishihara, Yuta Kambe, Tristan Vaccon, Kazuhiro Yokoyama

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.

📄 PDF Abstract BibTeX arXiv:2311.12904

Code (2)

hiroshikera/transformer-groebner 공식 구현 pytorch

HiroshiKERA/calt

Tasks

Dataset Generation

Methods 이 논문이 사용한 방법론

Attention 설명 없음

Position-Wise Feed-Forward Layer 설명 없음

Dense Connections Dense Connections, or Fully Connected Connections, are a type of layer in a deep neural network that use a linear operation where every input is connected to every output…

Label Smoothing Label Smoothing is a regularization technique that introduces noise for the labels. This accounts for the fact that datasets may have mistakes in them, so maximizing the…

Absolute Position Encodings Absolute Position Encodings are a type of position embeddings for [Transformer-based models] where positional encodings are…

Softmax The Softmax output function transforms a previous layer's output into a vector of probabilities. It is commonly used for multiclass classification. Given an input vector $x$…

BPE Byte Pair Encoding, or BPE, is a subword segmentation algorithm that encodes rare and unknown words as sequences of subword units. The intuition is that various word…

Linear Layer A Linear Layer is a projection $\mathbf{XW + b}$.

HATSolver: Learning Groebner Bases with Hierarchical Attention Transformers

2025-12-09 · Mohamed Malhou, Ludovic Perret, Kristin Lauter arxiv

At NeurIPS 2024, Kera et al. introduced the use of transformers for computing Groebner bases, a central object in computer algebra with numerous practical applications. In this paper, we improve this approach by applying…

Beyond Grobner Bases: Basis Selection for Minimal Solvers

2018-06-01 · CVPR 2018 6 · Viktor Larsson, Magnus Oskarsson, Kalle Astrom, Alge Wallis 외

Many computer vision applications require robust estimation of the underlying geometry, in terms of camera motion and 3D structure of the scene. These robust methods often rely on running minimal solvers in a RANSAC fram…

Beyond Gröbner Bases: Basis Selection for Minimal Solvers

2018-03-12 · Viktor Larsson, Magnus Oskarsson, Kalle Åström, Alge Wallis 외

Gr\"obner Bases of Neural Ideals

2018-04-20

The brain processes information about the environment via neural codes. The neural ideal was introduced recently as an algebraic object that can be used to better understand the combinatorial structure of neural codes. E…

Form

When algebra twinks system biology: a conjecture on the structure of Gröbner bases in complex chemical reaction networks

2025-01-21 · Paola Ferrari, Sara Sommariva, Michele Piana, Federico Benvenuto 외

We address the challenge of identifying all real positive steady states in chemical reaction networks (CRNs) governed by mass-action kinetics. Traditional numerical methods often require specific initial guesses and may …