Feature #1488: BuiltIn Interreduce-Function - CoCoALib - CoCoA Project

Feature #1488

BuiltIn Interreduce-Function

Added by Julian Danner over 3 years ago. Updated about 1 year ago.

Status:

Closed

Priority:

High

Assignee:

John Abbott

Category:

New Function

Target version:

CoCoALib-0.99850

Start date:

15 Sep 2020

Due date:

% Done:

100%

Estimated time:

Spent time:

3.25 h

Description

The function interreduce is implemented in CoCoA-5, and the implementation (NotBuiltin.cpkg5) can be translated into C++ in a straightforward way. Below you can find such an implementation which I am already using for more than a year. It is well-tested for lists of polynomials. (As I did not know where to put it best, I just added it to src/CoCoA-5/BuiltInFunctions-CoCoALib.C.)

DECLARE_STD_BUILTIN_FUNCTION(ir, 1) { //InterReduce-function added by Danner May'19
  intrusive_ptr<RightValue> w = runtimeEnv->evalArgAs<LIST>(ARG(0));
  vector<RingElem> v = runtimeEnv->evalRVAsListOfRingElem(w, ARG(0));

  //ensure v is not an empty list
  if (v.empty()) {
    return Value::from(v);
  }
  //delete possible zeros in v
  v.erase(std::remove(v.begin(), v.end(), v[0]-v[0]),v.end()); //v[0]-v[0]=0 in the correct ring.

  vector<RingElem> ans;
  RingElem rem;
  int count=0;
  bool newLPPfound=true;
  while(newLPPfound){
    ans=vector<RingElem>();
    if(VerbosityLevel()>=90){printf("interreduced: round n.%i\n", ++count);}
    newLPPfound=false;
    sort(v.begin(), v.end(), [](RingElem elem1, RingElem elem2) {return LPP(elem1)<LPP(elem2);} );
    for(vector<RingElem>::const_iterator it=v.begin(); it!=v.end(); ++it){
      CheckForInterrupt("interreduction");
      rem=NR(*it,ans);
      if(!IsZero(rem)) {
          ans.push_back(rem);
          if(!newLPPfound && LPP(rem)!=LPP(*it)){
              newLPPfound=true;
          }
      }
    }
    v=ans;
  }
  //result is stored in ans
  return Value::from(ans);
}
END_STD_BUILTIN_FUNCTION

It would be nice to officially get it in CoCoA-Lib ;)

Related issues

History

#1 Updated by John Abbott over 3 years ago

Category set to New Function
Status changed from New to In Progress
Target version set to CoCoALib-0.99800
% Done changed from 0 to 10

Here is my revised version of the source code. It could surely be made faster, but this version is relatively simple and "obviously works".

  std::vector<RingElem> INTERRED(std::vector<RingElem> v)
  {
    if (v.empty()) { return v; } // ??? or error???
// BUG:  MUST check that all ringelems are in same ring...
    const char* const FnName = "INTERRED";
    VerboseLog VERBOSE(FnName);
    //delete possible zeros in v
    const ring& P = owner(v[0]);
    v.erase(std::remove(v.begin(), v.end(), zero(P)), v.end());

    int count = 0; // BUG?  int or long?
    while (true)
    {
      VERBOSE(90) << "round " << ++count << endl; // NB *always* incrs count!
      const auto CompareLPPs = [](const RingElem& f, const RingElem& g) { return LPP(f)<LPP(g); };
      sort(v.begin(), v.end(), CompareLPPs);

      vector<RingElem> ans;
      RingElem rem;
      bool newLPPfound = false;
      for (const auto& f: v)
      {
        CheckForInterrupt(FnName);
        rem = NR(f,ans);
        if (IsZero(rem)) continue;
        ans.push_back(rem);
        if (!newLPPfound && LPP(rem) != LPP(f))
          newLPPfound = true;
      }
      if (!newLPPfound) return ans;
      swap(v,ans); // quicker than: v = ans;
    }
  }

