Reducing the size and number of linear programs in a dynamic Gröbner basis algorithm

DOI10.1007/S00200-014-0216-5MaRDI QIDQ744015zbMATH OpenOpenAlexFDO

Authors Massimo Caboara, John Perry

Publication date 2 October 2014

Published in Applicable Algebra in Engineering, Communication and Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1209.2379

zbMATH Keywords

term orderingboundary vectorsdynamic Buchberger algorithmGröbner bases

Mathematics Subject Classification ID

Linear programming (90C05) Symbolic computation and algebraic computation (68W30) Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10)

Abstract: The dynamic algorithm to compute a Gr"obner basis is nearly twenty years old, yet it seems to have arrived stillborn; aside from two initial publications, there have been no published followups. One reason for this may be that, at first glance, the added overhead seems to outweigh the benefit; the algorithm must solve many linear programs with many linear constraints. This paper describes two methods of reducing the cost substantially, answering the problem effectively.

Recommendations

• A Note on Dynamic Gröbner Bases Computation
• scientific article; zbMATH DE number 1263330
• A dynamic F4 algorithm to compute Gröbner bases
• Efficient computation of zero-dimensional Gröbner bases by change of ordering
• A comparison of unrestricted dynamic Gröbner basis algorithms
• Exploring the dynamic Buchberger algorithm
• A new efficient algorithm for computing Gröbner bases (F₄)
• On an installation of Buchberger's algorithm
• An extension of Buchberger's algorithm to compute all reduced Gröbner bases of a polynomial ideal
• Dynamical Gröbner bases over Dedekind rings

Cites work

• scientific article; zbMATH DE number 3466805 (Why is no real title available?)
• scientific article; zbMATH DE number 1263330 (Why is no real title available?)
• scientific article; zbMATH DE number 1273640 (Why is no real title available?)
• scientific article; zbMATH DE number 2151220 (Why is no real title available?)
• A new class of term orders for elimination
• A new efficient algorithm for computing Gröbner bases (F₄)
• An algorithm for finding the basis elements of the residue class ring of a zero dimensional polynomial ideal
• Computing inhomogeneous Gröbner bases
• Ideal-specific elimination orders form a star-shaped region
• Minkowski Addition of Polytopes: Computational Complexity and Applications to Gröbner Bases
• Signature-based algorithms to compute Gröbner bases
• The Gröbner fan of an ideal

Cited in

(5)

• scientific article; zbMATH DE number 146430 (Why is no real title available?)
• A comparison of unrestricted dynamic Gröbner basis algorithms
• A dynamic F4 algorithm to compute Gröbner bases
• A Note on Dynamic Gröbner Bases Computation
• Exploring the dynamic Buchberger algorithm

Describes a project that uses

Uses Software

• SageMath

This page was built for publication: Reducing the size and number of linear programs in a dynamic Gröbner basis algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q744015)