research-article

Exploring the Dynamic Buchberger Algorithm

Author:

John PerryAuthors Info & Claims

ISSAC '17: Proceedings of the 2017 ACM International Symposium on Symbolic and Algebraic Computation

Pages 365 - 372

https://doi.org/10.1145/3087604.3087643

Published: 23 July 2017 Publication History

Abstract

Abstract "Static" Buchberger algorithms to compute a Gröbner basis require as input both a set of polynomials and a term ordering. "Dynamic" Buchberger algorithms do not require an ordering as input, but compute instead a Gröbner basis with respect to a "discovered" ordering. A good heuristic usually results in a basis that is relatively small, a desirable property for many applications. This article uses a new C++ implementation to explore variants of the original algorithm. While the implementation is preliminary, and in general much slower than well-known static implementations, it still succeeds at computing some bases more quickly.

References

[1]

J. Abbott, A. M. Bigatti, and G. Lagorio. 2017. CoCoA-5: a system for doing Computations in Commutative Algebra. Available at http://cocoa.dima.unige.it. (2017).

[2]

R. Bagnara, P. M. Hill, and E. Zaffanella. 2008. The Parma Polyhedra Library: Toward a Complete Set of Numerical Abstractions for the Analysis and Verification of Hardware and Software Systems. Science of Computer Programming 72, 1--2 (2008), 3--21.

Digital Library

[3]

Michael Brickenstein. 2009. Slimgb: Gröbner bases with slim polynomials. Revista Matemática Complutense 23, 2 (2009), 453--466.

[4]

Bruno Buchberger. 1965. Ein Algorithmus zum Auffinden der Basiselemente des Restklassenringes nach einem nulldimensionalem Polynomideal (An Algorithm for Finding the Basis Elements in the Residue Class Ring Modulo a Zero Dimensional Polynomial Ideal). Ph.D. Dissertation. Mathematical Institute, University of Innsbruck, Austria. English translation published in the Journal of Symbolic Computation (2006) 475--511.

Digital Library

[5]

Bruno Buchberger. 1985. Gröbner-Bases: An Algorithmic Method in Polynomial Ideal Theory. In Multidimensional Systems Theory - Progress, Directions and Open Problems in Multidimensional Systems, N. K. Bose (Ed.). Reidel Publishing Company, Dotrecht -- Boston -- Lancaster, 184--232.

[6]

Massimo Caboara. 1993. A Dynamic Algorithm for Gröbner basis computation. In ISSAC '93. ACM Press, 275--283.

Digital Library

[7]

Massimo Caboara and John Perry. 2014. Reducing the size and number of linear programs in a dynamic Gröbner basis algorithm. Applicable Algebra in Engineering, Communication and Computing 25, 1 (2014), 99--117. Preprint available at arxiv.org/abs/1209.2379.

[8]

Wolfram Decker, Gert-Martin Greuel, Gerhard Pfister, and Hans Schönemann. 2016. Singular 4--1-0 -- A computer algebra system for polynomial computations. http://www.singular.uni-kl.de. (2016).

[9]

Torbjörn Granlund et al. 2000--2016. The GNU Linear Multiple Precision Arithmetic Library. The GNU Project. Available at gmplib.org.

[10]

Jean-Charles Faugère. 1999. A New Efficient Algorithm for Computing Gröbner bases (F4). Journal of Pure and Applied Algebra 139, 1--3 (June 1999), 61--88.

[11]

Jean-Charles Faugère. 2002. A new efficient algorithm for computing Gröbner bases without reduction to zero F5. In International Symposium on Symbolic and Algebraic Computation Symposium - ISSAC 2002, Villeneuve d'Ascq, France. 75--82. Revised version downloaded from fgbrs.lip6.fr/jcf/Publications/index.html.

Digital Library

[12]

Rudiger Gebauer and Hans Möller. 1988. On an Installation of Buchberger's Algorithm. Journal of Symbolic Computation 6 (1988), 275--286.

Digital Library

[13]

Vladimir Gerdt and Yuri Blinkov. 1998. Involutive Bases of Polynomial Ideals. Mathematics and Computers in Simulation 45, 5--6 (March 1998), 419--541.

Digital Library

[14]

Alessandro Giovini, Teo Mora, Gianfranco Niesi, Lorenzo Robbiano, and Carlo Traverso. 1991. "One sugar cube, please" OR Selection strategies in the Buchberger algorithm. In Proceedings of the 1991 International Symposium on Symbolic and Algebraic Computation. ACM Press, 49--54.

Digital Library

[15]

Oleg Golubitsky. in preparation. Converging term order sequences and the dynamic Buchberger algorithm. (in preparation). Preprint received in private communication.

[16]

Daniel R. Grayson and Michael E. Stillman. 1992. Macaulay2, a software system for research in algebraic geometry. Available at http://www.math.uiuc.edu/Macaulay2/. (1992).

[17]

Peter Gritzmann and Bernd Sturmfels. 1993. Minkowski Addition of Polytopes: Computational Complexity and Applications to Gröbner Bases. SIAM J. Disc. Math 6, 2 (1993), 246--269.

Digital Library

[18]

Amir Hashemi and Delaram Talaashrafi. 2016. A Note on Dynamic Gröbner Bases Computation. In CASC 2016 (Lecture Notes in Computer Science), Vol. 9890. Springer, 276--288.

[19]

Andrew Makhorin. 2012. GNU Linear Programming Kit. The GNU Project. www.gnu.org/software/glpk/.

[20]

Teo Mora and Lorenzo Robbiano. 1988. The Gröbner fan of an ideal. Journal of Symbolic Computation 6 (1988), 183--208.

Digital Library

[21]

