Resultant - Computation

Computation

Since the resultant depends polynomially (with integer coefficients) on the roots of P and Q, and it is invariant with respect to permutations of each set of roots, it must be possible to calculate it using an (integer) polynomial formula on the coefficients of P and Q. See elementary symmetric polynomial for details.

More concretely, the resultant is the determinant of the Sylvester matrix (and of the Bézout matrix) associated to P and Q.

The above definition of the resultant can be rewritten as

so it can be expressed polynomially in terms of the coefficients of Q. By the symmetry of the defining formula, this shows that the resultant is a polynomial expression of the coefficients of both P and Q.

This expression remains unchanged if Q is replaced by the remainder P mod Q of the Euclidean division of Q by P. If we set P' = P mod Q, then this idea can be continued by swapping the roles of P' and Q. However, P' has a set of roots different from that of P. This can be resolved by writing res(P',Q) as a determinant again, where P' has leading zero coefficients. This determinant can now be simplified by iterative expansion with respect to the column, where only the leading coefficient q of Q appears: res(P,Q)=qdegP-degP' res(P',Q). Continuing this procedure ends up in a variant of the Euclid's algorithm.

This procedure needs a number of arithmetic operations on the coefficients that is of the order of product of the degrees. However, when the coefficients are integers, rational numbers or polynomials, these arithmetic operations imply a number of GCD computations of coefficients which is of the same order and make the algorithm inefficient.

The subresultant pseudo-remainder sequences have been introduced to solve this problem and avoid any fraction and any GCD computation of coefficients. A more efficient algorithm is obtained by using the good behavior of the resultant under a ring homomorphism of the coefficients: to compute a resultant of two polynomials with integer coefficients, one computes their resultants modulo sufficiently many prime numbers, and then reconstruct the result with Chinese remainder theorem.