Project

General

Profile

Slug #129

Better GCD

Added by John Abbott about 12 years ago. Updated almost 10 years ago.

Status:
New
Priority:
Normal
Assignee:
-
Category:
New Function
Target version:
CoCoALib-1.0
Start date:
15 Apr 2012
Due date:
% Done:

0%

Estimated time:
15.00 h
Spent time:
4.75 h

Description

Currently CoCoALib computes GCDs using GBasis/syzygy computations. This is often terribly slow -- there is faster code in CoCoA 4 for certain special cases. This faster code should be called whenever possible.

Related issues

Related to CoCoALib - Feature #127: Convert DUPFF code to C++In Progress2012-04-05

Related to CoCoALib - Slug #675: Matrix determinant over multivariate poly ringIn Progress2015-03-28

Related to CoCoA-5 - Slug #480: gcd too slow for large degree univariate polyNew2014-03-18

Related to CoCoALib - Slug #952: GCD very slowClosed2016-10-25

Related to CoCoALib - Feature #987: GCD: add special case if args are monomialsNew2016-11-28

Related to CoCoALib - Slug #1359: gcd: low degree but big coeffs can be slowNew2019-10-30

History

#1 Updated by John Abbott about 12 years ago

Implemented a first version where some GCD computations are passed to the old CoCoA-4 code. It is a poor implementation (uses globals, leaks memory).

Speed gain was disappointing for multivariate over QQ.
Good speed gain for univariate over small Fp.

#2 Updated by John Abbott almost 12 years ago

I cleaned the code so that it leaks less memory now.
The cleaning was a consequence of some other development.

#3 Updated by John Abbott over 11 years ago

(copied from some old handwritten notes)

GCD univ over QQ and ZZ (with normalization)
............. Fp (..................)
.............. other (???)

Multivariate over QQ and ZZ
................. Fp
................. other

C4 uses builtin if char=0, o/w uses syzygies.

#4 Updated by Anna Maria Bigatti about 10 years ago

  • Target version set to CoCoALib-0.99533 Easter14

#5 Updated by Anna Maria Bigatti about 10 years ago

  • Category set to New Function

#6 Updated by John Abbott about 10 years ago

  • Target version changed from CoCoALib-0.99533 Easter14 to CoCoALib-0.99534 Seoul14

#7 Updated by John Abbott almost 10 years ago

  • Target version changed from CoCoALib-0.99534 Seoul14 to CoCoALib-1.0

#8 Updated by John Abbott over 7 years ago

  • Related to Slug #480: gcd too slow for large degree univariate poly added

#9 Updated by John Abbott over 7 years ago

#10 Updated by John Abbott over 7 years ago

  • Related to Feature #987: GCD: add special case if args are monomials added

#11 Updated by John Abbott over 4 years ago

  • Related to Slug #1359: gcd: low degree but big coeffs can be slow added

Also available in: Atom PDF