An extension of F5: Given a system of multivariate polynomials, compute a Gröbner Basis and the respective vectors of origin.
Given input system F = (f0, …, fn-1), a Gröbner basis algorithm outputs system G = (g0, …, gm-1) spanning the same ideal ⟨F⟩. Even for mildly complex systems F, it is generally not at all obvious how to (weightedly) combine the fi to arrive at any given gj.
A vector v = (v0, …, vn-1) is called Vector of Origin (voo) for gj if the inner product of F and v equals gj. That is, Σi fi·vi = gj.
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!
The F5 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.