#2 Updated by John Abbott over 3 years ago

% Done changed from 10 to 20

I have now put my version of the impl in a new file SparsePolyOps-interreduce.C with corresponding header file.

What name should the function have? And what exactly should its semantics be?
Currently it is called interreduce and it computes a new list of polys which is interreduced (the original list is unaffected).

I have not written any doc yet... because we need to answer the 2 questions above first.

NOTE: right the CoCoALib fn is called interreduce but it corresponds to the CoCoA function interreduced :-(

#3 Updated by John Abbott over 3 years ago

Might it be useful to sort elements inside the interreduction loop according to a more "sophisticated" ordering: e.g.
all monomials are less than all binomials
all binomials are less than all polys with at least 3 terms
within each category (monomial, binomial, longer) sort by LPP

The main operation is NR; is it permitted to rescale the result by a convenient constant?
I tried giving as input a list of random univariates, the result was a single polynomial with LPP=1 (as expected), but the leading coefficient was "nasty".

#4 Updated by John Abbott over 3 years ago

Related to Feature #1405: New fn: interreduction added

#5 Updated by John Abbott over 3 years ago

Status changed from In Progress to Resolved
Assignee set to John Abbott
% Done changed from 20 to 70

The function is called interreduced: it returns an interreduced copy of the original list (which is not changed).

The function interreduce can be implemented as

void interreduce(std::vector<RingElem>& v) { swap(v, interreduced(v)); }

I do not see any way of doing this better and exception-safely.

QUESTION Should the "smarts" in comment 3 be made into a new issue, or is it simply not that important?

#6 Updated by John Abbott over 3 years ago

I have commented out interreduce.
I have renamed the files to SparsePolyOps-interreduced.

NOT YET DOCUMENTED
Where should the doc go? See also #1510

#7 Updated by Anna Maria Bigatti about 3 years ago

John Abbott wrote:

I have commented out interreduce.
I have renamed the files to SparsePolyOps-interreduced.

NOT YET DOCUMENTED
Where should the doc go? See also #1510

This is for me...

#8 Updated by Anna Maria Bigatti about 3 years ago

% Done changed from 70 to 80

#9 Updated by John Abbott over 2 years ago

Related to Support #1510: Documentation for SparsePolyOps? added

#10 Updated by John Abbott over 2 years ago

Status changed from Resolved to Feedback
% Done changed from 80 to 90

Is there documentation now?

#11 Updated by John Abbott over 2 years ago

Related to Design #1642: interreduce: make monic if over finite field? added

#12 Updated by John Abbott about 2 years ago

This is still not documented -- Anna can you do this?

Should the code be put into SparsePolyOps-vector?
Presumably doc should either be in SparsePolyOps (or SparsePolyOps-vector if that file has separate doc).

#13 Updated by John Abbott about 2 years ago

Target version changed from CoCoALib-0.99800 to CoCoALib-0.99850

#14 Updated by John Abbott about 2 years ago

Related to Design #1649: Add file SparsePolyOps-vector.C added

#15 Updated by John Abbott over 1 year ago

Priority changed from Normal to High

Anna! Please document and close this issue!

#16 Updated by Anna Maria Bigatti over 1 year ago

Description updated (diff)

#17 Updated by Anna Maria Bigatti over 1 year ago

Reminder for me: write doc for CoCoALib (and check manual for CoCoA-5)

#18 Updated by Anna Maria Bigatti over 1 year ago

Anna Maria Bigatti wrote:

Reminder for me: write doc for CoCoALib (and check manual for CoCoA-5)

Create the documentation file SparsePolyOps-vector.txt

#19 Updated by John Abbott about 1 year ago

Anna?

#20 Updated by Anna Maria Bigatti about 1 year ago

Status changed from Feedback to Closed
% Done changed from 90 to 100