Consider two polynomials $f,g\in\mathbb{F}_2$ of degree $O(2^n)$, with the property that they are extremely sparse (say, only $O(n)$ of the coefficients are non-zero). Is there a way to calculate their resultant that does not involve an exponential computation in $n$? The Sylvester matrix would be very structured (more than it is already), but I don't know if there are methods to exploit this structure to compute its determinant.

In a more general context, I'm using the resultant to check if $f$ and $g$ share a root. Is there another method to check this, considering the sparsity property?


See the oevre of I. Emiris:

Emiris, Ioannis Z.; Pan, Victor Y., Improved algorithms for computing determinants and resultants, J. Complexity 21, No. 1, 43-71 (2005). ZBL1101.68981.

Jeronimo, Gabriela; Sabia, Juan, Sparse resultants and straight-line programs, ZBL06825747.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.