PolSys seminar


On the complexity of computing Gröbner bases for weighted homogeneous systems

Friday, September 12, 2014
Speaker(s) :  Thibaut Verron (PolSys team, CNRS/INRIA/UPMC)

Let $K$ be a field and $(f_1, ldots, f_m)subset K[X_1, ldots, X_n]$ be a sequence of weighted homogeneous polynomials of respective weighted degrees $(d_1, ldots, d_n)$. By this, we mean that there exists $(w_{1},dots,w_{n}) in mathbb{Z}_{>0}^{n}$ s.t. for any $1 leq j leq n$, the polynomial $f_{i}(X_{1}^{w_{1}},dots,X_{n}^{w_{n}})$ is homogeneous and has degree $d_{i}$.
Gröbner bases algorithms for homogeneous systems can be adapted to the weighted homogeneous case, and for zero dimensional weighted homogeneous systems defined by a regular sequence, the complexity of these algorithms is polynomial in the number of solutions, which is given by the weighted Bézout bound $prod d_{i} / prod w_{i}$. The weighted structure also ensures that the degree of regularity of the system, defined as the maximal degree reached when compute a degree basis, is reduced by a term linear in the sum of the weights. In this talk, we examine these systems under new genericity hypotheses, which allow us to refine this result by making the bound sharp.
We also investigate the positive dimensional and the over-determined cases. Under genericity hypotheses, we can again bound the degree of regularity and obtain complexity results similar to the zero dimensional case. Experiments with both generic systems and systems from applications confirm that taking into account the weighted structure of a system yields significant speed-ups.
Joint work with Jean-Charles Faugère and Mohab Safey El Din.

More details here …
Elias.Tsigaridas (at) nulllip6.fr