Theodore Motzkin, Howard Raiffa, Gerald Thompson, and Robert Thrall. 1953. The double description method. In Contributions to the theory of games. Annals of Mathematics Studies, Vol. 2. Princeton University Press, Princeton, New Jersey, 51--73.

[22]

Lorenzo Robbiano. 1986. On the theory of graded structures. Journal of Symbolic Computation 2 (1986), 139--170.

Digital Library

[23]

William Stein. 2012. Sage: Open Source Mathematical Software (Version 5.x). The Sage Group. Available at www.sagemath.org.

[24]

Carlo Traverso. 1996. Hilbert functions and the Buchberger algorithm. Journal of Symbolic Computation 22, 4 (1996), 355--376.

Digital Library

[25]

Jan Verschelde. 2017. The database of polynomial systems. Available at http://homepages.math.uic.edu/~jan/. (2017).

[26]

Thomas Yan. 1998. The Geobucket Data Structure for Polynomials. Journal of Symbolic Computation 25 (1998), 285--293.

Digital Library

[27]

Nikolai Zolotykh. 2012. A new modification of the double description method for constructing the skeleton of a polyhedral cone. Comput. Math. Math. Phys. 52, 1 (2012), 146--156.

Cited By

Bastrakov SChurkin AZolotykh N(2020)Accelerating Fourier–Motzkin elimination using bit pattern treesOptimization Methods and Software10.1080/10556788.2020.171260036:5(1082-1095)Online publication date: 14-Jan-2020
https://doi.org/10.1080/10556788.2020.1712600
Perry J(2020)A dynamic F4 algorithm to compute Gröbner basesApplicable Algebra in Engineering, Communication and Computing10.1007/s00200-020-00450-y31:5-6(411-434)Online publication date: 1-Nov-2020
https://dl.acm.org/doi/10.1007/s00200-020-00450-y
Langeloh G(2020)A comparison of unrestricted dynamic Gröbner Basis algorithmsApplicable Algebra in Engineering, Communication and Computing10.1007/s00200-020-00449-531:5-6(389-409)Online publication date: 1-Nov-2020
https://dl.acm.org/doi/10.1007/s00200-020-00449-5
Show More Cited By

Index Terms

Exploring the Dynamic Buchberger Algorithm
1. Computing methodologies
  1. Symbolic and algebraic manipulation
    1. Symbolic and algebraic algorithms
      1. Algebraic algorithms

Recommendations

A dynamic F4 algorithm to compute Gröbner bases
Abstract
The F4 algorithm re-imagines Buchberger’s algorithm as the row reduction of a Macaulay matrix: each row corresponds to a polynomial; each reduction of one row by another corresponds to one step of reducing an S-polynomial; and any row that ...
Applying IsRewritten criterion on Buchberger algorithm

Faugere's F"5 algorithm is one of the fastest algorithms to compute Grobner bases. It uses two criteria namely the F"5 criterion and the IsRewritten criterion to detect the useless critical pairs (see Faugere (2002) [8]). The IsRewritten criterion has ...
A speed-up of the algorithm for computing comprehensive Gröbner systems
ISSAC '07: Proceedings of the 2007 international symposium on Symbolic and algebraic computation

We introduce a new algorithm for computing comprehensive Gröbner systems.There exists the Suzuki-Sato algorithm for computing comprehensive Gröbner systems. The Suzuki-Sato algorithm often creates overmuch cells of the parameter space for comprehensive ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

ISSAC '17: Proceedings of the 2017 ACM International Symposium on Symbolic and Algebraic Computation

July 2017

466 pages

ISBN:9781450350648

DOI:10.1145/3087604

Editor:
Michael Burr
Clemson University, USA
,
General Chair:
Chee K. Yap
New York University, USA
,
Program Chair:
Mohab Safey El Din
University Pierre et Marie Curie, France

Copyright © 2017 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

In-Cooperation

SIGSAM: ACM Special Interest Group on Symbolic and Algebraic Manipulation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 23 July 2017

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

ISSAC '17

ISSAC '17: International Symposium on Symbolic and Algebraic Computation

July 23 - 28, 2017

Kaiserslautern, Germany

Acceptance Rates

Overall Acceptance Rate 395 of 838 submissions, 47%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
118
Total Downloads

Downloads (Last 12 months)6
Downloads (Last 6 weeks)0

Reflects downloads up to 18 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Bastrakov SChurkin AZolotykh N(2020)Accelerating Fourier–Motzkin elimination using bit pattern treesOptimization Methods and Software10.1080/10556788.2020.171260036:5(1082-1095)Online publication date: 14-Jan-2020
https://doi.org/10.1080/10556788.2020.1712600
Perry J(2020)A dynamic F4 algorithm to compute Gröbner basesApplicable Algebra in Engineering, Communication and Computing10.1007/s00200-020-00450-y31:5-6(411-434)Online publication date: 1-Nov-2020
https://dl.acm.org/doi/10.1007/s00200-020-00450-y
Langeloh G(2020)A comparison of unrestricted dynamic Gröbner Basis algorithmsApplicable Algebra in Engineering, Communication and Computing10.1007/s00200-020-00449-531:5-6(389-409)Online publication date: 1-Nov-2020
https://dl.acm.org/doi/10.1007/s00200-020-00449-5
Zolotykh NBastrakov S(2019)Two variations of graph test in double description methodComputational and Applied Mathematics10.1007/s40314-019-0862-038:3Online publication date: 17-May-2019
https://doi.org/10.1007/s40314-019-0862-0
Semenov SZolotykh N(2019)A Dynamic Algorithm for Constructing the Dual Representation of a Polyhedral ConeMathematical Optimization Theory and Operations Research10.1007/978-3-030-22629-9_5(59-69)Online publication date: 12-Jun-2019
https://doi.org/10.1007/978-3-030-22629-9_5

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents