Project

General

Profile

Feature #987

GCD: add special case if args are monomials

Added by John Abbott over 7 years ago. Updated over 7 years ago.

Status:
New
Priority:
Normal
Assignee:
-
Category:
Improving
Target version:
CoCoALib-1.0
Start date:
28 Nov 2016
Due date:
% Done:

0%

Estimated time:
Spent time:
0.25 h

Description

While trying to comprehend the (undocumented) code I wrote in ArithGroup.cpkg5, I noticed a comment about GCD being very slow for monomials over a finite field (because it drops through to the general syzygy method).

Add a special case: perhaps not hugely useful, but should be fairly easy to implement.

Related issues

Related to CoCoALib - Slug #129: Better GCDNew2012-04-15

History

#1 Updated by John Abbott over 7 years ago

The relevant place in the code seems to be in SparsePolyRing.C:814.

To see how slow the current code is, try the following:

f := x+y+z;
g := f^256; --> has 33153 terms
lcm(support(g)); --> takes about 1.1s

use ZZ/(32003)[x,y,z];
f := x+y+z;
g := f^256; --> has 33153 terms
lcm(support(g)); --> takes ages (36s)

#2 Updated by John Abbott over 7 years ago

Also available in: Atom PDF