Opened 5 years ago

Last modified 19 months ago

#16749 needs_info enhancement

Speedup resultant of multivariate polynomials

Reported by: mmarco Owned by:
Priority: major Milestone: sage-6.4
Component: algebra Keywords: resultant, discriminant, polynomial, multivariate
Cc: saraedum Merged in:
Authors: Miguel Marco Reviewers:
Report Upstream: N/A Work issues:
Branch: u/mmarco/ticket/16749 (Commits) Commit: 2ec35c2f20fb54ff648e253c79ac78a6cb76c05d
Dependencies: Stopgaps:

Description

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.

Change History (4)

comment:1 Changed 5 years ago by mmarco

  • Branch set to u/mmarco/ticket/16749
  • Created changed from 08/01/14 19:37:19 to 08/01/14 19:37:19
  • Modified changed from 08/01/14 19:37:19 to 08/01/14 19:37:19

comment:2 Changed 5 years ago by saraedum

  • Commit set to 2ec35c2f20fb54ff648e253c79ac78a6cb76c05d

See #12174 for a similar issue.


New commits:

0f2a4b7first version
1e75183working implementation
2ec35c2Speedup of resultant of bivariate polynomials over the rationals.

comment:3 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:4 Changed 19 months ago by saraedum

  • Status changed from new to needs_info

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

Note: See TracTickets for help on using tickets.