Gröbner Basis VooDoo

An extension of F₅: Given a system of multivariate polynomials, compute a Gröbner Basis and the respective vectors of origin.

Vectors of Origin

Given input system F = (f₀, …, f_n-1), a Gröbner basis algorithm outputs system G = (g₀, …, g_m-1) spanning the same ideal ⟨F⟩. Even for mildly complex systems F, it is generally not at all obvious how to (weightedly) combine the f_i to arrive at any given g_j.

A vector v = (v₀, …, v_n-1) is called Vector of Origin (voo) for g_j if the inner product of F and v equals g_j. That is, Σ_i f_i·v_i = g_j.

Arranging all m vectors of origin into a matrix V, we have F·V = G. This n×m matrix V, where each entry is a multivariate polynomial, contains a lot of juicy information about F!

Code

The F₅ algorithm due to Jean-Charles Faugère implicitly uses vectors of origin – this code simply makes them explicit. It is an extension of the F5 and F4 sagemath implementation by Martin Albrecht and John Perry.