Learning to Compute Gröbner Bases

Hiroshi Kera, Yuki Ishihara, Tristan Vaccon

arXiv · PDF · Open in the Atlas

Code that ran

We lifted 18 functions out of this paper's own repositories and ran 12 of them in a sandbox. "Ran" means the function executed on a synthesized input and returned a value. It is not a reproduction of the paper's results.

Repositories linked to this paper

• hiroshikera/transformer-groebner — marked official in Papers with Code; named in the paper
• HiroshiKERA/calt
• HiroshiKERA/transformer-groebner

Some links come from the archived Papers with Code dataset (CC BY-SA 4.0): attribution and licence.

Abstract

Solving a polynomial system, or computing an associated Gröbner 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öbner basis computation with Transformers. The training requires many pairs of a polynomial system and the associated Gröbner basis, raising two novel algebraic problems: random generation of Gröbner bases and transforming them into non-Gröbner ones, termed as backward Gröbner 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öbner bases, and Gröbner computation is learnable in a particular class. algebraic constraints. Notably, the form of Gröbner bases is suited for finding solutions and allows parametric coefficients, and thus, it is vital to make Gröbner basis computation efficient and practical in applications. Following the definition of Gröbner bases in (Buchberger, 1965), the original algorithm to compute them can be presented as (i) create potential new leading terms by constructing S-polynomials, (ii) reduce them either to zero or to new polynomials for the Gröbner basis, and (iii) repeat until no new S-polynomials can be constructed. Plenty of work has been developed to surpass this algorithm. There are four main strategies: (a) avoiding unnecessary S-polynomials based on the F5 algorithm and the more general signature-based algorithms (Faugère, 2002;Bardet et al., 2015). Machine learning appeared for this task in (Peifer et al., 2020). (b) More efficient reduction using efficient linear algebraic computations using (Faugère, 1999) and the very recent GPU-using (Berthomieu et al., 2023). (c) Performing modular computations, following (Arnold, 2003;Noro and Yokoyama, 2018), to prevent coefficient growth during the computation. (d) Using the structure of the ideal, e.g., (Faugère et al., 1993;Berthomieu et al., 2022) for change of term ordering for 0-dimensional ideals or (Traverso, 1997) when the Hilbert function is known. In this study, we present the fifth strategy: (e) Gröbner basis computation fully via learning without specifying any mathematical procedures. Transformers for mathematics. Recent studies have revealed that Transformers can be used for mathematical reasoning and symbolic computation. The training only requires samples (i.e., problem-solution pairs), and no explicit mathematical procedures need to be specified. In (Lample and Charton, 2020), the first study that uses Transformers for mathematical problems is presented. It showed that Transformers can learn symbolic integration and differential equation solving with training with sufficiently many and diverse samples. Since then, Transformers have been applied to checking local stability and controllability of differential equations (

For agents

The same record, over MCP at https://syntology.ai/mcp:

get_harvested_code_for_paper("2311.12904")
get_code_for_paper("2311.12904")
have("2311.12904")

Connect an agent — have() is free.