Reducing the size and number of linear programs in a dynamic Gröbner basis algorithm (Q744015): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Changed an Item |
||
Property / describes a project that uses | |||
Property / describes a project that uses: SageMath / rank | |||
Normal rank |
Revision as of 00:35, 1 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Reducing the size and number of linear programs in a dynamic Gröbner basis algorithm |
scientific article |
Statements
Reducing the size and number of linear programs in a dynamic Gröbner basis algorithm (English)
0 references
2 October 2014
0 references
For most applications of \textit{Gröbner bases}, we need only a Gröbner basis of the given ideal and do not need to specify the monomial ordering. Therefore, it would be of interest to find the shortest Gröbner basis for the ideal by appropriate choice of a monomial ordering. In this direction, \textit{P. Gritzmann} and \textit{B. Sturmfels} [SIAM J. Discrete Math. 6, No. 2, 246--269 (1993; Zbl 0798.68157)] introduced the dynamic versions of Buchberger's Gröbner bases algorithm for polynomial ideals. In the paper under review the authors consider an improvement of the \textit{dynamic Buchberger's algorithm}. Despite of the ordinary Buchberger's algorithm, this algorithm computes a Gröbner basis for a given ideal and it does not require a monomial ordering as input. Indeed, this algorithm returns an efficient monomial ordering and also a Gröbner basis for the given ideal with respect to that ordering. The main approaches to compute dynamic Gröbner bases are based on linear programming, but the associated linear programs grow very large and the algorithm may become inefficient. In this paper, the authors propose two methods to reduce the size and the number of these linear programs which have been solved during the computation.
0 references
Gröbner bases
0 references
dynamic Buchberger algorithm
0 references
boundary vectors
0 references
term ordering
0 references