Project

General

Profile

Slug #1042

LF curiously slow (breaking a poly into homog pieces)

Added by John Abbott about 1 year ago. Updated 6 months ago.

Status:
Closed
Priority:
Low
Assignee:
Category:
Improving
Target version:
Start date:
10 Apr 2017
Due date:
% Done:

100%

Estimated time:
2.99 h
Spent time:

Description

The following loop is curiously slow:

    while (!IsZero(fpow2))
      fpow2 -= LF(fpow2);

Anna has already made an improvement, but it ought to be faster.


Related issues

Related to CoCoALib - Feature #1022: New "LF" function which is based on StdDegNew2017-03-06

Related to CoCoALib - Feature #1033: Split poly into homog partsClosed2017-03-17

History

#1 Updated by John Abbott about 1 year ago

Here is a complete example:

  RingElem CutLF(RingElem& f)
  {
    const SparsePolyRing& P = owner(f);
    if (IsZero(f)) return f;
    RingElem ans(P);
    do
    {
      P->myMoveLMToBack(raw(ans), raw(f));
    }
    while (!IsZero(f) && (CmpWDeg(LPP(f), LPP(ans)) == 0));
    return ans;
  }

  void program()
  {
    GlobalManager CoCoAFoundations;

    ring P = NewPolyRing(RingQQ(), symbols("x,y,z"));
    RingElem f = ReadExpr(P,"x+y+z+1");
    RingElem fpow = power(f,199);
    RingElem fpow2 = fpow;
    const long n = NumTerms(fpow);
    long count = 0;
    // LOOP 1:
    double t0 = CpuTime();
    while (!IsZero(fpow))
    {
      RingElem lffpow = CutLF(fpow);
      count += NumTerms(lffpow);
    }
    cout << "loop1 time: " << CpuTime() - t0 << endl;
    cout << count -  n << endl;

    // LOOP 2:
    double t1 = CpuTime();
    while (!IsZero(fpow2))
      fpow2 -= LF(fpow2);
    cout << "loop2 time: " << CpuTime() - t1 << endl;
  }

LOOP 1 takes about 0.5s
LOOP 2 takes about 25s
While LOOP 2 will be slower because it is allocating memory, a factor of about 50 seems excessive.

#2 Updated by John Abbott about 1 year ago

  • Related to Feature #1022: New "LF" function which is based on StdDeg added

#3 Updated by John Abbott about 1 year ago

I think this issue is relatively unimportant, hence the "low" priority.
I have put it on redmine just so that we do not forget it.

#4 Updated by John Abbott 10 months ago

  • Status changed from New to Resolved
  • Assignee set to John Abbott
  • % Done changed from 0 to 80

I have checked in my implementation (almost the same as the one above, plus some arg checking).

QUESTION what should CutLF do if passed a zero poly as arg? Note that LF gives error.

#5 Updated by John Abbott 10 months ago

There was also a question about the name: I have called it CutLF. Another possibility could be MoveLF similar to MoveLM? This would require 2 args, one being the destination (and what should happen if the destination is not zero or in the wrong ring?)

#6 Updated by John Abbott 10 months ago

  • Target version changed from CoCoALib-0.99999 to CoCoALib-0.99560

#7 Updated by John Abbott 10 months ago

After some reflection and after chatting to Anna we have decided that CutLF should also give an error (like LF) when the arg is zero. I will check in shortly.

#8 Updated by John Abbott 6 months ago

  • Status changed from Resolved to Closed
  • % Done changed from 80 to 100

#9 Updated by John Abbott 6 months ago

  • Estimated time set to 2.99 h

#10 Updated by John Abbott 6 months ago

Also available in: Atom PDF