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

DOI10.1007/S00200-014-0216-5zbMATH Open1328.13038arXiv1209.2379OpenAlexW2001476969MaRDI QIDQ744015FDOQ744015

Authors: Massimo Caboara, John Perry 

Publication date: 2 October 2014

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

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.

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

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_4)\)
• 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

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)

Cites Work

• Title not available (Why is that?)
• A new efficient algorithm for computing Gröbner bases \((F_4)\)
• An algorithm for finding the basis elements of the residue class ring of a zero dimensional polynomial ideal
• Title not available (Why is that?)
• Signature-based algorithms to compute Gröbner bases
• A new class of term orders for elimination
• Title not available (Why is that?)
• Minkowski Addition of Polytopes: Computational Complexity and Applications to Gröbner Bases
• The Gröbner fan of an ideal
• Computing inhomogeneous Gröbner bases
• Ideal-specific elimination orders form a star-shaped region
• Title not available (Why is that?)

Cited In (5)

• Title not available (Why is that?)
• 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

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)