I am new to the theory of solving systems of polynomial equations using Gröbner bases and I am confused about the terminology. I will appreciate any help to clarify my confusion.
Some sources are stating that in order to solve the system of polynomial equations one needs to compute Gröbner bases (multiple bases) with respect to degree reversed lexicographical ordering, then change the orderings of Gröbner bases (again multiple bases) to lexicographical ordering, and then transform Gröbner bases to either triangular sets or rational univariate representations. Other sources talk about a Gröbner basis. We compute a Gröbner basis (single) w.r.t. to degree reversed lexicographical ordering, then change the ordering of a Gröbner basis (again single basis) to lexicographical ordering…
If I have a system of $m$ polynomials $f_1, \cdots, f_m \in \mathbb{F}_p[x_1, \dots, x_n]$ and want to find roots of this system of polynomials using Gröbner bases theory, then I first generate an ideal $I = \langle f_1, \cdots, f_m \rangle$. Then for this ideal with respect to the term order do I need to compute a Gröbner basis or multiple Gröbner bases?
Thank you.
Best Answer
Groebner bases are defined with respect to some ordering on the monomials of the ring. To compute a Groebner basis with respect to a fixed ordering (say, lexicographical), a computer algebra package such as Magma will first compute it with respect to an 'easier' basis, normally grevlex or weighted grevlex using some algorithm (e.g., Buchberger or Faugère) and then transform that into a Groebner basis with respect to your chosen basis (normally using something called a Groebner walk).
If you want to solve your polynomial equations then any Groebner basis will do. However, you might want to use several different ones. From practical experience using these things, the grevlex ordering might offer a short basis, but it will not be a basis for the radical of the ideal, just of the ideal itself. For solving the equations, you would like the radical of the ideal. This is possible, but hard. The poor man's version is to just remove all of the powers from the defining polynomials of the ideal. Now, switching to a different ordering yields a new set of defining polynomials, which might once again have powers. Remove these powers, then switch to another ordering, remove any powers you might find, and so on until your set of polynomials stabilizes with respect to all orderings you might want.
Since you aren't generating the genuine radical of the ideal, you might end up with possible solutions that aren't genuine, but this poor man's version of taking the radical is computationally a lot easier, in the sense that it's possible this year, and you might still get enough to work with.