Dimension-dependent bounds for Grobner bases of polynomial ideals

被引：18

作者：

Mayr, Ernst W. ^{[1
]}

Ritscher, Stephan ^{[1
]}

机构：

[1] Tech Univ Munich, D-85748 Garching, Germany

来源：

JOURNAL OF SYMBOLIC COMPUTATION | 2013年 / 49卷

关键词：

Grobner basis; Degree bound; Polynomial ideal; Ideal dimension; Regular sequence; Noether normalization; Cone decomposition; COMMUTATIVE THUE SYSTEMS;

D O I：

10.1016/j.jsc.2011.12.018

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Given a basis F of a polynomial ideal I in K[x(1),...,x(n)] with degrees deg(F) <= d, the degrees of the reduced Grobner basis G w.r.t. any admissible monomial ordering are known to be double exponential in the number of indeterminates in the worst case, i.e. deg(G) = d(2 theta(n)). This was established in Mayr and Meyer (1982) and Dube (1990). We modify both constructions in order to give worst case bounds depending on the ideal dimension proving that deg(G) = d(n theta(1)2 theta(r)) for r-dimensional ideals (in the worst case). (C) 2011 Elsevier Ltd. All rights reserved.

引用

页码：78 / 94

页数：17

共 36 条

[31] Solving Systems of Polynomial Equations with Symmetries Using SAGBI-Grobner Bases [J].

Faugere, Jean-Charles ;

Rahmany, Sajjad .

ISSAC2009: PROCEEDINGS OF THE 2009 INTERNATIONAL SYMPOSIUM ON SYMBOLIC AND ALGEBRAIC COMPUTATION, 2009, :151-158

[32] A Divide-and-conquer Algorithm for Computing Grobner Bases of Syzygies in Finite Dimension [J].

Naldi, Simone ;

Neiger, Vincent .

PROCEEDINGS OF THE 45TH INTERNATIONAL SYMPOSIUM ON SYMBOLIC AND ALGEBRAIC COMPUTATION, ISSAC 2020, 2020, :380-387

[33] MXL3: An Efficient Algorithm for Computing Grobner Bases of Zero-Dimensional Ideals [J].

Mohamed, Mohamed Saied Emarn ;

Cabarcas, Daniel ;

Ding, Jintai ;

Buchmann, Johannes ;

Bulygin, Stanislav .

INFORMATION SECURITY AND CRYPTOLOGY - ISISC 2009, 2010, 5984 :87-+

[34] Grobner bases in difference-differential modules and difference-differential dimension polynomials [J].

Zhou Meng ;

Winkler, Franz .

SCIENCE IN CHINA SERIES A-MATHEMATICS, 2008, 51 (09) :1732-1752

[35] Generalization of the F5 algorithm for calculating Gröbner bases for polynomial ideals [J].

A. I. Zobnin .

Programming and Computer Software, 2010, 36 :75-82

[36] ON HOMOGENEOUS k-BUCHSBAUM POLYNOMIAL IDEALS, WITH ALGORITHMS IF THE KRULL DIMENSION IS LESS THAN OR EQUAL TO TWO [J].

Benjamin, E. ;

Bresinsky, H. .

HOUSTON JOURNAL OF MATHEMATICS, 2008, 34 (03) :637-647

← 1 2 3 4 →