A complexity analysis of the F4 Gröbner basis algorithm with tracer data
This provides a theoretical advance in computational algebra for researchers working on polynomial system solving, though it appears incremental as it builds on existing conjectures and algorithms.
The paper tackles the problem of computing grevlex Gröbner bases for generic zero-dimensional systems by deriving a new complexity bound for the F4 Tracer algorithm, improving over state-of-the-art bounds by an exponential factor in the number of variables.
We provide a new complexity bound for the computation of grevlex Gröbner bases in the generic zero-dimensional case, relying on Moreno-SocÃas' conjecture. We first formalize a property of regular sequences that implies a well-known folklore consequence, which we call the increasing degree property. We then derive a new understanding of the selection of pairs in the F4 algorithm based on Moreno-SocÃas' conjecture. Moreover, we obtain an exact formula for the number of elements in the grevlex Gröbner basis of a given degree, for half of the relevant degrees. Combining these results, we derive a precise complexity formula for the F4 Tracer algorithm, together with its asymptotic behavior when the number of variables tends to infinity. These results yield an improvement over the state-of-the-art complexity bounds by a factor which is exponential in the number of variables.