High-order lifting for polynomial Sylvester matrices
Abstract
A new algorithm is presented for computing the resultant of two "sufficiently generic" bivariate polynomials over an arbitrary field. For such p and q in K[x, y] of degree d in x and n in y, the resultant with respect to y is computed using O(n^(1.458)d) arithmetic operations as long as d = O(n^(1/3)). For d = 1, the complexity estimate is therefore essentially reconciled with the best known estimates of Neiger et al. 2021 for the related problems of modular composition and characteristic polynomial in a univariate quotient algebra. This further allows to cross the 3/2 barrier in the exponent of n for the first time in the case of the resultant. More generally, our algorithm improves on best previous algebraic ones as long as d = O(n^(0.47)). The resultant is the determinant of the associated univariate polynomial Sylvester matrix of degree d, the problem is therefore intimately related to that of computing determinants of structured polynomial matrices. We first identify new advanced aspects of structure specific to the polynomial Sylvester matrix. Thanks to this, our contribution is to compute the determinant by successfully mixing the block baby steps/giant steps approach of Kaltofen and Villard 2005, until then restricted to the case d = 1 for characteristic polynomials, and the high-order lifting strategy of Storjohann 2003 usually reserved for dense polynomial matrices.
Origin : Files produced by the author(s)