Opened 5 years ago
Last modified 11 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
- 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
- Commit set to 2ec35c2f20fb54ff648e253c79ac78a6cb76c05d
comment:3 Changed 5 years ago by
- Milestone changed from sage-6.3 to sage-6.4
comment:4 Changed 11 months ago by
- Status changed from new to needs_info
What's the status of this? Does this need review?
See #12174 for a similar issue.
New commits:
first versionworking implementationSpeedup of resultant of bivariate polynomials over the rationals.