We 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 Ti,..., Te and polynomial
sets U,.....Ue such that Zero(lP/Q) = (JJ=J Zero(Ti/HJ,-), where Zero(F/Q) denotes
the set of common zeros of the polynomials in F' 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 ZerofTj/U,) ф 0 for each t. One of them, for which the computed triangular systems [Ti, 4J;] 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. Л few encouraging examples are given in detail for illustration.
1. Introduction
The procedures of triangularizing systems of multivariate (differential) polynomials by successively eliminating the variables are called elimination methods. The development of elimination methods and their underlying theory has a long history in mathematics. It may be traced back to the Chinese matrix method for linear systems described in Chiu Chang Suan Shu early in the first century (cf. Needham, 1959 and Boyer, 1968). This method was further developed by Chinese algebraists, leading to the method of Thien Yuan for general polynomial systems in the medieval centuries. Several elimination methods have appeared in the European literature since the 18th century. They include the early methods of Euler (1840) and Bezout, the well known method of Gauss (1873) and the dialytic method of Sylvester (1904). Among these methods, the last was generalized late on as resultant theory by other British mathematicians including Cayley, Macaulay (1916), Hodge fa Pedoe (1947) and is for general polynomial systems, while the others are merely for linear systems. Two remarkable elimination methods, one associated with the concept of characteristic sets (Ritt, 1932, 1950, Wu, 1984a, 1986) and the other with Grobner bases (Buchberger, 1970,1985), were developed in this century and have received much attention recently in the area of symbolic computation. A fundamental application of elimination methods is to soive systems of polynomial equations, which is of practical
