Speedup resultant of multivariate polynomials

[miguelmarco]

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]

Branch: u/mmarco/ticket/16749

[saraedum]

Commit: 2ec35c2

[saraedum]

comment:2

See #12174 for a similar issue.

---

New commits:

0f2a4b7	first version
1e75183	working implementation
2ec35c2	Speedup of resultant of bivariate polynomials over the rationals.

[saraedum]

comment:4

What's the status of this? Does this need review?