Changeset 5bccba in git for Singular/LIB/ncfactor.lib

Timestamp:

Feb 11, 2019, 5:41:21 PM (5 years ago)

Author:

Viktor Levandovskyy <levandov@…>

Branches:

(u'spielwiese', 'fe61d9c35bf7c61f2b6cbf1b56e25e2f08d536cc')

Children:

77624bdb8f875aa938e9fda67d8720405651c08d

Parents:

1bd40025d3997a6d11d72e7f8e2834d3fdd83ef9dfa15b9f0da1b32d9c4aff3f6014b3b03d8a72c2

Message:

Merge remote-tracking branch 'upstream/spielwiese' into spielwiese

File:

• Singular/LIB/ncfactor.lib (modified) (28 diffs)

Singular/LIB/ncfactor.lib

@@ -1 +1 @@
 ///////////////////////////////////////////////////////////
-version="version ncfactor.lib 4.1.1.0 Jan_2018 "; // $Id$
+version="version ncfactor.lib 4.0.0.0 _2017 "; //$Id$
 category="Noncommutative";
 info="
 LIBRARY: ncfactor.lib  Tools for factorization in some noncommutative algebras
-AUTHORS: Albert Heinle,     aheinle@uwaterloo.ca
-@*       Viktor Levandovskyy,     levandov@math.rwth-aachen.de
-
-OVERVIEW: New methods for factorization on polynomials
-  are implemented for three types of algebras, all generated by
-   2*n, n in NN, generators (n'th Weyl, n'th shift and graded polynomials in n'th q-Weyl algebras)
-   over a field K.
+AUTHORS: Albert Heinle,     aheinle at uwaterloo.ca
+@*       Viktor Levandovskyy,     levandov at math.rwth-aachen.de
+
+OVERVIEW: In this library, new methods for factorization on polynomials
+@* are implemented for several types of algebras, namely
+@* - finitely presented (and also free) associative algebras (Letterplace subsystem)
+@* - G-algebras (Plural subsystem), including (q)-Weyl and (q)-shift algebras in 2n variables
+@* The determination of the best algorithm available for users input is done
+@* automatically in the procedure ncfactor().
+
 @* More detailled description of the algorithms and related publications can be found at
-   @url{https://cs.uwaterloo.ca/\~aheinle/}.
+@url{https://cs.uwaterloo.ca/\~aheinle/}.
 
 PROCEDURES:
-  ncfactor(h);               Factorization in any G-algebra.
+  ncfactor(h);               Factorization in any finitely presented algebra (incl. G-algebra)
   facWeyl(h);                Factorization in the n'th Weyl algebra
   facFirstWeyl(h);           Factorization in the first Weyl algebra
@@ -37 +40 @@
 LIB "solve.lib"; //for solve
 LIB "poly.lib"; //for content
+LIB "fpadim.lib"; //for letterplace
 
 proc tst_ncfactor()
@@ -128 +132 @@
   }
   print("Successful.");
-  print("Testing Min");
-  if (!test_Min())
-  {
-    ERROR("Min is not working properly.");
-  }
-  print("Successful.");
   print("Testing isListEqual");
   if (!test_isListEqual())
@@ -410 +408 @@
   }
   print("Successful.");
-  print("Testing delete_duplicates_noteval_and_sort");
+  print("Testing getMaxDegreeVecLetterPlace");
+  if(!test_getMaxDegreeVecLetterPlace())
+  {
+    ERROR("getMaxDegreeVecLetterPlace is not working properly.");
+  }
+  print("Successful.");
+  print("Testing wordsWithMaxAppearance");
+  if(!test_wordsWithMaxAppearance())
+  {
+    ERROR("wordsWithMaxAppearance is not working properly.");
+  }
+  print("Successful.");
+  print("Testing monsSmallerThanLetterPlace");
+  if(!test_monsSmallerThanLetterPlace())
+  {
+    ERROR("monsSmallerThanLetterPlace is not working properly.");
+  }
+  print("Successful.");
+  print("Testing ncfactor_letterplace_poly_s");
+  if(!test_ncfactor_letterplace_poly_s())
+  {
+    ERROR("ncfactor_letterplace_poly_s is not working properly.");
+  }
+  print("Successful.");
+  print("Testing ncfactor_without_opt_letterplace");
+  if(!test_ncfactor_without_opt_letterplace())
+  {
+    ERROR("ncfactor_without_opt_letterplace is not working properly.");
+  }
+  print("Successful.");
   print("All tests ran successfully.");
 }
@@ -2041 +2068 @@
   return(result);
 }//testing increment_intvec
-
-
-//I know that Singular has this function in the package
-//qhmoduli.lib. But I don't see the reason why I should clutter my
-//namespace with functions to study Moduli Spaces of
-//Semi-Quasihomogeneous Singularities (in case somebody wonders)
-static proc Min(def lst)
-"USAGE: Min(lst); list is an iterable element (list/ideal/intvec)
-        containing ordered elements.
-PURPOSE: returns the minimal element in lst
-ASSUME: lst contains at least one element
-"{//proc Min
-  def minElem = lst[1];
-  int i;
-  for (i = 2; i<=size(lst);i++)
-  {
-    if (lst[i]<minElem)
-    {
-      minElem = lst[i];
-    }
-  }
-  return (minElem);
-}//proc Min
-
-
-static proc test_Min()
-{//Testing Min
-  int result = 1;
-  //Test 1: One element list
-  int expected= 1;
-  int obtained = Min(list(1));
-  if (expected!=obtained)
-  {
-    print("Test 1 for Min failed.");
-    print("Expected:\n");
-    print(expected);
-    print("obtained:\n");
-    print(obtained);
-    result = 0;
-  }
-  //Test 2: Two element list, first one is Min
-  expected = 5;
-  obtained = Min(list(5,8));
-  if (expected!=obtained)
-  {
-    print("Test 2 for Min failed.");
-    print("Expected:\n");
-    print(expected);
-    print("obtained:\n");
-    print(obtained);
-    result = 0;
-  }
-  //Test 3: Two element list, second one is Min
-  expected = 5;
-  obtained = Min(list(8,5));
-  if (expected!=obtained)
-  {
-    print("Test 3 for Min failed.");
-    print("Expected:\n");
-    print(expected);
-    print("obtained:\n");
-    print(obtained);
-    result = 0;
-  }
-  //Test 4: A lot of elements, Min randomly in between.
-  expected = -11;
-  obtained = Min(list(5,8,7,2,8,0,-11,0,25));
-  if (expected!=obtained)
-  {
-    print("Test 4 for Min failed.");
-    print("Expected:\n");
-    print(expected);
-    print("obtained:\n");
-    print(obtained);
-    result = 0;
-  }
-  return(result);
-}//Testing Min
-
 
 static proc isListEqual(list l1, list l2)
@@ -3340 +3288 @@
 "
 {//isInCommutativeSubRing
+  int i; int j; int k;
+  intvec tempIntVec;
+  int previouslyEncounteredVar = -1;
+  if ( attrib(basering, "isLetterplaceRing") >= 1)
+  {//separate department: letterplace case
+    for (i = 1; i<=size(h); i++)
+    {//iterating over the monomials of h
+      tempIntVec = lp2iv(h[i]);
+      if (size(tempIntVec) > 1)
+      {//nontrivial monomial
+    j = tempIntVec[1];
+    if (previouslyEncounteredVar != -1 and j != previouslyEncounteredVar)
+    {//In this case, the previously encountered var is not equal to this one
+      return(0);
+    }//In this case, the previously encountered var is not equal to this one
+    previouslyEncounteredVar = j;
+    for (k = 2; k <= size(tempIntVec); k++)
+    {//checking if each entry in the intvec is the same
+      if (tempIntVec[k]!=j)
+      {//more than one variable in monomial
+        return(0);
+      }//more than one variable in monomial
+    }//checking if each entry in the intvec is the same
+      }//nontrivial monomial
+      else
+      {i++; continue;}
+    }//iterating over the monomials of h
+    return(1);
+  }//separate department: letterplace case
   list tempRingList = ringlist(basering);
   if (size(tempRingList)<=4)
@@ -3346 +3323 @@
   }//In this case, the given ring was commutative
   list appearing_variables;
