#696 closed enhancement (duplicate)
SAGE's multivariate gcd sucks over QQ and/or ZZ
Reported by: | was | Owned by: | somebody |
---|---|---|---|
Priority: | major | Milestone: | sage-duplicate/invalid/wontfix |
Component: | basic arithmetic | Keywords: | |
Cc: | Merged in: | ||
Authors: | Reviewers: | ||
Report Upstream: | Work issues: | ||
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description
I think those timings are way out of date, since Singular 3 seems to be *very* fast at mod p multivariate GCD computation, even though it sucks over QQ. Check out this paper: http://www.cecm.sfu.ca/CAG/papers/brown.ps It on exactly the problem of GCD over QQ (or equiv ZZ), and section 2 has a complete description of a gcd algorithm that reduces gcd over ZZ to doing gcd's mod p. Who wants to be a hero -- like Jon Bober and number of partitions -- and implement this for Sage, so that multivariate GCD's aren't embarrassingly slow in Sage anymore? This slowness *has* been something reported to me on several occasions during the last 2 years. William
NOTE -- I would implement this modular GCD algorithm in Sage, not Singular.
I would also investigate other algorithms mentioned in the paper.
Change History (2)
comment:1 Changed 14 years ago by
- Resolution set to duplicate
- Status changed from new to closed
comment:2 Changed 14 years ago by
- Milestone changed from Sage-2.10 to sage-duplicate
Note: See
TracTickets for help on using
tickets.
See #694 instead!