# Learning a performance metric of Buchberger's algorithm

@article{Mojsilovic2021LearningAP, title={Learning a performance metric of Buchberger's algorithm}, author={Jelena Mojsilovi'c and Dylan Peifer and Sonja Petrovi'c}, journal={ArXiv}, year={2021}, volume={abs/2106.03676} }

What can be (machine) learned about the complexity of Buchberger’s algorithm? Given a system of polynomials, Buchberger’s algorithm computes a Gröbner basis of the ideal these polynomials generate using an iterative procedure based on multivariate long division. The runtime of each step of the algorithm is typically dominated by a series of polynomial additions, and the total number of these additions is a hardware independent performance metric that is often used to evaluate and optimize… Expand

#### Figures and Tables from this paper

#### References

SHOWING 1-10 OF 25 REFERENCES

Learning selection strategies in Buchberger's algorithm

- Computer Science, Mathematics
- ICML
- 2020

A new approach to Buchberger's algorithm is introduced that uses reinforcement learning agents to perform S-pair selection, a key step in the algorithm, and how the difficulty of the problem depends on the choices of domain and distribution of polynomials is studied. Expand

Random sampling in computational algebra: Helly numbers and violator spaces

- Computer Science, Mathematics
- J. Symb. Comput.
- 2016

It is shown that Clarkson's sampling algorithm can be applied to two problems in computational algebra: solving large-scale polynomial systems and finding small generating sets of graded ideals. Expand

Sparse Gröbner bases: the unmixed case

- Mathematics, Computer Science
- ISSAC
- 2014

A variant of Fröberg's conjecture is proposed which allows us to estimate the complexity of solving overdetermined sparse systems and it is proved that restrictive assumptions in usual complexity estimates of classical inhomogeneous Gröbner bases algorithms can be removed. Expand

Algebraic Algorithms for Sampling from Conditional Distributions Eye Color Black Brunette Red Blonde Total

We construct Markov chain algorithms for sampling from discrete exponential families conditional on a sufticient statistic. Examples include contingency tables, logistic regression, and spectral… Expand

Short rational functions for toric algebra and applications

- Mathematics, Computer Science
- J. Symb. Comput.
- 2004

This work encodes the binomials belonging to the toric ideal I A associated with an integral d × n matrix A using a short sum of rational functions as introduced by Barvinok and Woods, and derives a polynomial time algorithm for normal form computations. Expand

Smale’s 17th problem: Average polynomial time to compute affine and projective solutions

- Mathematics
- 2008

Smale’s 17th Problem asks: “Can a zero of n complex polynomial equations in n unknowns be found approximately, on the average, in polynomial time with a uniform algorithm?”. We give a positive answer… Expand

Deep Learning for Symbolic Mathematics

- Mathematics, Computer Science
- ICLR
- 2020

It is shown that neural networks can be surprisingly good at more elaborated tasks in mathematics, such as symbolic integration and solving differential equations, and a syntax for representing these mathematical problems, and methods for generating large datasets that can be used to train sequence-to-sequence models. Expand

On Smale's 17th Problem: A Probabilistic Positive Solution

- Mathematics, Computer Science
- Found. Comput. Math.
- 2008

A uniform probabilistic algorithm is presented for Smale's 17th Problem and it is proved that the complexity of this problem is polynomial. Expand

Average behavior of minimal free resolutions of monomial ideals

- Mathematics
- Proceedings of the American Mathematical Society
- 2019

We show that, under a natural probability distribution, random monomial ideals will almost always have minimal free resolutions of maximal length; that is, the projective dimension will almost always… Expand

Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra, 3/e (Undergraduate Texts in Mathematics)

- Mathematics
- 1992

Algebraic Geometry is the study of systems of polynomial equations in one or more variables, asking such questions as: Does the The denominator is taking on this, book interested. This book for… Expand