-  int i; int j;
   intvec degreeIntVec;
   for (i = 1; i<=nvars(basering);i++)
@@ -3426 +3402 @@
   {
     print("Test 4 for isInCommutativeSubRing failed.");
+    print("Expected:\n");
+    print(expected);
+    print("obtained:\n");
+    print(obtained);
+    result = 0;
+  }
+  return(result);
+  //Test 5: Letterplace ring, negative example
+  ring r2 = 0,(x,y,z),dp;
+  int d =4; // degree bound
+  def R2 = makeLetterplaceRing(d);
+  setring R2;
+  expected = 0;
+  obtained = isInCommutativeSubRing(x + y);
+  if (expected !=obtained)
+  {
+    print("Test 5 for isInCommutativeSubRing failed.");
+    print("Expected:\n");
+    print(expected);
+    print("obtained:\n");
+    print(obtained);
+    result = 0;
+  }
+  //Test 6: Letterplace ring, positive example
+  expected = 1;
+  obtained = isInCommutativeSubRing(x + x*x);
+  if (expected !=obtained)
+  {
+    print("Test 6 for isInCommutativeSubRing failed.");
+    print("Expected:\n");
+    print(expected);
+    print("obtained:\n");
+    print(obtained);
+    result = 0;
+  }
+  //Test 7: Letterplace ring, previous bug
+  expected = 0;
+  obtained = isInCommutativeSubRing(x*x - y*y);
+  if (expected !=obtained)
+  {
+    print("Test 7 for isInCommutativeSubRing failed.");
     print("Expected:\n");
     print(expected);
@@ -3457 +3474 @@
   if (deg(h)<=0)
   {
-    dbprint(p,dbprintWhitespace + "h is a constant. Returning
- immediately");
+    dbprint(p,dbprintWhitespace + "h is a constant. Returning immediately");
     return(list(list(h)));
   }
   def r = basering;
   list factorizeOutput;
-  if (size(ringlist(basering))<=4)
+  if (size(ringlist(basering))<=4 && (attrib(r, "isLetterplaceRing") == 0) )
   {//commutative ring case
-    dbprint(p,dbprintWhitespace + "We are in a commutative
- ring. Factoring h using factorize.");
+    dbprint(p,dbprintWhitespace + "We are in a commutative ring. Factoring h using factorize.");
     factorizeOutput = factorize(h);
   }//commutative ring case
   else
   {//commutative subring case;
-    dbprint(p,dbprintWhitespace + "We are in a commutative
- subring. Generating commutative ring..");
-    def rList = ringlist(basering);
-    rList = delete(rList,5);
-    rList = delete(rList,5);
-    def tempRing = ring(rList);
-    setring(tempRing);
-    poly h = imap(r,h);
-    dbprint(p, dbprintWhitespace+"Factoring h in commutative ring.");
-    list tempResult = factorize(h);
-    setring(r);
-    factorizeOutput = imap(tempRing,tempResult);
+    dbprint(p,dbprintWhitespace + "We are in a commutative subring. Generating commutative ring.");
+    if (attrib(r, "isLetterplaceRing") == 0)
+    {//G-algebra case
+      def rList = ringlist(basering);
+      rList = delete(rList,5);
+      rList = delete(rList,5);
+      def tempRing = ring(rList);
+      setring(tempRing);
+      poly h = imap(r,h);
+      dbprint(p, dbprintWhitespace+"Factoring h in commutative ring.");
+      list tempResult = factorize(h);
+      setring(r);
+      factorizeOutput = imap(tempRing,tempResult);
+    }//G-algebra case
+    else
+    {//Letterplace case
+      int theRightVar = lp2iv(h[1])[1];
+      list commFactInIv = list();
+      list tempMonomList = list();
+      def rList = ringlist(basering);
+      rList[2] = list("@x");
+      rList[3] = list(list("dp", intvec(1)),
+              list("C", 0));
+      def tempRing = ring(rList);
+      setring(tempRing);
+      ideal tempIdeal;
+      for (i=1; i<=nvars(r); i++)
+      {tempIdeal[i] = var(1);}
+      map fromR = r, tempIdeal;
+      poly h = fromR(h);
+      dbprint(p, dbprintWhitespace+"Factoring h in commutative ring.");
+      list tempResult = factorize(h);
+      dbprint(p, dbprintWhitespace+"Done. The result is:");
+      dbprint(p, tempResult);
+      dbprint(p, dbprintWhitespace+"Now translated into intvec representation:");
+      for (i = 1; i <= size(tempResult[1]); i++)
+      {//translate all factorizations into lists of intvecs and coeffs
+    commFactInIv[i] = list();
+    for (j = 1; j <= size(tempResult[1][i]); j++)
+    {//iterate over each monomial
+      commFactInIv[i][j] = list(leadcoef(tempResult[1][i][j]));
+      if (deg(tempResult[1][i][j]) != 0)
+      {//a power of @x
+        commFactInIv[i][j] = commFactInIv[i][j] + list(theRightVar:deg(tempResult[1][i][j]));
+      }//a power of @x
+    }//iterate over each monomial
+      }//translate all factorizations into lists of intvecs and coeffs
+      dbprint(p, commFactInIv);
+      setring(r);
+      factorizeOutput = imap(tempRing,tempResult);
+      list commFactInIv = imap(tempRing, commFactInIv);
+      poly tempEntry;
+      for (i = 1; i<=size(commFactInIv); i++)
+      {
+    tempEntry = 0;
+    for (j=1; j<=size(commFactInIv[i]); j++)
+    {
+      if (size(commFactInIv[i][j]) == 1)
+      {//simply a number
+        tempEntry = tempEntry + commFactInIv[i][j][1];
+      }//simply a number
+      else
+      {
+        tempEntry = tempEntry + commFactInIv[i][j][1]*iv2lp(commFactInIv[i][j][2]);
+      }
+    }
+    factorizeOutput[1][i] = tempEntry;
+      }
+    }//Letterplace case
   }//commutative subring case;
-  dbprint(p,dbprintWhitespace + "Done commutatively factorizing.
- The result is:");
+  dbprint(p,dbprintWhitespace + "Done commutatively factorizing. The result isssssss:");
   dbprint(p,factorizeOutput);
   dbprint(p,dbprintWhitespace+"Computing all permutations of this factorization.");
@@ -3526 +3597 @@
   }
   kill R;
-  //Test 2: Non-commutative ring, constant
+  //Test 2: G-Algebra, constant
   ring R = 0,(x,d),dp;
   def r = nc_algebra(1,1);
@@ -3542 +3613 @@
   }
   kill r; kill R;
-  //Test 3: Non-commutative ring, definitely commutative subring, irreducible
+  //Test 3: G-Algebra, definitely commutative subring, irreducible
   ring R = 0,(x1,x2,d1,d2),dp;
   def r = Weyl();
@@ -3558 +3629 @@
   }
   kill r; kill R;
-  //Test 4: Non-commutative ring, definitely commutative subring,
+  //Test 4: G-Algebra, definitely commutative subring,
   //reducible
   ring R = 0,(x1,x2,d1,d2),dp;
@@ -3579 +3650 @@
   }
   kill r; kill R;
+  //Test 5: Letterplace ring, constant
+  ring r = 0,(x,y,z),dp;
+  int d =4; // degree bound
+  def R = makeLetterplaceRing(d);
+  setring R;
+  list expected = list(list(poly(3445)));
+  list obtained = factor_commutative(3445);
+  if (!isListEqual(expected,obtained))
+  {
+    print("Test 5 for factor_commutative failed.");
+    print("Expected:\n");
+    print(expected);
+    print("obtained:\n");
+    print(obtained);
+    result = 0;
+  }
+  //Test 6: Letterplace ring, definitely commutative subring, irreducible
+  expected = list(list(poly(1), x*x+ 2*x + 2));
+  obtained = factor_commutative(x*x+ 2*x + 2);
+  if (!isListEqual(expected,obtained))
+  {
+    print("Test 6 for factor_commutative failed.");
+    print("Expected:\n");
+    print(expected);
+    print("obtained:\n");
+    print(obtained);
+    result = 0;
+  }
+  //Test 7: Letterplace ring, definitely commutative subring,
+  //reducible
+  expected = list(list(poly(1), x*x+ 2*x + 2, x*x- 2*x - 2),
+            list(poly(1), x*x- 2*x - 2, x*x+ 2*x + 2));
+  obtained = factor_commutative((x*x+ 2*x + 2)*(x*x- 2*x - 2));
+  if (!isListEqual(expected,obtained))
+  {
+    print("Test 7 for factor_commutative failed.");
+    print("Expected:\n");
+    print(expected);
+    print("obtained:\n");
+    print(obtained);
+    result = 0;
+  }
+  //Test 8: Letterplace ring, using last variable
+  expected = list(list(poly(1), z*z+ 2*z + 2, z*z - 2*z - 2),
+            list(poly(1), z*z - 2*z - 2, z*z+ 2*z + 2));
+  obtained = factor_commutative((z*z+ 2*z + 2)*(z*z - 2*z - 2));
+  if (!isListEqual(expected,obtained))
+  {
+    print("Test 8 for factor_commutative failed.");
+    print("Expected:\n");
+    print(expected);
+    print("obtained:\n");
+    print(obtained);
+    result = 0;
+  }
   return(result);
 }//testing factor_commutative
