Grobner bases of bihomogeneous ideals generated by polynomials of bidegree (1,1): Algorithms and complexity

被引:38
作者
Faugere, Jean-Charles [1 ]
El Din, Mohab Safey
Spaenlehauer, Pierre-Jean
机构
[1] INRIA, Paris Rocquencourt Ctr, SALSA Project, Paris, France
基金
美国国家科学基金会;
关键词
Grobner bases; Bihomogeneous ideals; Algorithms; Complexity;
D O I
10.1016/j.jsc.2010.10.014
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
Solving multihomogeneous systems, as a wide range of structured algebraic systems occurring frequently in practical problems, is of first importance. Experimentally, solving these systems with Grobner bases algorithms seems to be easier than solving homogeneous systems of the same degree. Nevertheless, the reasons for this behaviour are not clear. In this paper, we focus on bilinear systems (i.e. bihomogeneous systems where all equations have bidegree (1, 1)). Our goal is to provide a theoretical explanation of the aforementioned experimental behaviour and to propose new techniques to speed up the Grobner basis computations by using the multihomogeneous structure of those systems. The contributions are theoretical and practical. First, we adapt the classical F-5 criterion to avoid reductions to zero which occur when the input is a set of bilinear polynomials. We also prove an explicit form of the Hilbert series of bihomogeneous ideals generated by generic bilinear polynomials and give a new upper bound on the degree of regularity of generic affine bilinear systems. We propose also a variant of the F5 Algorithm dedicated to multihomogeneous systems which exploits a structural property of the Macaulay matrix which occurs on such inputs. Experimental results show that this variant requires less time and memory than the classical homogeneous F5 Algorithm. Lastly, we investigate the complexity of computing a Grobner basis for the grevlex ordering of a generic 0-dimensional affine bilinear system over k[x(1), ... ,xn(x), y(1), ... , y(ny)]. In particular, we show that this complexity is upper bounded by O(((nx+ny+min(nx+1,ny+1)(min(nx+1,ny+1)))(omega)), which is polynomial in n(x) + n(y) (i.e. the number of unknowns) when min(nx, ny) is constant. (C) 2010 Elsevier Ltd. All rights reserved.
引用
收藏
页码:406 / 437
页数:32
相关论文
共 29 条
[1]  
[Anonymous], 2010, INT S SYMBOLIC ALGEB
[2]  
ATIYAH M, 1969, SERIES MATH
[3]  
Bardet M., 2004, Etude des systemes algebriques surdetermines. Applications aux codes correcteurs et a la cryptographie
[4]  
BARDET M, 2005, P EFF METH ALG GEOM
[5]   COMBINATORICS OF MAXIMAL MINORS [J].
BERNSTEIN, D ;
ZELEVINSKY, A .
JOURNAL OF ALGEBRAIC COMBINATORICS, 1993, 2 (02) :111-121
[6]  
Bruns W, 2003, NATO SCI SER II-MATH, V115, P9
[8]  
COX D, 2007, LECT NOTES PURE APPL
[9]  
Cox D. A., 2007, IDEALS VARIETIES ALG, V3/e
[10]   Multihomogeneous resultant formulae by means of complexes [J].
Dickenstein, A ;
Emiris, LZ .
JOURNAL OF SYMBOLIC COMPUTATION, 2003, 36 (3-4) :317-342