An Elimination Method for Polynomial Systems

AbstractWe present an elimination method for polynomial systems, in the form of three main algorithms. For any given system [P,Q] of two sets of multivariate polynomials, one of the algorithms computes a sequence of triangular forms T1,…,Te and polynomial sets U1,…,Ue such that Zero(P/Q) = ∪ei=1 Zero(Ti/Ui), where Zero(P/Q) denotes the set of common zeros of the polynomials in P which are not zeros of any polynomial in Q, and similarly for Zero(Ti/Ui). The two other algorithms compute the same zero decomposition but with nicer properties such as Zero(Ti/Ui) ≠ &0slash; for each i. One of them, for which the computed triangular systems [Ti, Ui] possess the projection property, provides a quantifier elimination procedure for algebraically closed fields. For the other, the computed triangular forms Ti are irreducible. The relationship between our method and some existing elimination methods is explained. Experimental data for a set of test examples by a draft implementation of the method are provided, and show that the efficiency of our method is comparable with that of some well-known methods. A few encouraging examples are given in detail for illustration