@@ -6730 +6856 @@
 
   result = delete_duplicates_noteval_and_sort(result);
-  //print(M);
   if (size(result) == 0)
   {//no factorization found
@@ -6894 +7019 @@
   }
   hZeroinR = tempHList;
-  //hBetweenDegrees = reverse(hBetweenDegrees);
   dbprint(p,dbprintWhitespace+" Done!");
   dbprint(p,dbprintWhitespace+" Moving everything into the ring K[theta]");
@@ -8244 +8368 @@
   list tempList = list();
   //First, we are going to deal with our most hated guys: The Coefficients.
-  //
   dbprint(p,dbprintWhitespace + "We get all combinations for the coefficient of the
 maximal homogeneous part");
@@ -9746 +9869 @@
   rlist[3][2][2]=intvec(0);
   rlist = insert(rlist,ideal(0),3);
-  //The following lines of code will become obsolete once bug #753 in
-  //Singular is fixed. Until then, this measure is unfortunately
-  //necessary.
-  //begin
-  intvec perms = 0:nvars(@r);
-  for (i =1; i<=nvars(@r);i++)
-  {//finding the right position of each input variable
-    for (j = 1; j<=size(inpList); j++)
-    {
-      if (var(i)==inpList[j])
-      {//found the correct spot
-    perms[i] = j;
-    break;
-      }//found the correct spot
-    }
-  }//finding the right position of each input variable
   def @r2 = ring(rlist);
   setring(@r2);
   def @r3 = Weyl();
   setring(@r3);
-  ideal mappingIdeal;
-  for (i = 1; i<=size(perms); i++)
-  {//generating the mapping ideal
-    if (perms[i]>0)
-    {//only variables that are in the input list are permitted
-      mappingIdeal[i] = var(perms[i]);
-    }//only variables that are in the input list are permitted
-  }//generating the mapping ideal
-  map toR3 = @r, mappingIdeal;
-  poly h = toR3(h);
+  poly h = imap(@r,h);
   list result = facWeyl(h);
   setring(@r);
-  ideal mappingIdeal;
-  for (i = 1; i<=size(perms);i++)
-  {//finding the correct permutation
-    for (j = 1; j<=size(perms); j++)
-    {//the spot needs to coincide
-      if (perms[j]==i)
-      {//found it
-    mappingIdeal[i] = var(j);
-    break;
-      }//found it
-    }//the spot needs to coincide
-  }//finding the correct permutation
-  map toR = @r3, mappingIdeal;
-  list result = toR(result);
-  //end
-  //once bug is fixed, please uncomment the following lines and
-  //discard the above
-  /* def @r2 = ring(rlist); */
-  /* setring(@r2); */
-  /* def @r3 = Weyl(); */
-  /* setring(@r3); */
-  /* poly h = imap(@r,h); */
-  /* list result = facWeyl(h); */
-  /* setring(@r); */
-  /* list result = imap(@r3,result); */
+  list result = imap(@r3,result);
   return(result);
 }//proc facSubWeyl
@@ -10474 +10548 @@
  - We have n parameters q_1,..., q_n given.
 
