Project

General

Profile

Slug #1118

SLUG: factorization of x^9999

Added by John Abbott over 6 years ago. Updated 3 months ago.

Status:
In Progress
Priority:
Low
Assignee:
-
Category:
Improving
Target version:
CoCoALib-0.99880
Start date:
08 Nov 2017
Due date:
% Done:

10%

Estimated time:
Spent time:
0.35 h

Description

CoCoA is slow at factorizing high powers of x. For example:

>>> t0 := CpuTime();  factor(x^99999); TimeFrom(t0);
record[RemainingFactor := 1, factors := [x], multiplicities := [99999]]
384.006

Complexity is quadratic in the exponent!

Related issues

Related to CoCoALib - Feature #1513: Better test for univariate-ness (and better conversion)New2020-10-19

History

#1 Updated by John Abbott over 3 years ago

I confirm that computation time increases quadratically (why?)
Also current (2020-10-19) speed is about the same as previously measured.

Better see what the profiler says...

#2 Updated by John Abbott over 3 years ago

  • Status changed from New to In Progress
  • Target version changed from CoCoALib-1.0 to CoCoALib-0.99850
  • % Done changed from 0 to 10

The quadratic behaviour derives from the GCD computation being between dense univariate polynomials.

A solution would be to have a "smarter" pseudo-sparse mapping to "dense univariate": namely, find exponents d and e such that f(x) = x^e * g(x^d).
These exponents can be found in linear time (in number of terms in the poly); indeed it could be combined with the recognition that the poly is univariate...
Perhaps this should be a separate issue?

#3 Updated by John Abbott over 3 years ago

  • Related to Feature #1513: Better test for univariate-ness (and better conversion) added

#4 Updated by John Abbott 3 months ago

  • Target version changed from CoCoALib-0.99850 to CoCoALib-0.99880

Also available in: Atom PDF