Project

General

Profile

Slug #1042

LF curiously slow (breaking a poly into homog pieces)

Added by John Abbott 11 months ago. Updated 4 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 11 months 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 11 months ago

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

#3 Updated by John Abbott 11 months 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 8 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 8 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 8 months ago

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

#7 Updated by John Abbott 8 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 4 months ago

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

#9 Updated by John Abbott 4 months ago

  • Estimated time set to 2.99 h

#10 Updated by John Abbott 4 months ago

Also available in: Atom PDF