=ADD=
=reftype=
14
=number=
01-02
=url=
ftp://ftp.risc.uni-linz.ac.at/pub/techreports/2001/01-02.ps.gz
=year=
2001
=month=
01
=author=
Bikker; Piet
=title=
The B\'ezout Construction of the Resultant
=abstract=
A fast and robust algorithm is presented for the construction of the resultant
of a system of multivariate polynomial equations. The resultant of the typically
overdetermined system of $m + 1$ polynomials in $m$ indeterminates,
$$ f_1(x_1, \ldots, x_m) = 0, \ldots, f_{m + 1}(x_1, \ldots, x_m) = 0,
gives the necessary and sufficient condition, in terms of the coefficients, for
the existence of the common solution.

Based on ifrsd of B\'ezout and Poisson for solving polynomial systems by
resultants, a new resultant matrix construction is treated by two different
approaches.

One approach is based on a sequence of determinantal conditions that are
guaranteed to be satisfied in case of a generic polynomial system. These conditions
can be written as minors of the Macaulay matrix of the leading forms $f_1, \ldots, f_m$.
As a result a set of reducers is obtained. These are used to eliminate monomials
from non-constant multiples of $f_{m + 1}$, ending in a linear system that is consistent
in and only if the polynomial system posseses solutions.

The other approach uses Groebner basis techniques for the generation of the
resultant matrix. First, the Groebner basis of the ideal generated by $f_1, \ldots, f_m$
is constructed. With the help of the Groebner basis a set of monomials that are
linearly independent of the solutions is determined. The resultant matrix is the
coefficient matrix of the linear system obtained by the normal forms of the
multiplication of this basis by $f_{m + 1}$. The size of the matrix is the smallest among the
ones generated by the various resultant methods.

The obtained resultant matrix is called the B\'ezout matrix. In can be viewed as
a generalization of the B\'ezoutian different from the Dixon resultant matrix. It is
shown how to use the B\'ezout matrix to obtain all the components of the solutions.

Whereas other resultant formulations suffer from the sparsity and the algebraic
dependencies between the coefficients of the polynomial system giving so-called
extraneous factors and either non-square or singular matrices, this approach controls
all the exceptional cases. The suspicious factors that correspond to the
determinantal conditions of leading coefficients of Groebner basis elements are used to
exclude factors of the resultant from being extraneous. By this, all factors of the
true eliminant can be determined. The resultant matrix is allways square and its
singularity is shown to correspond to a vanishing resultant: no additional
investigation among the minors is needed.

The algorithm with the second approach was implemented for Maple and Asir.
Computational experiments show that the method is competitive with other fast
methods for solving polynomial systems, like FGLM and Dixon's resultant.
Especially for dense systems the method is superior. It turns out that the time needed
for the computation of the Groebner basis and the matrix construction is not the
new bottleneck. Still most of the time is used for the final determination evaluation.
=note=
PhD Thesis