9.
We present a bounded probability algorithm for the computation of the
Chowforms of the equidimensional components of an algebraic variety. In particular,
this gives an alternative procedure for the effective equidimensional decomposition
of the variety, since each equidimensional component is characterized by its Chow
form.
The expected complexity of the algorithm is polynomial in the size and the geometric
degree of the input equation system defining the variety. Hence it improves (or
meets in some special cases) the complexity of all previous algorithms for computing Chow forms. In addition to this, we clarify the probability and uniformity aspects,
which constitutes a further contribution of the paper.
The algorithm is based on elimination theory techniques, in line with the geometric
resolution algorithm due to M. Giusti, J. Heintz, L. M. Pardo, and their collaborators.
In fact, ours can be considered as an extension of their algorithm for zero-dimensional
systems to the case of positive-dimensional varieties. The key element for dealing
with positive-dimensional varieties is a new Poisson-type product formula. This
formula allows us to compute the Chow form of an equidimensional variety from a
suitable zero-dimensional fiber.
As an application, we obtain an algorithm to compute a subclass of sparse resultants,
whose complexity is polynomial in the dimension and the volume of the input
set of exponents. As another application, we derive an algorithm for the computation
of the (unique) solution of a generic overdetermined polynomial equation system.
相似文献