Sub-cubic change of ordering for Gröbner basis: a probabilistic approach

The usual algorithm to solve polynomial systems using Grobner bases consists of two steps: first computing the DRL Grobner basis using the F 5 algorithm then computing the LEX Grobner basis using a change of ordering algorithm. When the Bezout bound is reached, the bottleneck of the total solving process is the change of ordering step. For 20 years, thanks to the FGLM algorithm the complexity of change of ordering is known to be cubic in the number of solutions of the system to solve. We show that, in the generic case or up to a generic linear change of variables, the multiplicative structure of the quotient ring can be computed with no arithmetic operation. Moreover, given this multiplicative structure we propose a change of ordering algorithm for Shape Position ideals whose complexity is polynomial in the number of solutions with exponent ω where 2 ≤ ω i.e . with exponent ω) complexity and whose total complexity is dominated by the complexity of the F 5 algorithm. In practice we obtain significant speedups for various polynomial systems by a factor up to 1500 for specific cases and we are now able to tackle some instances that were intractable.