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. The experiments show that our dataset generation method is at least three 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.
(K. Yokoyama)
CEUR Workshop Proceedings
ceur-ws.org ISSN1613-0073 that Transformers can learn symbolic integration simply by observing many (d/ d , ) pairs in training.
The training samples are generated by first randomly generating and computing its derivative d/ d and/or by the reverse process.
However, a crucial challenge in the learning of Gröbner basis computation is that it is mathematically unknown how to eficiently generate many (non-Gröbner set, Gröbner basis) pairs. We need an eficient backward approach (i.e., solution-to-problem computation) because, as discussed above, the forward approach (i.e., problem-to-solution computation) is prohibitively expensive. To this end, we frame two problems: (i) a random generation of Gröbner bases and (ii) a backward transformation from a Gröbner basis to an associated non-Gröbner set. To our knowledge, neither of them has been addressed in the study of Gröbner bases because of the lack of motivations; all the eforts have been dedicated to the forward computation from a non-Gröbner set to Gröbner basis.
Tackling aforementioned two unexplored algebraic problems, we investigates the first learning approach to the Gröbner computation using Transformers and experimentally show its learnability uncovered two unexplored algebraic problems in the 0-dimensional case. Our experiments show that the proposed dataset generation is highly eficient and faster than a baseline method by three or four orders of magnitude. Further, we observe a learnability gap between polynomials on finite fields and infinite fields while predicting polynomial supports are more tractable. Full version of this paper can be found in [17].
Our notations and definitions follow [ 18] except that we call power products of indeterminate terms instead of monomials. By Gröbner basis computation, we mean computation of reduced Gröbner bases. Our goal is to realize Gröbner basis computation through learning. To this end, we need a large training set {( , )}=1 with finite polynomial set ⊂ [ 1, … , ] and Gröbner basis of ideal ⟨ ⟩. As the computation from to is computationally expensive in general, we instead resort to backward generation (i.e., solution-to-problem process); that is, we generate a Gröbner basis randomly and transform it to non-Gröbner set .
Problem 2.1 (Random generation of Gröbner bases). Find a collection = { Gröbner basis ⊂ [ 1, … , ] of ⟨ ⟩, = 1, … , . The collection should contain diverse bases, and we }=1 with the reduced need an eficient algorithm for constructing them.
Problem 2.2 (Backward Gröbner problem). Given a Gröbner basis ⊂ [ 1, … , ], find a collection should contain diverse sets, and we need an eficient algorithm for constructing them. ℱ = { }=1 of polynomial sets that are not Gröbner bases but ⟨ ⟩ = ⟨⟩ for = 1, … , . The collection
to contain diverse polynomial sets. Thus, the algorithms for these problems should not be deterministic but should have some controllable randomness.
What makes the learning of Gröbner basis computation hard is that, to our knowledge, neither (i) a random generation of Gröbner basis nor (ii) the backward transform from Gröbner basis to non-Gröbner set has been considered in computational algebra. Its primary interest has been instead posed on Gröbner basis computation (i.e., forward generation), and nothing motivates the random generation of Gröbner basis nor the backward transform. Interestingly, machine learning now sheds light on them. Formally, we address the following problems for dataset generation.
In this paper, we tackle these problems in the case of radical 0-dimensional ideals. We first address Prob. 2.1 using the fact that 0-dimensional radical ideals are generally in shape position.
1, … , ] is called in shape position if some univariate polynomials ℎ, 1, … , −1 ∈ [ ] form the reduced ≺lex-Gröbner basis of as follows. = {ℎ, 1 − 1, … , −1 − −1 }.
(2.1)
Particularly, 0-dimensional radical ideals are almost always in shape position if is an infinite field or finite field with large field order [
19, 20]. With this fact, an eficient sampling of Gröbner bases of 0-dimensional radical ideals can be realized by sampling polynomials in [ ], i.e., ℎ, 1, … , −1 with ℎ ≠ 0. We have to make sure that the degree of ℎ is always greater than that of 1, … , −1 , which is necessary and suficient for
to be a reduced Gröbner basis. This approach involves eficiency and randomness, and thus resolving Prob. 2.1. To address Prob. 2.2, we consider the following problem. non-Gröbner set = ( 1, … , )⊤ =
such that ⟨ ⟩ = ⟨⟩ . its ≺-Gröbner basis with respect to term order ≺.1 Find a polynomial matrix ∈ [ Problem 2.4. Let ⊂ [ 1, … , ] be a 0-dimensional ideal, and let = ( 1, … , )⊤ ∈ [ 1 , … , ] be 1, … , ]× giving a Namely, we generate a set of polynomials = ( 1, … , )⊤ from = ( 1, … , )⊤ by = ∑=1 for = 1, … , , where ∈ [
1, … , ] denotes the (, ) -th entry of . Note that ⟨ ⟩ and ⟨⟩ not identical, and the design of such that ⟨ ⟩ = ⟨⟩ is of our question.
A similar question was studied without the Gröbner condition in [21, 22]. They provided an algebraic necessary and suficient condition for the polynomial system of to have a solution outside the variety defined by . This condition is expressed explicitly by multivariate resultants. However, strong additional assumptions are required: , ,
are homogeneous, is a regular sequence, and in the end, ⟨ ⟩ = ⟨ ⟩ is only satisfied up to saturation. Thus, they are not compatible with our setting and method for Prob. 2.1. Our analysis gives the following results for the design to achieve ⟨ ⟩ = ⟨⟩ for the are generally 0-dimensional case. = ( 1, … , )⊤ = with ∈ [ 1, … , ]
× .
Theorem 2.5. Let = ( 1, … , )⊤ be a Gröbner basis of a 0-dimensional ideal in [ 1, … , ]. Let 1. If ⟨ ⟩ = ⟨⟩ , it implies ≥ . 2. If has a left-inverse in [ 1, … , ] × , ⟨ ⟩ = ⟨⟩ holds. 3. The equality ⟨ ⟩ = ⟨⟩
holds if and only if there exists a matrix ∈ [ row of − is a syzygy of , where is the identity matrix of size . 1, … , ]× such that each
We now assume ≺=≺lex and 0-dimensional ideals in shape position. Then, has exactly generators. When = , we have the following.
Proposition 2.6. For any ∈ [
1, … , ]× with det( ) ∈ ∖ {0} , we have ⟨ ⟩ = ⟨⟩ . 2 = ( −, −, ∈ [
1, … , ] is to compute =
( 2 + 2)-times multiplications of polynomials.
As non-zero constant scaling does not change the ideal, we focus on with det( ) = ±1 without loss of generality. Such can be constructed using the Bruhat decomposition = 1, 2 ∈ ST(, [
1, … , ]) are upper-triangular matrices with all-one diagonal entries (i.e., unimodular upper-triangular matrices) and ∈ {0, 1} × denotes a permutation matrix. Noting that −1 satisfies 1 2, where −1 = , we have ⟨⟩ = ⟨⟩
from Thm. 2.5. Therefore, random sampling ( 1, 2, ) of unimodular upper-triangular matrices 1, 2 and a permutation matrix resolves the backward Gröbner problem for = . We extend this idea to the case of > using a rectangular unimodular upper-triangular matrix 2′ ) ∈ [ 1, … , ]× , where 2′ ∈ [ 1, … , ]× is a unimodular upper-triangular matrix and (−)× is the zero matrix. The permutation matrix is now ∈ {0, 1} × . Our strategy 1
2 , which only requires a sampling of ( 2) polynomials in [ 1, … , ], and We present the eficiency of our dataset generation method and the learnability of Gröbner basis computation. The experiments were conducted with 48-core CPUs, 768GB RAM, and NVIDIA RTX A6000ada GPUs. Due to the space limitation, we cannot present full experimental setup. See the full version in [17]. 1We surcharge notations to mean that the set { 1, … , } defined by the vector is a ≺-Gröbner basis. Dataset generation. We constructed 12 datasets () for ∈ {2, 3, 4, 5} and ∈ { 7, 31, ℚ} and measured the runtime of our backward generation and naive forward generation (i.e., Gröbner basis computation). In the backward generation, we sampled Gröbner bases of ideals in shape position. In this step, univariable polynomials were generically sampled in [ 1, … , ]≤5. Next, Gröbner bases were transformed to non-Gröbner sets based on Thm. 2.5. Random polynomials in Bruhat decomposition (i.e., 1 and 2′) were sampled from [ 1, … , ]≤3 and restricted to monomials and binomials. For ℚ, coeficients of all sampled polynomials were bounded as / with , ∈ {−5, … , 5} and we only accepted with coeficients such as , ∈ {−100, … , 100} . This restriction is required from our machine learning model and learning framework. For forward generation, we adopted three algorithms given by SageMath [23] with the libSingular backend. For a fair comparison, forward generation computed Gröbner bases of the non-Gröbner sets given by the backward generation, leading to the identical dataset. As Tab. 1 shows, our backward generation is significant orders of magnitude faster than the forward generation. A sharp runtime growth is observed in the forward generation as the number of variables increases. Note that these numbers only show the runtime on 1,000 samples, while training typically requires millions of samples. Therefore, the forward generation is almost infeasible, and the proposed method resolves a bottleneck in the learning of Gröbner basis computation. Learning results. We used a standard Transformer (e.g., 6 encoder/decoder layers and 8 attention heads) and a standard training setup. The batch size was set to 16, and models were trained for 8 epochs. Each polynomial set in the datasets is converted into a sequence using the prefix representation and the separator tokens. To make the input sequence length manageable for vanilla Transformers, we used simpler datasets −() using 1, 2′ of a moderate density ∈ (0, 1] . This makes the maximum sequence length less than 5,000. Specifically, we used = 1.0, 0.6, 0.3, 0.2 for = 2, 3, 4, 5 , respectively. The training set has one million samples, and the test set has one thousand samples. Table 2 shows that trained Transformers successfully compute Gröbner bases with moderate/high accuracy. Not shown here, but we found several examples in the datasets for which Transformer successfully compute Gröbner bases significantly faster than math algorithms. The accuracy shows that the learning is more successful on infinite field coeficients ∈ {ℚ, ℝ} than finite field ones = . This may be a counter-intuitive observation because there are more possible coeficients in and for ℚ than . Specifically, for , the coeficient / ∈ ℚ is restricted to those with , ∈ {−5, … , 5} (i.e., roughly 50 choices), and , ∈ {−100, … , 100} (i.e., roughly 20,000 choices) for . In contrast, there are only choices for . The performance even degrades for the larger order = 31 . Interestingly, the support accuracy shows that the terms forming the polynomial (i.e., the support of polynomial) are correctly identified well. Thus, Transformers have dificulty determining the coeficients in finite fields. Several studies have also reported that learning to solve a problem involving modular arithmetic may encounter some dificulties [ 24, 25, 26]. 4. Conclusion This study proposed the first learning approach to a fundamental algebraic task, the Gröbner basis computation. While various recent studies have reported the learnability of mathematical problems by Transformers, we addressed the first problem with nontriviality in the dataset generation. Ultimately, the learning approach may be useful to address large-scale problems that cannot be approached by Gröbner basis computation algorithms because of their computational complexity. Transformers can output predictions in moderate runtime. The outputs may be incorrect, but there is a chance of obtaining a hint of a solution, as shown in our experiments. We believe that our study reveals many interesting open questions to achieve Gröbner basis computation learning.
This research was supported by JST ACT-X Grant Number JPMJAX23C8 and JSPS KAKENHI Grant Number JP22K13901. Yuta Kambe (Mitsubishi Electric Information Technology R&D Center) is not included in the authors due to a technical reason at submission. [11] J.-C. Faugère, A new eficient algorithm for computing Gröbner bases (F4), Journal of Pure and
Applied Algebra 139 (1999) 61–88. [12] J.-C. Faugère, A new eficient algorithm for computing Gröbner bases without reduction to zero (F5), in: Proceedings of the 2002 International Symposium on Symbolic and Algebraic Computation, ISSAC ’02, Association for Computing Machinery, New York, NY, USA, 2002, p. 75–83. [13] R. H. Makarim, M. Stevens, M4GB: An eficient Gröbner-basis algorithm, in: Proceedings of the 2017 ACM on International Symposium on Symbolic and Algebraic Computation, ISSAC’17, Association for Computing Machinery, New York, NY, USA, 2017, pp. 293–300. [14] G. Lample, F. Charton, Deep learning for symbolic mathematics, in: International Conference on
Learning Representations, 2020. URL: https://openreview.net/forum?id=S1eZYeHFDS. [15] L. Biggio, T. Bendinelli, A. Neitz, A. Lucchi, G. Parascandolo, Neural symbolic regression that scales, in: Proceedings of the 38th International Conference on Machine Learning, volume 139, 2021, pp. 936–945. [16] F. Charton, Linear algebra with transformers, Transactions on Machine Learning Research (2022). [17] H. Kera, Y. Ishihara, Y. Kambe, T. Vaccon, K. Yokoyama, Learning to compute gröbner bases, 2024.
arXiv:2311.12904. [18] D. A. Cox, J. Little, D. O’Shea, Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra, Undergraduate Texts in Mathematics, Springer International Publishing, 2015. [19] P. Gianni, T. Mora, Algebraic solution of systems of polynomial equations using Groebner bases, in: Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, Springer Berlin Heidelberg, Berlin, Heidelberg, 1989, pp. 247–257. [20] M. Noro, K. Yokoyama, A modular method to compute the rational univariate representation of zero-dimensional ideals, Journal of Symbolic Computation 28 (1999) 243–263. [21] L. Busé, M. Elkadi, B. Mourrain, Resultant over the residual of a complete intersection, Journal of
Pure and Applied Algebra 164 (2001) 35–57. [22] L. Busé, Étude du résultant sur une variété algébrique, Theses, Université Nice Sophia Antipolis, 2001. [23] The Sage Developers, SageMath, the Sage Mathematics Software System (Version 10.0), 2023.
https://www.sagemath.org. [24] A. Power, Y. Burda, H. Edwards, I. Babuschkin, V. Misra, Grokking: Generalization beyond overfitting on small algorithmic datasets, arXiv abs/2201.02177 (2022). [25] F. Charton, Can transformers learn the greatest common divisor?, arXiv abs/2308.15594 (2023). [26] A. Gromov, Grokking modular arithmetic, arXiv abs/2301.02679 (2023).