Paper Info
Title
On Computing The Resultant Of Generic Bivariate Polynomials
Abstract
An 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/omega) d)(1+o)(1) arithmetic operations in K, where two n x n matrices are multiplied using O(n(omega)) 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 x 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 anm x 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 Grobner bases and of characteristic polynomials of generic structured matrices and in univariate quotient algebras.
Year
DOI
Venue
2018
10.1145/3208976.3209020
ISSAC'18: PROCEEDINGS OF THE 2018 ACM INTERNATIONAL SYMPOSIUM ON SYMBOLIC AND ALGEBRAIC COMPUTATION
Field
DocType
Citations 
Characteristic polynomial,Inverse,Discrete mathematics,Combinatorics,Polynomial,Polynomial matrix,Matrix (mathematics),Computer science,Quotient,Toeplitz matrix,Sylvester matrix
Conference
1
PageRank 
References 
Authors
0.37
7
1
Name
Order
Citations
PageRank
Gilles Villard156548.04