"Solving Systems of Nonlinear Algebraic Equations 
     by Using the Groebner Walk Method and Its Improvements"

    Quoc-Nam Tran.
    Wolfram Research Inc.
    100 Trade Centre Dr.
    Champaign, IL, 61820
    USA
    E-mail:tqnam@wolfram.com
	
The method of Gr\"obner bases \cite{Buchberger65, Buchberger85} is one of 
the main tools for solving systems of nonlinear algebraic equations. 
In order to solve such a system, one has to compute a Gr\"obner basis with 
respect to an elimination term order, say pure lexicographic order. 
However, they are time and memory consuming to do so directly.

One way to overcome those difficulties is to partition the computation of 
the Gr\"obner basis into several smaller computations following a path in 
the Gr\"obner fan of the ideal generated by the system of equations. 
This approach of Collart et al. \cite{CKM96} is called the Gr\"obner walk 
method, which does not require any assumption about the dimension of the 
ideal. 
A crucial parameter to the performance of the Gr\"obner walk method is the 
choice of the walking path since the number of conversion steps and the 
complexity of each step heavily depend on it.

Ideally, the walking path should be free of the intersections of several 
cones since in this general position, the initial forms involve far fewer 
terms; therefore, the transformations can be computed cheaply. As suggested 
in \cite{CKM96} and improved in \cite{AGK96, AmGl98}, it is appropriate 
to vary the starting point in order to ensure the generality of the position. 

However, the real difficulty comes from the target point, where one has to 
perform the last conversion with respect to the elimination term order but 
do not know how to vary the point. Typically, the target point lies on the 
intersection of very many cones, which ends up with the initial form of 
considerable number of terms. (We have many examples whose initial form has 
few hundred terms.) Therefore, it increases the complexity of the conversion 
since we have to compute a Gr\"obner basis with respect to the elimination 
term order of such a large initial form. Amrheim and Gloor in \cite{AmGl98} 
offer a heuristic way to guess a perturbed target point and check the validity 
after the conversion. But, if the heuristic guess fails than one has to 
compute the Gr\"obner basis with respect to the elimination term order of 
such a large initial form anyway.

In this paper, the author give a deterministic method to vary the target 
point in order to ensure the generality of the position, i.e. we always 
have just few terms in the initial forms. The main idea of the method is 
that eventhough we have not known the Gr\"obner basis with respect to the 
target cone yet, we know in advance how large the polynomials in the 
Gr\"obner basis can be. 
(See the full paper for the algorithm and the proof of correctness.)

It turns out that this theoretical result brings a dramatic speed up 
in practice. We have implemented the Gr\"obner walk method together 
with the deterministic method for varying the target point in the kernel 
of Mathematica. Our experiments show the superlative performance of our
improved Gr\"obner walk method in comparison with Buchberger's and 
"traditional" Gr\"obner walk algorithms. 
Our record is a speed up of 30,000 times faster than the direct 
computation of the reduced Gr\"obner basis with respect to pure 
lexicographic order (using the sugar cube strategy).

From my experiments, the improved Gr\"obner walk method can be competitive
with other well-known methods for conversion.