twoSidedReduction() [2/2]

auto NCGroebner::twoSidedReduction

(

const Poly *

reducee

)

const->Poly *

Definition at line 254 of file NCGroebner.cpp.

{
  // stats for benchmarking, debug only...
  size_t loop_count = 0;
  size_t nterms = 0; // number of terms added in to the heap
 
  // easy access to variables in the class
  const FreeAlgebra& A{ freeAlgebra() };
  const PolyList& reducers{ currentValue() };
  const WordTable& W{ mWordTable };
  //const SuffixTree& W{ mWordTable };
  
  // pair will be (i,j) where the ith word in wordtable appears in word in position j
  std::pair<int,int> subwordPos; 
  Word leftWord, rightWord;
 
  Poly* remainder = new Poly;
  Poly tmp; // temp polynomial for seeing what is being added to heap.
 
  mHeap->clear();
  nterms += reducee->numTerms();
  mHeap->addPolynomial(*reducee);
 
  FreeMonoidLogger::reset();
 
  while (not mHeap->isZero())
    {
      loop_count++;
      
      // Find (left, right, index) s.t. left*reducers[index]*right == leadMonomial(reduceeSoFar).
      Word reduceeLeadWord;
      std::pair<Monom, ring_elem> LT { mHeap->viewLeadTerm() };
 
      A.monoid().wordFromMonom(reduceeLeadWord, LT.first);
 
      if (W.subword(reduceeLeadWord,subwordPos))
        {
          // If there is one, perform reduceeSoFar -= coef * left * reducers[index] * right
          A.monoid().wordPrefixFromMonom(leftWord, LT.first, subwordPos.second);
          A.monoid().wordSuffixFromMonom(rightWord, LT.first, W[subwordPos.first].size()+subwordPos.second);
 
          ring_elem c = A.coefficientRing()->negate(LT.second);
          ring_elem d = reducers[subwordPos.first]->cbegin().coeff();
          // TODO: Check to see if d is a unit before inverting.
          auto coeffNeeded = A.coefficientRing()->divide(c,d);
          
          A.clear(tmp);
          A.mult_by_term_left_and_right(tmp,
                                        *reducers[subwordPos.first],
                                        coeffNeeded, 
                                        leftWord, 
                                        rightWord);
          nterms += tmp.numTerms();
          mHeap->addPolynomial(tmp);
        }
      else
        {
          // If none, copy that term to the remainder (use add_to_end)
          // and subtract that term
          A.add_to_end(*remainder, LT.second, LT.first);
          mHeap->removeLeadTerm();
        }
    }
  if (M2_gbTrace >= 5)
    {
      std::cout << "reduction: " << "#steps: " << loop_count << " " << FreeMonoidLogger() << std::endl;
      std::cout << "           " << "#terms: " << nterms << std::endl;
      std::cout << "           " << AllocLogger() << std::endl;
    }
  return remainder;
}

References FreeAlgebra::add_to_end(), FreeAlgebra::clear(), FreeAlgebra::coefficientRing(), currentValue(), Ring::divide(), freeAlgebra(), LT, M2_gbTrace, mHeap, FreeAlgebra::monoid(), FreeAlgebra::mult_by_term_left_and_right(), mWordTable, Ring::negate(), FreeMonoidLogger::reset(), WordTable::subword(), FreeMonoid::wordFromMonom(), FreeMonoid::wordPrefixFromMonom(), and FreeMonoid::wordSuffixFromMonom().