Opened 14 years ago

Closed 14 years ago

Last modified 14 years ago

#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:

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

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 was

  • Resolution set to duplicate
  • Status changed from new to closed

See #694 instead!

comment:2 Changed 14 years ago by mabshoff

  • Milestone changed from Sage-2.10 to sage-duplicate
Note: See TracTickets for help on using tickets.