Back to search

Cornell University

Reinforcement Learning in Buchberger's Algorithm

Abstract

dc:description.abstract

Buchberger’s algorithm is the classical algorithm for computing a Gröbner basis, and optimized implementations are crucial for many computer algebra systems. In this thesis we introduce a new approach to Buchberger’s algorithm that uses deep reinforcement learning agents to perform S-pair selection, a key choice in the algorithm. We first study how the difficulty of the problem depends on several random distributions of polynomial ideals, about which little is known. Next, we train a policy model using proximal policy optimization to learn S-pair selection strategies for random systems of binomial equations. In certain domains the trained model outperforms state-of-the-art selection heuristics in total number of polynomial additions performed, which provides a proof-of-concept that recent developments in machine learning have the potential to improve performance of critical algorithms in symbolic computation. Finally, we apply these techniques to Bigatti’s algorithm for computing a Hilbert series, and consider extending these results with neural network value models and tree search.

Degree

thesis:*
Name thesis:degree_name
Ph. D., Mathematics
Level thesis:degree_level
Doctor of Philosophy
Discipline thesis:degree_discipline
Mathematics
Grantor
Cornell University
Year dc:date.issued
2021

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Peifer, Dylan
Chair dc:contributor.chair
  • Stillman, Michael
Committee members dc:contributor.committeemember
  • Kozen, Dexter
  • Halpern-Leistner, Daniel S.

Subjects

dc:subject × 6

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*
Dc Identifier Bibid
15049405
Dc Identifier Other
ProQuest Submission ID: 12500
ProQuest Publication ID: 28492264

Chain of custody

source
Harvested from
Cornell University
Base URL
ecommons.cornell.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Peifer, Dylan. Reinforcement Learning in Buchberger's Algorithm. Doctor of Philosophy thesis, Cornell University, 2021. https://hdl.handle.net/1813/109782