Let \(A=k[x_1,\dots,x_n]\) be a multivariate polynomial ring, where \(k=\mathbb{R}\) or \(\mathbb{C}\), and suppose \(P_1=0,\dots,P_m=0\) is a system of polynomials in \(A\) we wish to solve. As is well known, we can solve this system by computing a Gröbner basis for the system in lexicographic order. As is also well known, computing a Gröbner basis in lexicographic order is computationally highly intensive. Building on the work of the second author [G. Viry in: EUROSAM 84, Symbolic and algebraic computation, Proc. Int. Symp., Cambridge 1984, Lect. Notes Comput. Sci. 174, 64-73 (1984; Zbl 0569.12003)] the authors present a way to simplify the system before computing the Gröbner basis. The new system is always solved over \(\mathbb{C}\) and the solutions of the simplified system correspond to solutions to the original system, all of whose coordinates are non-zero. [Reviewer’s remark: The authors point out that setting one or more variables to 0 before simplification allows one to search for solutions lying on the coordinate hyperplanes. This works well as long as \(n\), the number of variables in \(A\), is relatively small.]
The simplified system is obtained from the original one by an automorphism determined by finding a minimum vector in the lattice associated with a matrix whose rows are of two forms: row ‘\(l_i\)’ is a vector of the exponents of \(x_i\) in each monomial appearing in the polynomials of the system; row ‘\(e_j\)’ is the vector \((0,\dots, 0,{1\over 2},\dots,{1\over 2},0, \dots,0)\), where the sequence of \({1\over 2}\)’s is at the locations corresponding to the monomials in polynomial \(P_j\) of the system. (The authors’ examples make this very clear.)
The authors give an example of a system which, before simplification was still running after an hour using Maple on a 300 Mhz sparc ultra, but which took under 1 minute after simplification.