-SEE ALSO: homogfacFirstQWeyl, homogfacFirstQWeyl_all
+SEE ALSO: homogfacNthWeyl, homogfacFirstQWeyl, homogfacFirstQWeyl_all
 "
 {//proc homogfacNthQWeyl_all
@@ -10992 +11066 @@
 - There exists at least one variable in the ring.
 NOTE:
+- works for both PLURAL and LETTERPLACE subsystems
 - Every entry of the output list is a list with factors for one possible factorization.
   The first factor is always a constant (1, if no nontrivial constant
@@ -11002 +11077 @@
   for (i = 1; i<=voice;i++)
   {dbprintWhitespace = dbprintWhitespace + " ";}
-  dbprint(p,dbprintWhitespace + "Checking if the field fulfills
+  dbprint(p,dbprintWhitespace + "Checking if the field fulfills\
  everything we assume.");
   if (nvars(basering)<1)
@@ -11010 +11085 @@
     if (minpoly !=0)
     {
-      ERROR("factorize does not support fields of type (p^n,a)");
+      ERROR("factorize does not support fields of type (p^n,a) yet");
       return list(list());
     }
   }
-  dbprint(p,dbprintWhitespace + "Everything seems to be alright with
+  dbprint(p,dbprintWhitespace + "Everything seems to be alright with\
  the ground field.");
   if (deg(h)<=0)
@@ -11024 +11099 @@
   dbprint(p,dbprintWhitespace+"Checking if a more improved algorithm\
  is available other than the naive ansatz-method.");
-  dbprint(p,dbprintWhitespace+"1. Checking if h in commutative
- (sub)-ring");
+  dbprint(p,dbprintWhitespace+"1. Checking if h in commutative (sub)-ring");
   if (isInCommutativeSubRing(h))
   {//h is in a commutative subring
     return(factor_commutative(h));
   }//h is in a commutative subring
-  dbprint(p,dbprintWhitespace+"h was not in a commutative
+  dbprint(p,dbprintWhitespace+"h was not in a commutative\
  (sub)-ring.");
-  dbprint(p,dbprintWhitespace+"2. Checking if h is in Weyl-Algebra
- over QQ");
+  dbprint(p,dbprintWhitespace+"2. Checking if h was in a letterplace ring");
+  if ( attrib(basering, "isLetterplaceRing") >= 1 )
+  {
+    dbprint(p,dbprintWhitespace+
+            "We are indeed in a letterplace ring. Forwarding the computation " +
+            "to ncfactor-without-opt-letterplace");
+    return(ncfactor_without_opt_letterplace(h));
+  }
+  dbprint(p,dbprintWhitespace+"2. Checking if h is in Weyl-Algebra over QQ");
   if (ncfactor_isWeyl()&&npars(basering)==0&&char(basering)==0)
   {
-    dbprint(p,dbprintWhitespace + "We are indeed in a Weyl
- algebra. Forwarding computation to facWeyl");
+    dbprint(p,dbprintWhitespace +
+            "We are indeed in a Weyl algebra. Forwarding computation to facWeyl");
     return(facWeyl(h));
   }
   dbprint(p,dbprintWhitespace+"Our ring is not a Weyl algebra over QQ.");
-  dbprint(p,dbprintWhitespace+"3. Checking if we are in a q-Weyl
- algebra over QQ.");
+  dbprint(p,dbprintWhitespace+"3. Checking if we are in a q-Weyl algebra over QQ.");
   if (ncfactor_isQWeyl()&&char(basering)==0)
   {
-    dbprint(p,dbprintWhitespace + "We are indeed in a q-Weyl
+    dbprint(p,dbprintWhitespace + "We are indeed in a q-Weyl\
  algebra over QQ. Checking if homogeneous.");
     if(homogwithorderNthWeyl(h))
     {
-      dbprint(p,dbprintWhitespace+"h was homogeneous. Forwarding
+      dbprint(p,dbprintWhitespace+"h was homogeneous. Forwarding\
  computation to homogfacqweyl.");
       return(homogfacNthQWeyl_all(h));
@@ -11055 +11135 @@
   }
   dbprint(p,dbprintWhitespace+"Our ring is not a q-Weyl algebra.");
-  dbprint(p,dbprintWhitespace+"4. Checking if h is in a subalgebra
+  dbprint(p,dbprintWhitespace+"4. Checking if h is in a subalgebra\
  that resembles the Weyl algebra");
   if(isInWeylSubAlg(h)&&npars(basering)==0&&char(basering)==0)
   {
-    dbprint(p,dbprintWhitespace+"We are indeed in a subalgebra that is
+    dbprint(p,dbprintWhitespace+"We are indeed in a subalgebra that is\
  isomorphic to a Weyl algebra. Forwarding to facSubWeyl.");
     return(facSubWeyl(h));
   }
-  dbprint(p,dbprintWhitespace+"No optimized algorithm available. Going
+  dbprint(p,dbprintWhitespace+"No optimized algorithm available. Going \
  for the ansatz method without optimization.");
   return(ncfactor_without_opt(h));
@@ -11070 +11150 @@
 {
   "EXAMPLE:";echo=2;
+  // first, an example with PLURAL 
   def R = makeUsl2();
   setring(R);
   poly p = e^3*f+e^2*f^2-e^3+e^2*f+2*e*f^2-3*e^2*h-2*e*f*h-8*e^2
            +e*f+f^2-4*e*h-2*f*h-7*e+f-h;
+  ncfactor(p);
+  kill R;
+  // an example with LETTERPLACE
+  LIB "freegb.lib";
+  ring r = 0,(x,y),Dp;
+  def R = freeAlgebra(r,5); setring(R);
+  poly p = x*y*x - x;
   ncfactor(p);
 }
@@ -11286 +11374 @@
   {
     print("Test 10 for ncfactor failed.");
+    print("Expected:\n");
+    print(expected);
+    print("obtained:\n");
+    print(obtained);
+    result = 0;
+  }
+  kill r;
+  //Test 11: Generic Letterplace example
+  ring r = 0,(x,y,z),dp;
+  int d =4; // degree bound
+  def R = makeLetterplaceRing(d);
+  setring R;
+  poly f1 = 6*x*y*x + 9*x;
+  list obtained = ncfactor(f1);
+  list expected = sortFactorizations(
+    list(
+      list(number(3), x, 2*y*x + 3),
+      list(number(3), 2*x*y + 3, x)
+      ));
+  if (!isListEqual(expected,obtained))
+  {
+    print("Test 11 for ncfactor failed.");
     print("Expected:\n");
     print(expected);
@@ -11984 +12094 @@
 }//testing factorize_nc_s
 
+
+static proc getMaxDegreeVecLetterPlace(poly h)
+"USAGE: getMaxDegreeVecLetterPlace(h); h is a polynomial in a
+        Letterplace ring.
+RETURN: intvec
+PURPOSE: Returns for each variable in the ring the maximal
+         degree in which it appears in h.
+ASSUMING: The basering is
+"
+{//proc getMaxDegreeVecLetterPlace
+  int lv = attrib(basering, "isLetterplaceRing"); // nvars of orig ring
+  if (h == 0) { return (0:lv); }
+  intvec tempIntVec1 = 0:lv;
+  intvec maxDegrees = 0:lv;
+  intvec tempIntVec2;
+  int i; int j;
+  for (i = 1; i<=size(h); i++)
+  {//going through each monomial in h and finding the degree in each var
+    tempIntVec2 = lp2iv(h[i]);
+    if (tempIntVec2 == 0)
+    {
+      i++; continue;
+    }
+    tempIntVec1 = 0:lv;
+    for (j=1; j<=size(tempIntVec2); j++)
+    {//filling in the number of occurrences
+      tempIntVec1[tempIntVec2[j]] = tempIntVec1[tempIntVec2[j]] + 1;
+    }//filling in the number of occurrences
+    for (j = 1; j<=lv; j++)
+    {//putting the max into maxDegrees
+      maxDegrees[j] = max(maxDegrees[j], tempIntVec1[j]);
+    }//putting the max into maxDegrees
+  }//going through each monomial in h and finding the degree in each var
+  return(maxDegrees);
+}//proc getMaxDegreeVecLetterPlace
+
+static proc test_getMaxDegreeVecLetterPlace()
+{//testing getMaxDegreeVecLetterPlace
+  int result = 1;
+  ring r = 0,(x,y,z),dp;
+  int d =4; // degree bound
+  def R = makeLetterplaceRing(d);
+  setring R;
+  //Test 1: 0
+  intvec expected = 0:3;
+  intvec obtained = getMaxDegreeVecLetterPlace(0);
+  if (expected!=obtained)
+  {
+    print("Test 1 for getMaxDegreeVecLetterPlace failed.");
+    print("Expected:\n");
+    print(expected);
+    print("obtained:\n");
+    print(obtained);
+    result = 0;
+  }
+  //Test 2: Constant neq 0
+  expected = 0:3;
+  obtained = getMaxDegreeVecLetterPlace(3);
+  if (expected!=obtained)
+  {
+    print("Test 2 for getMaxDegreeVecLetterPlace failed.");
+    print("Expected:\n");
+    print(expected);
+    print("obtained:\n");
+    print(obtained);
+    result = 0;
+  }
+  //Test 3: univariate, first variable
+  expected = 2, 0, 0;
+  obtained = getMaxDegreeVecLetterPlace(5*x*x + x + 1);
+  if (expected!=obtained)
+  {
+    print("Test 3 for getMaxDegreeVecLetterPlace failed.");
+    print("Expected:\n");
+    print(expected);
+    print("obtained:\n");
+    print(obtained);
+    result = 0;
+  }
+  //Test 4: univariate, another variable
+  expected = 0, 0, 3;
+  obtained = getMaxDegreeVecLetterPlace(5*z*z*z + z*z + 1);
+  if (expected!=obtained)
+  {
+    print("Test 4 for getMaxDegreeVecLetterPlace failed.");
+    print("Expected:\n");
+    print(expected);
+    print("obtained:\n");
+    print(obtained);
+    result = 0;
+  }
+  //Test 5: random polynomial
+  expected = 3, 1, 2;
+  obtained = getMaxDegreeVecLetterPlace(2*x*y*x*x + 4*y*z*z);
+  if (expected!=obtained)
+  {
+    print("Test 5 for getMaxDegreeVecLetterPlace failed.");
+    print("Expected:\n");
+    print(expected);
+    print("obtained:\n");
+    print(obtained);
+    result = 0;
+  }
+  return(result);
+}//testing getMaxDegreeVecLetterPlace
+
+static proc wordsWithMaxAppearance(intvec maxDegInCoordinates, int upToDeg)
+"USAGE: wordsWithMaxAppearance(maxDegInCoordinates);
+maxDegreeInCoordinates is an intvec.
+RETURN: list
+PURPOSE: maxDegInCoordinates is a vector representing
+the maximum times a variable is allowed to appear in a monomial in
+letterplace representation. This function computes all possible words
+given this restriction.
+ASSUME: maxDegInCoordinates only has non-negative entries
+"{//wordsWithMaxAppearance
+  int p=printlevel-voice+2;//for dbprint
+  int i; int j;
+  string dbprintWhitespace = "";
+  for (i = 1; i<=voice;i++)
+  {dbprintWhitespace = dbprintWhitespace + " ";}
+  list result;
+  intvec tempMaxDegs;
+  list recResult;
+  for (i = 1; i<=size(maxDegInCoordinates); i++)
+  {//For each coordinate not equal to zero, do a recursive call and concatenate
+    if (maxDegInCoordinates[i] <= 0)
+    {//Done with coordinate i
+      i++; continue;
+    }//Done with coordinate i
+    tempMaxDegs = maxDegInCoordinates;
+    tempMaxDegs[i] = tempMaxDegs[i] - 1;
+    recResult = wordsWithMaxAppearance(tempMaxDegs, upToDeg);
+    if (size(recResult) == 0 && upToDeg>=1)
+    {//Single entry just needs to be there
+      result = result + list(intvec(i));
+    }//Single entry just needs to be there
+    result = result + recResult;
+    for (j = 1; j<=size(recResult); j++)
+    {//concatenate i to all elements in recResult
+      if (size(recResult[j]) + 1 <= upToDeg)
+      {//only concatenate if uptodeg is not exceeded
+    recResult[j] = intvec(i, recResult[j]);
+      }//only concatenate if uptodeg is not exceeded
+    }//concatenate i to all elements in recResult
+    result = result + recResult;
+  }//For each coordinate not equal to zero, do a recursive call and concatenate
+  return(delete_duplicates_noteval_and_sort(result));
+}//wordsWithMaxAppearance
+
+static proc test_wordsWithMaxAppearance()
+{//test_wordsWithMaxAppearance
+  int result = 1;
+  //Test 1: 0 intvec
+  list expected = list();
+  list obtained = wordsWithMaxAppearance(intvec(0), 4);
+  if (!isListEqual(expected,obtained))
+  {
+    print("Test 1 for wordsWithMaxAppearance failed.");
+    print("Expected:\n");
+    print(expected);
+    print("obtained:\n");
+    print(obtained);
+    result = 0;
+  }
+  //Test 2: 0 multiple entries intvec
+  expected = list();
+  obtained = wordsWithMaxAppearance(0:10, 4);
+  if (!isListEqual(expected,obtained))
+  {
+    print("Test 2 for wordsWithMaxAppearance failed.");
+    print("Expected:\n");
+    print(expected);
+    print("obtained:\n");
+    print(obtained);
+    result = 0;
+  }
+  //Test 3: Single letter
+  expected = list(intvec(4));
+  obtained = wordsWithMaxAppearance(intvec(0, 0, 0, 1, 0, 0), 4);
+  if (!isListEqual(expected,obtained))
+  {
+    print("Test 3 for wordsWithMaxAppearance failed.");
+    print("Expected:\n");
+    print(expected);
+    print("obtained:\n");
+    print(obtained);
+    result = 0;
+  }
+  //Test 4: Two letters, one appearance
+  expected = list(intvec(3), intvec(3,4), intvec(4), intvec(4,3));
+  obtained = wordsWithMaxAppearance(intvec(0, 0, 1, 1, 0, 0), 4);
+  if (!isListEqual(expected,obtained))
+  {
+    print("Test 4 for wordsWithMaxAppearance failed.");
+    print("Expected:\n");
+    print(expected);
+    print("obtained:\n");
+    print(obtained);
+    result = 0;
+  }
+  //Test 5: One letter, degree 2
+  expected = list(intvec(4), intvec(4,4));
+  obtained = wordsWithMaxAppearance(intvec(0, 0, 0, 2, 0, 0), 4);
+  if (!isListEqual(expected,obtained))
+  {
+    print("Test 5 for wordsWithMaxAppearance failed.");
+    print("Expected:\n");
+    print(expected);
+    print("obtained:\n");
+    print(obtained);
+    result = 0;
+  }
+  //Test 6: random example
+  expected = list(intvec(1),
+          intvec(1,4),
+          intvec(1,4,4),
+          intvec(4),
+          intvec(4,1),
+          intvec(4,1,4),
+          intvec(4,4),
+          intvec(4,4,1));
+  obtained = wordsWithMaxAppearance(intvec(1, 0, 0, 2, 0, 0), 4);
+  if (!isListEqual(expected,obtained))
+  {
+    print("Test 6 for wordsWithMaxAppearance failed.");
+    print("Expected:\n");
+    print(expected);
+    print("obtained:\n");
+    print(obtained);
+    result = 0;
+  }
+  return(result);
+}//test_wordsWithMaxAppearance
+
+static proc monsSmallerThanLetterPlace(poly e, intvec maxDegInCoordinates, int upToDeg)
+"USAGE: monsSmallerThanLetterPlace(e, maxDegInCoordinates); e is a
+monomial.
+maxDegreeInCoordinates encodes the maximal degree we wish to encounter
+in each variable.
+RETURN: list
+PURPOSE: Computes all monomials in the basering which are degree-wise
+smaller than the leading monomial of e.
+"{//monsSmallerThanLetterPlace
+  int p=printlevel-voice+2;//for dbprint
+  int i;
+  string dbprintWhitespace = "";
+  for (i = 1; i<=voice;i++)
+  {dbprintWhitespace = dbprintWhitespace + " ";}
+  list result;
+  int maxLen = min(sum(maxDegInCoordinates), lpDegBound(basering));
+  dbprint(p,dbprintWhitespace + "maxLength: " + string(maxLen));
+  list allPossibilities = wordsWithMaxAppearance(maxDegInCoordinates, upToDeg);
+  dbprint(p,dbprintWhitespace + "words with max appearance: " + string(allPossibilities));
+  poly candidate;
+  intvec candidateMaxDeg;
+  for (i = 1; i<=size(allPossibilities); i++)
+  {//checking for monomials with smaller degree than e
+    candidate = iv2lp(allPossibilities[i]);
+    dbprint(p,dbprintWhitespace + "Checking candidate: " + string(candidate));
+    candidateMaxDeg = getMaxDegreeVecLetterPlace(candidate);
+    if (candidate < e && candidateMaxDeg <= maxDegInCoordinates)
+    {//successfully found a candidate
+      result = insert(result, candidate);
+    }//successfully found a candidate
+  }//checking for monomials with smaller degree than e
+  return(result);
+}//monsSmallerThanLetterPlace
+
+static proc test_monsSmallerThanLetterPlace()
+{//test_monsSmallerThanLetterPlace
+  int result = 1;
+  ring r = 0,(x,y,z,d,w),dp;
+  int upToDegBound = 10; // degree bound
+  def R = makeLetterplaceRing(upToDegBound);
+  setring R;
+  //Test 1: 0, 0
+  poly input1 = 0;
+  intvec input2 = intvec(0,0,0,0,0);
+  list expected = list();
+  list obtained = monsSmallerThanLetterPlace(input1, input2, upToDegBound);
+  if (!isListEqual(expected,obtained))
+  {
+    print("Test 1 for monsSmallerThanLetterPlace failed.");
+    print("Expected:\n");
+    print(expected);
+    print("obtained:\n");
+    print(obtained);
+    result = 0;
+  }
+  //Test 2: 0, nontrivial maxdegree
+  input1 = 0;
+  input2 = intvec(0,0,2,1,0);
+  expected = list();
+  obtained = monsSmallerThanLetterPlace(input1, input2, upToDegBound );
+  if (!isListEqual(expected,obtained))
+  {
+    print("Test 2 for monsSmallerThanLetterPlace failed.");
+    print("Expected:\n");
+    print(expected);
+    print("obtained:\n");
+    print(obtained);
+    result = 0;
+  }
+  //Test 3: constant, nontrivial maxdegree
+  input1 = 7;
+  input2 = intvec(0,0,2,1,0);
+  expected = list();
+  obtained = monsSmallerThanLetterPlace(input1, input2, upToDegBound);
+  if (!isListEqual(expected,obtained))
+  {
+    print("Test 3 for monsSmallerThanLetterPlace failed.");
+    print("Expected:\n");
+    print(expected);
+    print("obtained:\n");
+    print(obtained);
+    result = 0;
+  }
+  //Test 4: single variable smallest, nontrivial maxdegree
+  input1 = w;
+  input2 = intvec(0,0,2,1,0);
+  expected = list();
+  obtained = monsSmallerThanLetterPlace(input1, input2, upToDegBound );
+  if (!isListEqual(expected,obtained))
+  {
+    print("Test 4 for monsSmallerThanLetterPlace failed.");
+    print("Expected:\n");
+    print(expected);
+    print("obtained:\n");
+    print(obtained);
+    result = 0;
+  }
+  //Test 5: single variable highest, nontrivial maxdegree
+  input1 = x;
+  input2 = intvec(0,0,2,1,0);
+  expected = list(d, z);
+  obtained = monsSmallerThanLetterPlace(input1, input2, upToDegBound);
+  if (!isListEqual(expected,obtained))
+  {
+    print("Test 5 for monsSmallerThanLetterPlace failed.");
+    print("Expected:\n");
+    print(expected);
+    print("obtained:\n");
+    print(obtained);
+    result = 0;
+  }
+  //Test 6: single variable highest, nontrivial maxdegree
+  input1 = x;
+  input2 = intvec(0,0,2,1,0);
+  expected = list(d, z);
+  obtained = monsSmallerThanLetterPlace(input1, input2, upToDegBound );
+  if (!isListEqual(expected,obtained))
+  {
+    print("Test 6 for monsSmallerThanLetterPlace failed.");
+    print("Expected:\n");
+    print(expected);
+    print("obtained:\n");
+    print(obtained);
+    result = 0;
+  }
+  //Test 7: nontrivial monomial, nontrivial maxdegree
+  input1 = z*z*d*d;
+  input2 = intvec(0,0,2,1,0);
+  expected = list(d*z*z,
+          d*z,
+          d,
+          z*d*z,
+          z*d,
+          z*z*d,
+          z*z,
+          z);
+  obtained = monsSmallerThanLetterPlace(input1, input2, upToDegBound);
+  if (!isListEqual(expected,obtained))
+  {
+    print("Test 7 for monsSmallerThanLetterPlace failed.");
+    print("Expected:\n");
+    print(expected);
+    print("obtained:\n");
+    print(obtained);
+    result = 0;
+  }
+  return(result);
+}//test_monsSmallerThanLetterPlace
+
+static proc ncfactor_letterplace_poly_s(poly h)
+"USAGE: ncfactor_letterplace_poly_s(h); h is a polynomial in a
+        letterplace algebra
+RETURN: list(list)
+PURPOSE: Compute all factorizations of h
+THEORY: Implements an ansatz-driven factorization method as outlined
+by Bell, Heinle and Levandovskyy in \"On Noncommutative Finite
+Factorization Domains\".
+ASSUME:
+- basering is a Letterplace ring
+- basefield is such, that factorize() can factor any univariate and
+  multivariate commutative polynomial over it.
+- h is not a constant or 0.
+NOTE:
+- Every entry of the output list is a list with factors for one possible factorization.
+  The first factor is always a constant (1, if no nontrivial constant
+  could be excluded).
+SEE ALSO: ncfactor
+"{//proc ncfactor_letterplace_poly_s
+  int p=printlevel-voice+2;//for dbprint
+  int i; int j; int k; int l;
+  string dbprintWhitespace = "";
+  for (i = 1; i<=voice;i++)
+  {dbprintWhitespace = dbprintWhitespace + " ";}
+  list result;
+  // Producing the set M of the paper (permutation of the variables in
+  // the leading monomial)
+  dbprint(p,dbprintWhitespace + "Generating the set M.");
+  def r = basering;
+  intvec maxDegrees = getMaxDegreeVecLetterPlace(h);
+  dbprint(p,dbprintWhitespace + "The maximum degrees for each var are given by: "+
+      string(maxDegrees));
+  intvec expVec = lp2iv(leadmonom(h));
+  dbprint(p, dbprintWhitespace + "The leading monomial of h is: " + string(expVec));
+  list M;
+  for (i = 1; i<size(expVec); i++)
+  {//The set M consists of all posssible two-word-combinations of the leading monomial
+    M = M + list(list(intvec(expVec[1..i]), intvec(expVec[i+1..size(expVec)])));
+  }
+  dbprint(p,dbprintWhitespace+"The set M is:");
+  dbprint(p, M);
+  list list_UpToA;
+  list list_UpToB;
+  list tempSringlist = ringlist(r);
+  list clearSlateRingList = ringlist(r);
+  clearSlateRingList[2] = list();
+  clearSlateRingList[3] = list();
+  if (size(clearSlateRingList) == 6)
+  {//some non-commutative relations defined
+    clearSlateRingList = delete(clearSlateRingList, 6);
+    clearSlateRingList = delete(clearSlateRingList, 5);
+  }
+  else
+  {//It is still possible that we have a 5th entry
+    if (size(clearSlateRingList) == 5)
+    {
+      clearSlateRingList = delete(clearSlateRingList, 5);
+    }
+  }
+  intvec tempIntVec;
+  def S; def W; def W2;
+  list MEntry;
+  poly tempA;
+  poly tempB;
+  int filterFlag;
+  int jj = 1; int sizeOfSol = 1;
+  for (i = 1; i<=size(M); i++)
+  {//Iterating over all two-combinations in the set M
+    MEntry = M[i];
+    tempA = iv2lp(MEntry[1]);
+    tempB = iv2lp(MEntry[2]);
+    dbprint(p,dbprintWhitespace + "The potential leading combination of a is " + string(tempA));
+    dbprint(p,dbprintWhitespace + "The potential leading combination of b is " + string(tempB));
+    dbprint(p,dbprintWhitespace + "Calculating the monomials smaller than A");
+    list_UpToA = monsSmallerThanLetterPlace(leadmonom(tempA),
+                        maxDegrees - getMaxDegreeVecLetterPlace(tempB),
+                        lpDegBound(r));
+    dbprint(p,dbprintWhitespace + "Done, they are: " + string(list_UpToA));
+    dbprint(p,dbprintWhitespace + "Calculating the monomials smaller than B");
+    list_UpToB = monsSmallerThanLetterPlace(leadmonom(tempB),
+                        maxDegrees - getMaxDegreeVecLetterPlace(tempA),
+                        lpDegBound(r));
+    dbprint(p,dbprintWhitespace + "Done, they are: " + string(list_UpToB));
+    //we need to filter out lm(tempA) and lm(tempB);
+    for (k = size(list_UpToA); k>0; k--)
+    {//removing the leading monomial from list_UpToA and invalid parts
+      if (list_UpToA[k] == leadmonom(tempA))
+      {//found it
+    list_UpToA = delete(list_UpToA,k);
+    continue;
+      }//found it
+      if(sum(getMaxDegreeVecLetterPlace(h)) < sum(getMaxDegreeVecLetterPlace(list_UpToA[k])))
+      {//total degree exceeds
+    list_UpToA = delete(list_UpToA,k);
+    continue;
+      }//total degree exceeds
+    }//removing the leading monomial from list_UpToA and invalid parts
+    for (k = size(list_UpToB); k>0; k--)
+    {//removing the leading monomial from list_UpToA
+      if (list_UpToB[k] == leadmonom(tempB))
+      {//found it
+    list_UpToB = delete(list_UpToB,k);
+    continue;
+      }//found it
+      if(sum(getMaxDegreeVecLetterPlace(h)) < sum(getMaxDegreeVecLetterPlace(list_UpToB[k])))
+      {//total degree exceeds
+    list_UpToB = delete(list_UpToB,k);
+    continue;
+      }//total degree exceeds
+    }//removing the leading monomial from list_UpToA
+    if (typeof(tempSringlist[1]) == "int")
+    {//No extra parameters in the original ring
+      tempSringlist[1] = list(tempSringlist[1],list(), list(list()));
+    }//No extra parameters in the original ring
+    for (k = size(list_UpToB)+1; k>=0; k--)
+    {//fill in b-coefficients as variables
+      tempSringlist[1][2] = insert(tempSringlist[1][2],"@b("+string(k)+")");
+      clearSlateRingList[2] = insert(clearSlateRingList[2],"@b("+string(k)+")");
+    }//fill in b-coefficients as variables
+    for (k = size(list_UpToA); k>=0; k--)
+    {//fill in a-coefficients as variables
+      tempSringlist[1][2] = insert(tempSringlist[1][2],"@a("+string(k)+")");
+      clearSlateRingList[2] = insert(clearSlateRingList[2], "@a("+string(k)+")");
+    }//fill in a-coefficients as variables
+    tempIntVec = 0;
+    for(k=1; k<=size(list_UpToA) + size(list_UpToB)+3; k++)
+    {tempIntVec[k] = 1;}
+    clearSlateRingList[3] =
+      list(list("lp",tempIntVec),list("C",intvec(0)));
+    if (size(tempSringlist[1][3][1]) == 0)
+    {//No values in there before
+      tempSringlist[1][3][1] =
+    list("lp", tempIntVec);
+      tempSringlist[1][4] = ideal(0);
+    }//No values in there before
+    else
+    {//there were other parameters
+      tempSringlist[1][3][1][2] = tempSringlist[1][3][1][2], tempIntVec;
+    }//there were other parameters
+    attrib(tempSringlist, "isLetterplaceRing", attrib(r,"isLetterplaceRing"));
+    attrib(tempSringlist, "maxExp", 1);
+    if (defined(S)) {
+      kill S;
+    }
+    def S = ring(tempSringlist); setring S;
+    attrib(S, "uptodeg", lpDegBound(r));
+    attrib(S, "isLetterplaceRing", attrib(r,"isLetterplaceRing"));
+    dbprint(p,dbprintWhitespace+"Done generating ring S:");
+    dbprint(p,dbprintWhitespace+string(S));
+    dbprint(p,dbprintWhitespace+"Generate the ansatz.");
+    dbprint(p,dbprintWhitespace+"The new ring is: " + string(basering));
+    setring(S);
+    poly h = imap(r, h);
+    poly a = imap(r,tempA);
+    poly b = imap(r,tempB);
+    if (!defined(list_UpToA))
+    {list list_UpToA = imap(r,list_UpToA);}
+    if (!defined(list_UpToB))
+    {list list_UpToB = imap(r,list_UpToB);}
+    b = b*par(size(list_UpToA)+size(list_UpToB)+3);
+    for (k = size(list_UpToB); k>0; k--)
+    {b = b + par(size(list_UpToA)+2+k)*list_UpToB[k];}
+    b = b + par(size(list_UpToA) + 2);
+    dbprint(p,dbprintWhitespace + "The ansatz for b is " + string(b));
+    for (k = size(list_UpToA); k>0; k--)
+    {a = a + par(k+1)*list_UpToA[k];}
+    a = a + par(1);
+    dbprint(p,dbprintWhitespace + "The ansatz for a is " + string(a));
+    poly ansatzPoly = a*b - h;
+    dbprint(p,dbprintWhitespace + "The ansatzpoly is " + string(ansatzPoly));
+    ideal listOfRelations = coeffs(ansatzPoly, var(1));
+    for (k = 2;k<=nvars(r);k++)
+    {listOfRelations = coeffs(listOfRelations,var(k));}
+    setring(r);
+    W = ring(clearSlateRingList); // comm ring of coeffs of the ansatz
+    W2 = W+r; // first coeffs, then orig letterplace vars
+    setring(W);
+    ideal listOfRelations = imap(S, listOfRelations);
+    option(redSB);
+    option(redTail);
+    dbprint(p,dbprintWhitespace + "Calculating the solutions of:");
+    dbprint(p,listOfRelations);
+    if (!defined(sol))
+    {
+      def sol = facstd(listOfRelations);
+    }
+    else
+    {
+      sol = facstd(listOfRelations);
+    }
+    dbprint(p,dbprintWhitespace + "Filtering the solutions that are " +
+      "not in the base-field.");
+    for(k = 1; k <=size(sol);k++)
+    {//filtering what is not in the ground-field
+      filterFlag = 0;
+      for (l=1; l<=size(sol[k]); l++)
+      {
+        if ((deg(sol[k][l])>1) or ((sol[k][l]/leadcoef(sol[k][l])==1)))
+        {//Not in the ground field
+          filterFlag = 1;
+          break;
+        }//Not in the ground field
+      }
+      if (filterFlag or (vdim(std(sol[k]))<0))
+      {//In this case, we can delete that whole entry and move on
+        sol= delete(sol,k);
+        continue;
+      }//In this case, we can delete that whole entry and move on
+    }//filtering what is not in the ground-field
+    dbprint(p,dbprintWhitespace + "Solutions for the coefficients are:");
+    dbprint(p,sol);
+    setring S;
+    ideal a_coef; jj=1;
+    while (a[jj]!=0)
+    {
+      a_coef[jj]=leadcoef(a[jj]);
+      jj++;
+    }
+    ideal b_coef;
+    jj=1;
+    while (b[jj]!=0)
+    {
+      b_coef[jj]=leadcoef(b[jj]);
+      jj++;
+    }
+    setring W; //W = ring of coeffs_variables
+    ideal a_coef = imap(S, a_coef);
+    ideal b_coef = imap(S, b_coef);
+    sizeOfSol = size(sol);
+    if (!defined(tempResultCoeffs)) {
+      list tempResultCoeffs;
+    }
+    tempResultCoeffs = list();
+    for (k=1; k<=sizeOfSol; k++)
+    {
+      sol[k] = std(sol[k]);
+      tempResultCoeffs = insert(tempResultCoeffs, list(
+      NF(a_coef, sol[k]), // element-wise
+      NF(b_coef, sol[k]))); // element-wise
+    }
+    setring S;
+    if(!defined(tempResultCoeffs)) {
+      list tempResultCoeffs = imap(W, tempResultCoeffs);
+    }
+    if (!(defined(tempResult)))
+    {list tempResult;}
+    poly ared;
+    poly bred;
+    for (k = 1; k <= size(tempResultCoeffs); k++)
+    {//Creating the resulting polynomials with the respective coeffs.
+      jj=1;
+      ared=0;
+      bred=0;
+      while (a[jj]!=0)
+      {//Going through all monomials of a
+        ared= ared+leadcoef(tempResultCoeffs[k][1][jj])*leadmonom(a[jj]);
+        jj++;
+      }//Going through all monomials of a
+      jj=1;
+      while (b[jj]!=0)
+      {//Going through all monomials of b
+        bred= bred+leadcoef(tempResultCoeffs[k][2][jj])*leadmonom(b[jj]);
+        jj++;
+      }//Going through all monomials of b
+      tempResult = insert(tempResult,list(ared,bred));
+    }//Creating the resulting polynomials with the respective coeffs.
+    setring(r);
+    if (!defined(tempResult))
+    {def tempResult = imap(S,tempResult);}
+    for (k=1; k<= size(tempResult);k++)
+    {
+      result = insert(result,tempResult[k]);
+    }
+    kill tempResult;
+    clearSlateRingList[2] = list();
+    clearSlateRingList[3] = list();
+    tempSringlist = ringlist(r);
+  }//Iterating over all two-combinations in the set M
+  if(size(result)==0)
+  {
+    return (list(list(h)));
+  }
+  return(delete_duplicates_noteval_and_sort(result));
+}//proc ncfactor_letterplace_poly_s
+
+
+static proc test_ncfactor_letterplace_poly_s()
+"Tests the basic functionality."
+{//proc test_ncfactor_letterplace_poly_s()
+  int result = 1;
+  ring r = 0,(x,y,z),dp;
+  int d =4; // degree bound
+  def R = makeLetterplaceRing(d);
+  setring R;
+  //TEST 1: power of 2
+  poly f1 = (x + y)*(x + y);
+  list obtained = ncfactor_letterplace_poly_s(f1);
+  list expected = sortFactorizations(
+    list(
+      list(x + y, x + y)
+      ));
+  if (!isListEqual(expected,obtained))
+  {
+    print("Test 1 for ncfactor_letterplace_poly_s failed.");
+    print("Expected:\n");
+    print(expected);
+    print("obtained:\n");
+    print(obtained);
+    result = 0;
+  }
+  //TEST 2: Monomial
+  f1 = x*z;
+  obtained = ncfactor_letterplace_poly_s(f1);
+  expected = sortFactorizations(
+    list(
+      list(x, z)
+      ));
+  if (!isListEqual(expected,obtained))
+  {
+    print("Test 2 for ncfactor_letterplace_poly_s failed.");
+    print("Expected:\n");
+    print(expected);
+    print("obtained:\n");
+    print(obtained);
+    result = 0;
+  }
+  //TEST 3: Generic product with all variables
+  f1 = (x*y + z*x)*(x+ z+ y);
+  obtained = ncfactor_letterplace_poly_s(f1);
+  expected = sortFactorizations(
+    list(
+      list(
+      x*y + z*x,
+      x+ z+ y))
+      );
+  if (!isListEqual(expected,obtained))
+  {
+    print("Test 3 for ncfactor_letterplace_poly_s failed.");
+    print("Expected:\n");
+    print(expected);
+    print("obtained:\n");
+    print(obtained);
+    result = 0;
+  }
+  //TEST 4: More than one factorization
+  f1 = x*y*x + x;
+  obtained = ncfactor_letterplace_poly_s(f1);
+  expected = sortFactorizations(
+    list(
+      list(x, y*x + 1),
+      list(x*y + 1, x))
+      );
+  if (!isListEqual(expected,obtained))
+  {
+    print("Test 4 for ncfactor_letterplace_poly_s failed.");
+    print("Expected:\n");
+    print(expected);
+    print("obtained:\n");
+    print(obtained);
+    result = 0;
+  }
+  return (result);
+}//proc test_ncfactor_letterplace_poly_s()
+
+static proc ncfactor_without_opt_letterplace(poly h)
+"USAGE: ncfactor_without_opt_letterplace(h); h is a polynomial in a
+        letterplace ring over a field k.
+RETURN: list(list)
+PURPOSE: Compute all factorizations of h, without making any
+         sanity-checks
+THEORY: Implements an ansatz-driven factorization method as outlined
+by Bell, Heinle and Levandovskyy in \"On Noncommutative Finite
+Factorization Domains\".
+ASSUME:
+- the basering is a Letterplace ring.
+- k is a ring, such that factorize can factor any univariate and
+  multivariate commutative polynomial over k.
+- There exists at least one variable in the ring.
+- h is not a constant or 0.
+NOTE:
+- Every entry of the output list is a list with factors for one possible factorization.
+  The first factor is always a constant (1, if no nontrivial constant
+  could be excluded).
+SEE ALSO: facWeyl, facSubWeyl, testNCfac, ncfactor
+"{//ncfactor_without_opt_letterplace
+  int p = printlevel-voice+2;
+  int i; int j; int k; int l;
+  string dbprintWhitespace = "";
+  for (i = 1; i<=voice;i++)
+  {dbprintWhitespace = dbprintWhitespace + " ";}
+  number commonCoefficient = content(h);
+  poly hath = h/commonCoefficient;
+  dbprint(p,dbprintWhitespace + "Calculating all possibilities of h as
+ a combination of two factors.");
+  list result = ncfactor_letterplace_poly_s(hath);
+  result = delete_duplicates_noteval_and_sort(result);
+  dbprint(p,dbprintWhitespace + "Done. The result is:");
+  dbprint(p,result);
+  dbprint(p,dbprintWhitespace+"Recursively check factors for
+ irreducibility");
+  list recursivetemp;
+  int changedSomething;
+  for(i = 1; i<=size(result);i++)
+  {//recursively factorize factors
+    if(size(result[i])>1)
+    {//Nontrivial factorization
+      for (j=1;j<=size(result[i]);j++)
+      {//Factorize every factor
+        recursivetemp = ncfactor_letterplace_poly_s(result[i][j]);
+        recursivetemp = delete_duplicates_noteval(recursivetemp);
+        changedSomething = 0;
+        for(k=1; k<=size(recursivetemp);k++)
+        {//insert factorized factors
+          if(size(recursivetemp[k])>1)
+          {//nontrivial
+            changedSomething = 1;
+            result = insert(result,result[i],i);
+            for(l = size(recursivetemp[k]);l>=1;l--)
+            {
+              result[i+1] = insert(result[i+1],recursivetemp[k][l],j);
+            }
+            result[i+1] = delete(result[i+1],j);
+          }//nontrivial
+        }//insert factorized factors
+        if (changedSomething)
+        {break;}
+      }//Factorize every factor
+      if(changedSomething)
+      {
+        result = delete(result,i);
+        continue;
+      }
+    }//Nontrivial factorization
+  }//recursively factorize factors
+  dbprint(p,dbprintWhitespace +" Done");
+  dbprint(p,dbprintWhitespace + "Removing duplicates from the list");
+  result = delete_duplicates_noteval_and_sort(result);
+  for (i = 1; i<=size(result);i++)
+  {//Putting the content everywhere
+    result[i] = insert(result[i],commonCoefficient);
+  }//Putting the content everywhere
+  result = normalizeFactors(result);
+  result = delete_duplicates_noteval_and_sort(result);
+  dbprint(p,dbprintWhitespace +" Done");
+  return(result);
+}//ncfactor_without_opt_letterplace
+
+static proc test_ncfactor_without_opt_letterplace()
+"Tests the basic functionality."
+{//test_ncfactor_without_opt_letterplace
+  int result = 1;
+  ring r = 0,(x,y,z),dp;
+  int d =4; // degree bound
+  def R = makeLetterplaceRing(d);
+  setring R;
+  //TEST 1: power of 2
+  poly f1 = 4*(x + y)*(x + y);
+  list obtained = ncfactor_without_opt_letterplace(f1);
+  list expected = sortFactorizations(
+    list(
+      list(number(4), x + y, x + y)
+      ));
+  if (!isListEqual(expected,obtained))
+  {
+    print("Test 1 for ncfactor_without_opt_letterplace failed.");
+    print("Expected:\n");
+    print(expected);
+    print("obtained:\n");
+    print(obtained);
+    result = 0;
+  }
+  //TEST 2: Monomial
+  f1 = 11*x*z;
+  obtained = ncfactor_without_opt_letterplace(f1);
+  expected = sortFactorizations(
+    list(
+      list(number(11), x, z)
+      ));
+  if (!isListEqual(expected,obtained))
+  {
+    print("Test 2 for ncfactor_without_opt_letterplace failed.");
+    print("Expected:\n");
+    print(expected);
+    print("obtained:\n");
+    print(obtained);
+    result = 0;
+  }
+  //TEST 3: Generic product with all variables
+  f1 = (2*x*y + 4*z*x)*(x+z+y);
+  obtained = ncfactor_without_opt_letterplace(f1);
+  expected = sortFactorizations(
+    list(
+      list(number(2), x*y + 2*z*x, x+z+y)
+      ));
+  if (!isListEqual(expected,obtained))
+  {
+    print("Test 3 for ncfactor_without_opt_letterplace failed.");
+    print("Expected:\n");
+    print(expected);
+    print("obtained:\n");
+    print(obtained);
+    result = 0;
+  }
+  //TEST 4: More than one factorization
+  f1 = 6*x*y*x + 9*x;
+  obtained = ncfactor_without_opt_letterplace(f1);
+  expected = sortFactorizations(
+    list(
+      list(number(3), x, 2*y*x + 3),
+      list(number(3), 2*x*y + 3, x)
+      ));
+  if (!isListEqual(expected,obtained))
+  {
+    print("Test 4 for ncfactor_without_opt_letterplace failed.");
+    print("Expected:\n");
+    print(expected);
+    print("obtained:\n");
+    print(obtained);
+    result = 0;
+  }
+  //Test 5: At least one recursive call
+  f1 = f1*(x + y);
+  obtained = ncfactor_without_opt_letterplace(f1);
+  expected = sortFactorizations(
+    list(
+      list(number(3), x, 2*y*x + 3, x + y),
+      list(number(3), 2*x*y + 3, x, x + y)
+      ));
+  if (!isListEqual(expected,obtained))
+  {
+    print("Test 5 for ncfactor_without_opt_letterplace failed.");
+    print("Expected:\n");
+    print(expected);
+    print("obtained:\n");
+    print(obtained);
+    result = 0;
+  }
+  return (result);
+}//test_ncfactor_without_opt_letterplace
+
+
 //==================================================
 // EASY EXAMPLES FOR WEYL ALGEBRA
@@ -12217 +13252 @@
 
  /* recent bufgixes (2) Jan 2018; exs from Viktor and Johannes Hoffmann
- // Original bug: found only (x+d)^2*x as faktorization
+ // Original bug: found only (x+d)^2*x as factorization
 LIB "nctools.lib";
 ring r = 0,(x,d),dp;
@@ -12225 +13260 @@
 
 //======================================================================
-// Hard examples not yet calculatable in feasible amount of time
+// Hard examples not yet computable in feasible amount of time
 //======================================================================