"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.