Project

General

Profile

Slug #1517

RandomLinearForm

Added by John Abbott over 3 years ago. Updated about 2 years ago.

Status:
Closed
Priority:
Low
Assignee:
John Abbott
Category:
Improving
Target version:
CoCoALib-0.99800
Start date:
23 Oct 2020
Due date:
% Done:

100%

Estimated time:
0.90 h
Spent time:
0.90 h

Description

The profiler tells me that RandomLinearForm spends most (almost all!) of its time in operator+=.

If the indets are ordered nicely (how can we know this?) then it may be better to use PushFront?

Anyway, RandomLinearForm is disappointingly slow in the test example from issue #1514 (with 1000 indets)

Related issues

Related to CoCoALib - Feature #1169: New function: RandomLinearForm (CoCoALib)Closed2018-03-19

Related to CoCoALib - Bug #1208: New function: Threadsafe RandomLinearForm (CoCoALib)New2018-08-02

History

#1 Updated by John Abbott over 3 years ago

  • Related to Feature #1169: New function: RandomLinearForm (CoCoALib) added

#2 Updated by John Abbott over 3 years ago

  • Related to Bug #1208: New function: Threadsafe RandomLinearForm (CoCoALib) added

#3 Updated by John Abbott over 3 years ago

  • Priority changed from Normal to Low

It could be that the problem is simply copying lots of PPs (each occupying 4000 bytes).
Could the memory manager be a bottleneck?

It would be nice to make it faster...

Source code: SparsePolyOps-RingElem.C around line 148

STRANGE operator+= seems to be calling CoCoA::RingDistrMPolyInlFpPPImpl::myAdd which would copy the whole poly, right?

#4 Updated by John Abbott over 3 years ago

  • Description updated (diff)
  • Status changed from New to In Progress
  • % Done changed from 0 to 10

The empirical complexity appears to be quadratic. Here is my test:

nvars := 40000;
use P ::= ZZ/(29641)[x[1..nvars]];
t0 := CpuTime();
l := RandomLinearForm(P);
TimeFrom(t0);

With nvars=20000 the time was about 1.15s; with nvars=40000 the time was about 4.4s.

With our dense repr for ordvs, the memory consumption is also essentially quadratic.

It might be faster with PPMonoidSparse... I wonder what state that code is in?

#5 Updated by John Abbott over 3 years ago

  • % Done changed from 10 to 50

I presume the timings in comment 4 were with unsigned short as SmallExponent_t (otherwise CoCoA has suddenly become slower by a factor of 2).

RandomLinearForm is definitely faster in CoCoALib, and the time taken is super-linear in the number of indets; but I cannot go far, because with 50000 indets the process dies spontaneously after reaching about 16Gb RAM -- why???

Anyway, since the memory requirement is quadratic there is no hope to make it much faster... perhaps it is not that important anyway?

#6 Updated by John Abbott about 2 years ago

  • Status changed from In Progress to Closed
  • Assignee set to John Abbott
  • % Done changed from 50 to 100
  • Estimated time set to 0.90 h

The code works. If there is a real use-case where the low speed is a problem then we can create a new issue.
I think we can just close this... I doubt it is that important (and it just clutters up the list of open issues).

Also available in: Atom PDF