eCommons

 

Reinforcement Learning in Buchberger's Algorithm

Other Titles

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.

Journal / Series

Volume & Issue

Description

169 pages

Sponsorship

Date Issued

2021-05

Publisher

Keywords

algebraic geometry; commutative algebra; computer algebra; Groebner basis; machine learning; reinforcement learning

Location

Effective Date

Expiration Date

Sector

Employer

Union

Union Local

NAICS

Number of Workers

Committee Chair

Stillman, Michael

Committee Co-Chair

Committee Member

Kozen, Dexter
Halpern-Leistner, Daniel S.

Degree Discipline

Mathematics

Degree Name

Ph. D., Mathematics

Degree Level

Doctor of Philosophy

Related Version

Related DOI

Related To

Related Part

Based on Related Item

Has Other Format(s)

Part of Related Item

Related To

Related Publication(s)

Link(s) to Related Publication(s)

References

Link(s) to Reference(s)

Previously Published As

Government Document

ISBN

ISMN

ISSN

Other Identifiers

Rights

Rights URI

Types

dissertation or thesis

Accessibility Feature

Accessibility Hazard

Accessibility Summary

Link(s) to Catalog Record