Constructing Sylvester-type resultant matrices using the Dixon formulation

摘要

A new method for constructing Sylvester-type resultant matrices for multivariate elimination is proposed. Unlike sparse resultant constructions discussed recently in the literature or the Macaulay resultant construction, the proposed method does not explicitly use the support of a polynomial system in the construction. Instead, a multiplier set for each polynomial is obtained from the Dixon resultant formulation using an arbitrary term (or a polynomial) for the construction. As shown in the Proceedings of the ACM Symposium on Theory of Computing (1996), the generalized Dixon resultant formulation implicitly exploits the sparse structure of the polynomial system. As a result, the proposed construction for Sylvester-type resultant matrices is sparse in the sense that the matrix size is determined by the support structure of the polynomial system, instead of the total degree of the polynomial system. The proposed construction is a generalization of a related construction proposed by the authors in which the monomial 1 is used (RCWA' 00, Proceedings of the 7th Rhine Workshop (2000), 167). It is shown that any polynomial (with support inside or outside the support of the polynomial system) can be used instead insofar as that polynomial does not vanish on any of the common zeros of the polynomial system. For generic unmixed polynomial systems (in which every polynomial in the polynomial system has the same support, i.e., the same set of terms), it is shown that the choice of a polynomial does not affect the matrix size insofar as the terms in the polynomial also appear in the polynomial system. The main advantage of the proposed construction is for mixed polynomial systems. Supports of a mixed polynomial system can be translated so as to have a maximal overlap, and a polynomial is selected with support from the overlapped subset of translated supports. Determining an appropriate translation vector for each support and a term from the overlapped support can be formulated as an optimization problem. It is shown that under certain conditions on the supports of polynomials in a mixed polynomial system, a polynomial can be selected leading to a Dixon dialytic matrix of the smallest size, thus implying that the projection operator computed using the proposed construction is either the resultant or has an extraneous factor of minimal degree. The proposed construction is compared theoretically and empirically, on a number of examples, with other methods for generating Sylvester-type resultant matrices.