Speedup resultant of multivariate polynomials

miguelmarco commented 10 years ago

Up to now we rely on singular to compute resultants of multivariate polynomials. There are faster ways.

Even computing the determinant of the sylvester matrix is usually (much) faster.

First i have implemented a trick for bivariate polynomials over the rationals (it could in principle work over any field with enough elements, but it is not clear that it is faster there). The trick consists on specialicing for several values of the surviving variable, compute the (univariate) resultant for them, and then reconstruct by lagrange interpolation.

It would also be worth to perform some benchmarks, and deduce a heuristic for the cases where the current method is beaten by the sylvester matrix determinant.

CC: @saraedum

Component: algebra

Keywords: resultant, discriminant, polynomial, multivariate

Author: Miguel Marco

Branch/Commit: u/mmarco/ticket/16749 @ 2ec35c2

Issue created by migration from https://trac.sagemath.org/ticket/16749

miguelmarco commented 10 years ago

Branch: u/mmarco/ticket/16749