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:

Status badges

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)

gcd_slow.singular (45.4 KB) - added by was 14 years ago.
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.
6546.patch (3.2 KB) - added by malb 14 years ago.

Download all attachments as: .zip

Change History (9)

Changed 14 years ago by was

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.

comment:1 Changed 14 years ago by was

This paper describes the algorithm used in Singular:

http://portal.acm.org/citation.cfm?doid=800192.805698

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 was

  • Cc = added
  • Owner changed from somebody to jbmohler

comment:3 Changed 14 years ago by was

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 was

  • Milestone changed from Sage-2.10 to sage-2.9

Changed 14 years ago by malb

comment:5 Changed 14 years ago by malb

  • 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 mhansen

  • 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 was

  • Resolution set to fixed
  • Status changed from assigned to closed
Note: See TracTickets for help on using tickets.