Project

General

Profile

Slug #480

gcd too slow for large degree univariate poly

Added by John Abbott about 10 years ago. Updated over 4 years ago.

Status:
New
Priority:
Normal
Assignee:
-
Category:
Cleaning
Target version:
CoCoA-5.?.?
Start date:
18 Mar 2014
Due date:
% Done:

0%

Estimated time:
Spent time:
0.20 h

Description

CoCoA-5 used more than 6Gbytes of memory while trying to compute gcd(f,x^(31^6)-x) in ZZ/(31)[x] where f := x^15 +x^14 +x^13 +x^12 -x^11 -x^10 -x^7 -x^6 -x^3 +x^2 +x +1

Why so much memory? Was it using a dense representation?

Related issues

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

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

Related to CoCoALib - Feature #257: Transcribe C4 code for GCD in QQ[x]New2012-10-09

History

#1 Updated by Anna Maria Bigatti about 10 years ago

  • Target version set to CoCoA-5.1.0 Easter14

#2 Updated by John Abbott about 10 years ago

  • Target version changed from CoCoA-5.1.0 Easter14 to CoCoA-5.?.?

#3 Updated by John Abbott over 7 years ago

#4 Updated by John Abbott over 7 years ago

#5 Updated by John Abbott over 7 years ago

  • Related to Feature #257: Transcribe C4 code for GCD in QQ[x] added

#6 Updated by John Abbott over 4 years ago

This slug still exists: on my current machine, top reports that CoCoA-5 is using 13Gbyte of memory. The computation completed in about 131s.

No doubt it is using a dense repr. Perhaps there should be special handling if there is a large disparity in degree?

The speed is not ideal, but the memory consumption is embarrassing.

Also available in: Atom PDF