On Computing the Resultant of Generic Bivariate Polynomials

International audienceAn algorithm is presented for computing the resultant of two generic bivariate polynomials over a field K. For such p and q in K[x, y] both of degree d in x and n in y, the algorithm computes the resultant with respect to y using (n^(2−1/ω) d)^(1+o(1)) arithmetic operations in K, where two n × n matrices are multiplied using O (n^ω) operations. Previous algorithms required time (n^2 d)^(1+o(1)). The resultant is the determinant of the Sylvester matrix S (x) of p and q, which is an n × n Toeplitz-like polynomial matrix of degree d. We use a blocking technique and exploit the structure of S (x) for reducing the determinant computation to the computation of a matrix fraction description R(x)Q (x)^(−1) of an m ×m submatrix of the inverse S (x)^(−1) , where m ≪ n. We rely on fast algorithms for handling dense polynomial matrices: the fraction description is obtained from an x-adic expansion via matrix fraction reconstruction, and the resultant as the determinant of the denominator matrix. We also describe some extensions of the approach to the computation of generic Gröbner bases and of characteristic polynomials of generic structured matrices and in univariate quotient algebras