Opened 14 years ago
Closed 14 years ago
#694 closed enhancement (fixed)
[with patch] SAGE's multivariate gcd sucks over QQ and/or ZZ
Reported by: | was | Owned by: | malb |
---|---|---|---|
Priority: | major | Milestone: | sage-2.8.6 |
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
Attachments (2)
Change History (9)
Changed 14 years ago by
comment:1 Changed 14 years ago by
This paper describes the algorithm used in Singular:
Jack Schmidt claims the paper I mention above is a dead end for this problem:
Careful to check the papers. The Moses, et al. paper for singular shows that Brown's method is ineffective for your problem, and it is reasonably likely that this modified Brown method of Kaltofen et al. is also ineffective. The Kaltofen, et al. paper avoids the question of exponential runtime by restricting to bivariate dense polynomials. The Wang paper describes one major improvement in a reasonable common corner case for singular's algorithm. One presumes singular can be asked to describe what it is doing during its EZ-GCD calculation, and you can check if you are in this corner case. Wang's EEZ-GCD may be the better solution, and one should be able to implement a prototype of this quickly in the singular language. At any rate, it may be better to look for improvements to EZ-GCD than for the modular gcd.
EZ-GCD is also a modular/p-adic algorithm, so it should benefit from various fast mod-p gcd.
comment:2 Changed 14 years ago by
- Cc = added
- Owner changed from somebody to jbmohler
comment:3 Changed 14 years ago by
This is basically fixed (as soon as we upgrade to the newer singular). From the Singular team:
"hannes@mathematik.uni-kl.de" to me, joel, sage-devel, singular-team show details 8:40 am (49 minutes ago) Dear sage-devel readers, following the discussion on sage-devel last week we implemented a modular approach to compute the multivariate gcd over QQ in Singular. We still need to develop the heuristic when to prefer EZGCD or the modular method: currently, the modular method is prefered - this is not too bad: the posted examples goes from several minutes to 1 sec running time. These changes are inlcuded in ftp://www.mathematik.uni-kl.de/pub/Math/Singular/src/3-0-3/Singular-3-0-3-1.tar.gz Hans PS: the timings at http://magma.maths.usyd.edu.au/users/allan/gcdcomp.html (originally from http://home.bway.net/lewis/fermat/gcdcomp) are questionable as they refer also to computations in characteristic 43051 in Singular 2.0.4, which it did not support.
comment:4 Changed 14 years ago by
- Milestone changed from Sage-2.10 to sage-2.9
Changed 14 years ago by
comment:5 Changed 14 years ago by
- Milestone changed from sage-2.9 to sage-2.8.6
- Owner changed from jbmohler to malb
- Status changed from new to assigned
Attached is a patch (6546) which makes use of the new SINGULAR spkg found at
http://sage.math.washington.edu/home/malb/pkgs/singular-3-0-3-1-20070929.spkg
which provides a multimodular GCD.
comment:6 Changed 14 years ago by
- Summary changed from SAGE's multivariate gcd sucks over QQ and/or ZZ to [with patch] SAGE's multivariate gcd sucks over QQ and/or ZZ
comment:7 Changed 14 years ago by
- Resolution set to fixed
- Status changed from assigned to closed
Note: See
TracTickets for help on using
tickets.
this file has the singular input of a multivariate polynomial gcd that takes *minutes* in SAGE over QQ, but mod p the same takes 0.08 seconds.