On the complexity of Gröbner basis computation for regular <br/><br/>and semi-regular systems

Thursday, September 21, 2006 - 1:20pm - 2:10pm
EE/CS 3-180
Bruno Salvy (Institut National de Recherche en Informatique Automatique (INRIA))
We study the complexity of Gröbner bases computation, in
particular in the generic situation where the variables are in
simultaneous Noether position with respect to the system. We bound
precisely the exponent of the complexity of Faugère
F5 algorithm in this case. This complexity is related to the index of
regularity of the ideal. For regular systems, this index is well-
known. We define a class of overdetermined systems called semi-
regular systems for which we derive sharp asymptotic estimates of the
index of regularity. These systems are conjectured to be generic in a
precise sense.

This is joint work with Magali Bardet and Jean-Charles Faugère.
MSC Code: