Generalised characteristic polynomials
โ Scribed by John Canny
- Publisher
- Elsevier Science
- Year
- 1990
- Tongue
- English
- Weight
- 710 KB
- Volume
- 9
- Category
- Article
- ISSN
- 0747-7171
No coin nor oath required. For personal study only.
โฆ Synopsis
Multipolynomial resultants provide the most efficient methods known {in terms as asymptotic complexity) for solving certain systems of polynomial equations or eliminating variables {Bajaj et al., 1988). The resultant off1 ..... f~ in K[x 1 ..... xm] will be a polynomial in m-n+l variables which is zero when the system f~ = 0 has a solution in/(m (/( the algebraic closure of K). Thus the resultant defines a projection operator from/C" to/(~,,-,+1). However, resultants are only exact conditions for homogeneous systems, and in the affine ease just mentioned, the resultant may be zero even if the system has no affine solution. This is most serious when the solution set of the system of polynomials has "excess components" (components of dimension >m-n), which may not even be affine, since these cause the resultant to vanish identically. In this paper we describe a projection operator which is not identically zero, but which is guaranteed to vanish on all the proper (dimension = m-n) components of the system f~ = 0. Thus it fills the role of a general affine projection operator or variable elimination "black box" which can be used for arbitrary polynomial systems. The construction is based on a generalisation of the characteristic polynomial of a linear system to polynomial systems. As a corollary, we give a single-exponential time method for finding all the isolated solution points of a system of polynomials, even in the presence of infinitely many solutions at infinity or elsewhere.
๐ SIMILAR VOLUMES
For k a positive integer, we consider the problem of counting solutions x to the equation kx = 0, where x is to lie in a given subset K of a torus group. This problem is considered for three classes of subsets K.