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 条

[21] Computing Grobner bases of pure binomial ideals via submodules of Zn [J].

Boffi, Giandomenico ;

Logar, Alessandro .

JOURNAL OF SYMBOLIC COMPUTATION, 2012, 47 (10) :1297-1308

[22] Fast Grobner basis computation and polynomial reduction for generic bivariate ideals [J].

van der Hoeven, Joris ;

Larrieu, Robin .

APPLICABLE ALGEBRA IN ENGINEERING COMMUNICATION AND COMPUTING, 2019, 30 (06) :509-539

[23] Criteria for Finite Difference Grobner Bases of Normal Binomial Difference Ideals [J].

Chen, Yu-Ao ;

Gao, Xiao-Shan .

PROCEEDINGS OF THE 2017 ACM INTERNATIONAL SYMPOSIUM ON SYMBOLIC AND ALGEBRAIC COMPUTATION (ISSAC'17), 2017, :93-100

[24] Grobner bases with respect to several orderings and multivariable dimension polynomials [J].

Levin, Alexander B. .

JOURNAL OF SYMBOLIC COMPUTATION, 2007, 42 (05) :561-578

[25] Properties of entire functions over polynomial rings via Grobner bases [J].

Apel, J ;

Stückrad, J ;

Tworzewski, P ;

Winiarski, T .

APPLICABLE ALGEBRA IN ENGINEERING COMMUNICATION AND COMPUTING, 2003, 14 (01) :1-10

[26] Decomposing Polynomial Sets Simultaneously into Grobner Bases and Normal Triangular Sets [J].

Dong, Rina ;

Mou, Chenqi .

COMPUTER ALGEBRA IN SCIENTIFIC COMPUTING, CASC 2017, 2017, 10490 :77-92

[27] Computing polynomial univariate representations of zero-dimensional ideals by Grobner basis [J].

Ma XiaoDong ;

Sun Yao ;

Wang DingKang .

SCIENCE CHINA-MATHEMATICS, 2012, 55 (06) :1293-1302

[28] Many toric ideals generated by quadratic binomials possess no quadratic Grobner bases [J].

Hibi, Takayuki ;

Nishiyama, Kenta ;

Ohsugi, Hidefumi ;

Shikama, Akihiro .

JOURNAL OF ALGEBRA, 2014, 408 :138-146

[29] Generalized Grobner Bases and New Properties of Multivariate Difference Dimension Polynomials [J].

Levin, Alexander .

PROCEEDINGS OF THE 2021 INTERNATIONAL SYMPOSIUM ON SYMBOLIC AND ALGEBRAIC COMPUTATION, ISSAC 2021, 2021, :273-280

[30] Grobner Bases with Respect to Several Term Orderings and Multivariate Dimension Polynomials [J].

Levin, Alexander B. .

ISSAC 2007: PROCEEDINGS OF THE 2007 INTERNATIONAL SYMPOSIUM ON SYMBOLIC AND ALGEBRAIC COMPUTATION, 2007, :251-260

← 1 2 3 4 →