Changeset 454d97a in git


Ignore:
Timestamp:
Feb 11, 2019, 9:08:09 PM (5 years ago)
Author:
Karim Abou Zeid <karim23697@…>
Branches:
(u'fieker-DuVal', '117eb8c30fc9e991c4decca4832b1d19036c4c65')(u'spielwiese', '3720ae8bfcff4a4649ee98a15552089151d2d59b')
Children:
6dec960990df047d162538a2bdcc48be39657b52
Parents:
e5c5654e20688cb941272427f370c757f08c21b1d4544a591cc6bf2a1fba681067422f3056ef5eab
Message:
Merge remote-tracking branch 'upstream/spielwiese' into bracket
Files:
17 edited

Legend:

Unmodified
Added
Removed
  • Singular/LIB/fpadim.lib

    re5c565 r454d97a  
    1515
    1616KEYWORDS: finitely presented algebra; Letterplace Groebner basis; K-basis; K-dimension; Hilbert series
    17 
    18 PROCEDURES:
    19 lpKDimCheck(G);            checks whether the K-dimension of A/<G> is finite
    20 lpKDim(G[,d,n]);           computes the K-dimension of A/<G>
    21 lpMonomialBasis(d, donly, J); computes a list of monomials not contained in J
    22 lpHilbert(G[,d,n]);        computes the truncated Hilbert series of A/<G>
    23 lpSickleDim(G[,d,n]);      computes the mistletoes and the K-dimension of A/<G>
    2417
    2518NOTE:
     
    7366[Stu] G. Studzinski: Dimension computations in non-commutative,
    7467associative algebras, Diploma thesis, RWTH Aachen, 2010.
     68
     69PROCEDURES:
     70lpKDimCheck(G);            checks whether the K-dimension of A/<G> is finite
     71lpKDim(G[,d,n]);           computes the K-dimension of A/<G>
     72lpMonomialBasis(d, donly, J); computes a list of monomials not contained in J
     73lpHilbert(G[,d,n]);        computes the truncated Hilbert series of A/<G>
     74lpSickleDim(G[,d,n]);      computes the mistletoes and the K-dimension of A/<G>
    7575
    7676SEE ALSO: freegb_lib, fpaprops_lib, ncHilb_lib
  • Singular/LIB/fpalgebras.lib

    re5c565 r454d97a  
    7878RETURN:  ideal
    7979ASSUME: basering has a letterplace ring structure and
    80 @*          A is a generalized Cartan matrix with integer entries
     80        A is a generalized Cartan matrix with integer entries
    8181PURPOSE: compute the ideal of Serre's relations associated to A
    8282EXAMPLE: example serreRelations; shows examples
     
    145145RETURN:  ring (and ideal)
    146146PURPOSE: compute the inhomogeneous Serre's relations associated to A in given
    147 @*       variable names
     147         variable names
    148148ASSUME: three ideals in the input are of the same sizes and contain merely
    149 @* variables which are interpreted as follows: N resp. P stand for negative
    150 @* resp. positive roots, C stand for Cartan elements. d is the degree bound for
    151 @* letterplace ring, which will be returned.
    152 @* The matrix A is a generalized Cartan matrix with integer entries
    153 @* The result is the ideal called 'fsRel' in the returned ring.
     149  variables which are interpreted as follows: N resp. P stand for negative
     150  resp. positive roots, C stand for Cartan elements. d is the degree bound for
     151  letterplace ring, which will be returned.
     152  The matrix A is a generalized Cartan matrix with integer entries
     153  The result is the ideal called 'fsRel' in the returned ring.
    154154EXAMPLE: example fullSerreRelations; shows examples
    155155"
     
    363363RETURN:  ring (and exports ideal)
    364364PURPOSE: compute the ideal of Adem relations for i<2j in characteristic 0
    365 @*  the ideal is exported under the name AdemRel in the output ring
     365    the ideal is exported under the name AdemRel in the output ring
    366366EXAMPLE: example ademRelations; shows examples
    367367"
  • Singular/LIB/fpaprops.lib

    re5c565 r454d97a  
    5555"USAGE: lpNoetherian(G); G an ideal in a Letterplace ring
    5656RETURN: int
    57 @*      0 not Noetherian
    58 @*      1 left Noetherian
    59 @*      2 right Noetherian
    60 @*      3 Noetherian
    61 @*      4 weak Noetherian
     57      0 not Noetherian
     58      1 left Noetherian
     59      2 right Noetherian
     60      3 Noetherian
     61      4 weak Noetherian
    6262PURPOSE: Check whether the monomial algebra A/<LM(G)> is (left/right) noetherian
    6363ASSUME: - basering is a Letterplace ring
    64 @*      - G is a Groebner basis
     64      - G is a Groebner basis
    6565THEORY: lpNoetherian works with the monomial algebra A/<LM(G)>.
    6666If it gives an affirmative answer for one of the properties, then it
     
    644644start. The parameter visited, cyclic and path should be 0.
    645645RETURN: int
    646 @*:     Maximal number of distinct cycles
     646     Maximal number of distinct cycles
    647647PURPOSE: Calculate the maximal number of distinct cycles in a single path starting at v
    648648ASSUME: Basering is a Letterplace ring
     
    730730proc lpUfGraph(ideal G, list #)
    731731"USAGE: lpUfGraph(G); G a set of monomials in a letterplace ring.
    732 @*      lpUfGraph(G,1); G a set of monomials in a letterplace ring.
    733732RETURN: intmat or list
    734733NOTE: lpUfGraph(G); returns intmat. lpUfGraph(G,1); returns list L with L[1] an intmat and L[2] an ideal.
     
    882881RETURN: int
    883882PURPOSE: Determines the Gelfand Kirillov dimension of A/<G>
    884 @*       -1 means positive infinite
     883       -1 means positive infinite
    885884ASSUME: - basering is a Letterplace ring
    886 @*      - G is a Groebner basis
     885      - G is a Groebner basis
    887886"
    888887{
  • Singular/LIB/freegb.lib

    re5c565 r454d97a  
    2626lpDegBound(R);                   returns the degree bound of a letterplace ring
    2727lpVarBlockSize(R);               returns the size of the letterplace blocks
    28 
    2928lpDivision(f,I);                 two-sided division with remainder
    3029lpGBPres2Poly(L,I);              reconstructs a polynomial from the output of lpDivision
    31 
    3230isOrderingShiftInvariant(i);     tests shift-invariance of the monomial ordering
    3331isVar(p);                        check whether p is a power of a single variable
    34 
    3532makeLetterplaceRing(d);          (deprecated, use freeAlgebra) creates a Letterplace ring out of given data
    3633letplaceGBasis(I);               (deprecated, use twostd) two-sided Groebner basis of a letterplace ideal I
     
    9087RETURN: ring with special attributes set
    9188PURPOSE: sets attributes for a letterplace ring:
    92 @*      'isLetterplaceRing' = true, 'uptodeg' = d, 'lV' = b, where
    93 @*      'uptodeg' stands for the degree bound,
    94 @*      'lV' for the number of variables in the block 0.
     89  'isLetterplaceRing' = true, 'uptodeg' = d, 'lV' = b, where
     90  'uptodeg' stands for the degree bound,
     91  'lV' for the number of variables in the block 0.
    9592NOTE: Activate the resulting ring by using @code{setring}
    9693"
     
    330327RETURN:  int
    331328PURPOSE: check, whether leading monomial of p is a power of a single variable
    332 @* from the basering. Returns the exponent or 0 if p is multivariate.
     329  from the basering. Returns the exponent or 0 if p is multivariate.
    333330EXAMPLE: example isVar; shows examples
    334331"
     
    373370"USAGE: letplaceGBasis(I);  I an ideal/module
    374371RETURN: ideal/module
    375 ASSUME: basering is a Letterplace ring, input consists of Letterplace
    376 @*      polynomials
    377 PURPOSE: compute the two-sided Groebner basis of I via Letterplace
    378 @*       algorithm (legacy routine)
     372ASSUME: basering is a Letterplace ring, input consists of Letterplace polynomials
     373PURPOSE: compute the two-sided Groebner basis of I via Letterplace algorithm (legacy routine)
    379374NOTE: the degree bound for this computation is read off the letterplace
    380 @*    structure of basering
     375      structure of basering
    381376EXAMPLE: example letplaceGBasis; shows examples
    382377"
     
    417412PURPOSE:compute the Lie bracket [a,b] = ab - ba between letterplace polynomials
    418413NOTE: if N>1 is specified, then the left normed bracket [a,[...[a,b]]]] is
    419 @*    computed.
     414computed.
    420415EXAMPLE: example lieBracket; shows examples
    421416"
     
    524519RETURN:  ring
    525520ASSUME: L has a special form. Namely, it is a list of modules, where
    526 
    527521 - each generator of every module stands for a monomial times coefficient in
    528 @* free algebra,
    529 
     522   free algebra,
    530523 - in such a vector generator, the 1st entry is a nonzero coefficient from the
    531 @* ground field
    532 
     524   ground field
    533525 - and each next entry hosts a variable from the basering.
    534526PURPOSE: compute the two-sided Groebner basis of an ideal, encoded by L
    535 @* in the free associative algebra, up to degree d
     527  in the free associative algebra, up to degree d
    536528NOTE: Apply @code{lst2str} to the output in order to obtain a better readable
    537 @*    presentation
     529   presentation
    538530EXAMPLE: example freeGBasis; shows examples
    539531"
     
    31693161RETURN: int
    31703162NOTE: Tests whether the ordering of the current ring is shift invariant, which is the case, when LM(p) > LM(p') for all p and p' where p' is p shifted by any number of places.
    3171 @*      If withHoles != 0 even Letterplace polynomials with holes (eg. x(1)*y(4)) are considered.
     3163
     3164If withHoles != 0 even Letterplace polynomials with holes (eg. x(1)*y(4)) are considered.
    31723165ASSUME: - basering is a Letterplace ring.
    31733166"
  • Singular/LIB/ncfactor.lib

    re5c565 r454d97a  
    11///////////////////////////////////////////////////////////
    2 version="version ncfactor.lib 4.1.1.0 Jan_2018 "; // $Id$
     2version="version ncfactor.lib 4.0.0.0 _2017 "; //$Id$
    33category="Noncommutative";
    44info="
    55LIBRARY: ncfactor.lib  Tools for factorization in some noncommutative algebras
    6 AUTHORS: Albert Heinle,     aheinle@uwaterloo.ca
    7 @*       Viktor Levandovskyy,     levandov@math.rwth-aachen.de
    8 
    9 OVERVIEW: New methods for factorization on polynomials
    10   are implemented for three types of algebras, all generated by
    11    2*n, n in NN, generators (n'th Weyl, n'th shift and graded polynomials in n'th q-Weyl algebras)
    12    over a field K.
     6AUTHORS: Albert Heinle,     aheinle at uwaterloo.ca
     7@*       Viktor Levandovskyy,     levandov at math.rwth-aachen.de
     8
     9OVERVIEW: In this library, new methods for factorization on polynomials
     10@* are implemented for several types of algebras, namely
     11@* - finitely presented (and also free) associative algebras (Letterplace subsystem)
     12@* - G-algebras (Plural subsystem), including (q)-Weyl and (q)-shift algebras in 2n variables
     13@* The determination of the best algorithm available for users input is done
     14@* automatically in the procedure ncfactor().
     15
    1316@* More detailled description of the algorithms and related publications can be found at
    14    @url{https://cs.uwaterloo.ca/\~aheinle/}.
     17@url{https://cs.uwaterloo.ca/\~aheinle/}.
    1518
    1619PROCEDURES:
    17   ncfactor(h);               Factorization in any G-algebra.
     20  ncfactor(h);               Factorization in any finitely presented algebra (incl. G-algebra)
    1821  facWeyl(h);                Factorization in the n'th Weyl algebra
    1922  facFirstWeyl(h);           Factorization in the first Weyl algebra
     
    3740LIB "solve.lib"; //for solve
    3841LIB "poly.lib"; //for content
     42LIB "fpadim.lib"; //for letterplace
    3943
    4044proc tst_ncfactor()
     
    128132  }
    129133  print("Successful.");
    130   print("Testing Min");
    131   if (!test_Min())
    132   {
    133     ERROR("Min is not working properly.");
    134   }
    135   print("Successful.");
    136134  print("Testing isListEqual");
    137135  if (!test_isListEqual())
     
    410408  }
    411409  print("Successful.");
    412   print("Testing delete_duplicates_noteval_and_sort");
     410  print("Testing getMaxDegreeVecLetterPlace");
     411  if(!test_getMaxDegreeVecLetterPlace())
     412  {
     413    ERROR("getMaxDegreeVecLetterPlace is not working properly.");
     414  }
     415  print("Successful.");
     416  print("Testing wordsWithMaxAppearance");
     417  if(!test_wordsWithMaxAppearance())
     418  {
     419    ERROR("wordsWithMaxAppearance is not working properly.");
     420  }
     421  print("Successful.");
     422  print("Testing monsSmallerThanLetterPlace");
     423  if(!test_monsSmallerThanLetterPlace())
     424  {
     425    ERROR("monsSmallerThanLetterPlace is not working properly.");
     426  }
     427  print("Successful.");
     428  print("Testing ncfactor_letterplace_poly_s");
     429  if(!test_ncfactor_letterplace_poly_s())
     430  {
     431    ERROR("ncfactor_letterplace_poly_s is not working properly.");
     432  }
     433  print("Successful.");
     434  print("Testing ncfactor_without_opt_letterplace");
     435  if(!test_ncfactor_without_opt_letterplace())
     436  {
     437    ERROR("ncfactor_without_opt_letterplace is not working properly.");
     438  }
     439  print("Successful.");
    413440  print("All tests ran successfully.");
    414441}
     
    20412068  return(result);
    20422069}//testing increment_intvec
    2043 
    2044 
    2045 //I know that Singular has this function in the package
    2046 //qhmoduli.lib. But I don't see the reason why I should clutter my
    2047 //namespace with functions to study Moduli Spaces of
    2048 //Semi-Quasihomogeneous Singularities (in case somebody wonders)
    2049 static proc Min(def lst)
    2050 "USAGE: Min(lst); list is an iterable element (list/ideal/intvec)
    2051         containing ordered elements.
    2052 PURPOSE: returns the minimal element in lst
    2053 ASSUME: lst contains at least one element
    2054 "{//proc Min
    2055   def minElem = lst[1];
    2056   int i;
    2057   for (i = 2; i<=size(lst);i++)
    2058   {
    2059     if (lst[i]<minElem)
    2060     {
    2061       minElem = lst[i];
    2062     }
    2063   }
    2064   return (minElem);
    2065 }//proc Min
    2066 
    2067 
    2068 static proc test_Min()
    2069 {//Testing Min
    2070   int result = 1;
    2071   //Test 1: One element list
    2072   int expected= 1;
    2073   int obtained = Min(list(1));
    2074   if (expected!=obtained)
    2075   {
    2076     print("Test 1 for Min failed.");
    2077     print("Expected:\n");
    2078     print(expected);
    2079     print("obtained:\n");
    2080     print(obtained);
    2081     result = 0;
    2082   }
    2083   //Test 2: Two element list, first one is Min
    2084   expected = 5;
    2085   obtained = Min(list(5,8));
    2086   if (expected!=obtained)
    2087   {
    2088     print("Test 2 for Min failed.");
    2089     print("Expected:\n");
    2090     print(expected);
    2091     print("obtained:\n");
    2092     print(obtained);
    2093     result = 0;
    2094   }
    2095   //Test 3: Two element list, second one is Min
    2096   expected = 5;
    2097   obtained = Min(list(8,5));
    2098   if (expected!=obtained)
    2099   {
    2100     print("Test 3 for Min failed.");
    2101     print("Expected:\n");
    2102     print(expected);
    2103     print("obtained:\n");
    2104     print(obtained);
    2105     result = 0;
    2106   }
    2107   //Test 4: A lot of elements, Min randomly in between.
    2108   expected = -11;
    2109   obtained = Min(list(5,8,7,2,8,0,-11,0,25));
    2110   if (expected!=obtained)
    2111   {
    2112     print("Test 4 for Min failed.");
    2113     print("Expected:\n");
    2114     print(expected);
    2115     print("obtained:\n");
    2116     print(obtained);
    2117     result = 0;
    2118   }
    2119   return(result);
    2120 }//Testing Min
    2121 
    21222070
    21232071static proc isListEqual(list l1, list l2)
     
    33403288"
    33413289{//isInCommutativeSubRing
     3290  int i; int j; int k;
     3291  intvec tempIntVec;
     3292  int previouslyEncounteredVar = -1;
     3293  if ( attrib(basering, "isLetterplaceRing") >= 1)
     3294  {//separate department: letterplace case
     3295    for (i = 1; i<=size(h); i++)
     3296    {//iterating over the monomials of h
     3297      tempIntVec = lp2iv(h[i]);
     3298      if (size(tempIntVec) > 1)
     3299      {//nontrivial monomial
     3300    j = tempIntVec[1];
     3301    if (previouslyEncounteredVar != -1 and j != previouslyEncounteredVar)
     3302    {//In this case, the previously encountered var is not equal to this one
     3303      return(0);
     3304    }//In this case, the previously encountered var is not equal to this one
     3305    previouslyEncounteredVar = j;
     3306    for (k = 2; k <= size(tempIntVec); k++)
     3307    {//checking if each entry in the intvec is the same
     3308      if (tempIntVec[k]!=j)
     3309      {//more than one variable in monomial
     3310        return(0);
     3311      }//more than one variable in monomial
     3312    }//checking if each entry in the intvec is the same
     3313      }//nontrivial monomial
     3314      else
     3315      {i++; continue;}
     3316    }//iterating over the monomials of h
     3317    return(1);
     3318  }//separate department: letterplace case
    33423319  list tempRingList = ringlist(basering);
    33433320  if (size(tempRingList)<=4)
     
    33463323  }//In this case, the given ring was commutative
    33473324  list appearing_variables;
    3348   int i; int j;
    33493325  intvec degreeIntVec;
    33503326  for (i = 1; i<=nvars(basering);i++)
     
    34263402  {
    34273403    print("Test 4 for isInCommutativeSubRing failed.");
     3404    print("Expected:\n");
     3405    print(expected);
     3406    print("obtained:\n");
     3407    print(obtained);
     3408    result = 0;
     3409  }
     3410  return(result);
     3411  //Test 5: Letterplace ring, negative example
     3412  ring r2 = 0,(x,y,z),dp;
     3413  int d =4; // degree bound
     3414  def R2 = makeLetterplaceRing(d);
     3415  setring R2;
     3416  expected = 0;
     3417  obtained = isInCommutativeSubRing(x + y);
     3418  if (expected !=obtained)
     3419  {
     3420    print("Test 5 for isInCommutativeSubRing failed.");
     3421    print("Expected:\n");
     3422    print(expected);
     3423    print("obtained:\n");
     3424    print(obtained);
     3425    result = 0;
     3426  }
     3427  //Test 6: Letterplace ring, positive example
     3428  expected = 1;
     3429  obtained = isInCommutativeSubRing(x + x*x);
     3430  if (expected !=obtained)
     3431  {
     3432    print("Test 6 for isInCommutativeSubRing failed.");
     3433    print("Expected:\n");
     3434    print(expected);
     3435    print("obtained:\n");
     3436    print(obtained);
     3437    result = 0;
     3438  }
     3439  //Test 7: Letterplace ring, previous bug
     3440  expected = 0;
     3441  obtained = isInCommutativeSubRing(x*x - y*y);
     3442  if (expected !=obtained)
     3443  {
     3444    print("Test 7 for isInCommutativeSubRing failed.");
    34283445    print("Expected:\n");
    34293446    print(expected);
     
    34573474  if (deg(h)<=0)
    34583475  {
    3459     dbprint(p,dbprintWhitespace + "h is a constant. Returning
    3460  immediately");
     3476    dbprint(p,dbprintWhitespace + "h is a constant. Returning immediately");
    34613477    return(list(list(h)));
    34623478  }
    34633479  def r = basering;
    34643480  list factorizeOutput;
    3465   if (size(ringlist(basering))<=4)
     3481  if (size(ringlist(basering))<=4 && (attrib(r, "isLetterplaceRing") == 0) )
    34663482  {//commutative ring case
    3467     dbprint(p,dbprintWhitespace + "We are in a commutative
    3468  ring. Factoring h using factorize.");
     3483    dbprint(p,dbprintWhitespace + "We are in a commutative ring. Factoring h using factorize.");
    34693484    factorizeOutput = factorize(h);
    34703485  }//commutative ring case
    34713486  else
    34723487  {//commutative subring case;
    3473     dbprint(p,dbprintWhitespace + "We are in a commutative
    3474  subring. Generating commutative ring..");
    3475     def rList = ringlist(basering);
    3476     rList = delete(rList,5);
    3477     rList = delete(rList,5);
    3478     def tempRing = ring(rList);
    3479     setring(tempRing);
    3480     poly h = imap(r,h);
    3481     dbprint(p, dbprintWhitespace+"Factoring h in commutative ring.");
    3482     list tempResult = factorize(h);
    3483     setring(r);
    3484     factorizeOutput = imap(tempRing,tempResult);
     3488    dbprint(p,dbprintWhitespace + "We are in a commutative subring. Generating commutative ring.");
     3489    if (attrib(r, "isLetterplaceRing") == 0)
     3490    {//G-algebra case
     3491      def rList = ringlist(basering);
     3492      rList = delete(rList,5);
     3493      rList = delete(rList,5);
     3494      def tempRing = ring(rList);
     3495      setring(tempRing);
     3496      poly h = imap(r,h);
     3497      dbprint(p, dbprintWhitespace+"Factoring h in commutative ring.");
     3498      list tempResult = factorize(h);
     3499      setring(r);
     3500      factorizeOutput = imap(tempRing,tempResult);
     3501    }//G-algebra case
     3502    else
     3503    {//Letterplace case
     3504      int theRightVar = lp2iv(h[1])[1];
     3505      list commFactInIv = list();
     3506      list tempMonomList = list();
     3507      def rList = ringlist(basering);
     3508      rList[2] = list("@x");
     3509      rList[3] = list(list("dp", intvec(1)),
     3510              list("C", 0));
     3511      def tempRing = ring(rList);
     3512      setring(tempRing);
     3513      ideal tempIdeal;
     3514      for (i=1; i<=nvars(r); i++)
     3515      {tempIdeal[i] = var(1);}
     3516      map fromR = r, tempIdeal;
     3517      poly h = fromR(h);
     3518      dbprint(p, dbprintWhitespace+"Factoring h in commutative ring.");
     3519      list tempResult = factorize(h);
     3520      dbprint(p, dbprintWhitespace+"Done. The result is:");
     3521      dbprint(p, tempResult);
     3522      dbprint(p, dbprintWhitespace+"Now translated into intvec representation:");
     3523      for (i = 1; i <= size(tempResult[1]); i++)
     3524      {//translate all factorizations into lists of intvecs and coeffs
     3525    commFactInIv[i] = list();
     3526    for (j = 1; j <= size(tempResult[1][i]); j++)
     3527    {//iterate over each monomial
     3528      commFactInIv[i][j] = list(leadcoef(tempResult[1][i][j]));
     3529      if (deg(tempResult[1][i][j]) != 0)
     3530      {//a power of @x
     3531        commFactInIv[i][j] = commFactInIv[i][j] + list(theRightVar:deg(tempResult[1][i][j]));
     3532      }//a power of @x
     3533    }//iterate over each monomial
     3534      }//translate all factorizations into lists of intvecs and coeffs
     3535      dbprint(p, commFactInIv);
     3536      setring(r);
     3537      factorizeOutput = imap(tempRing,tempResult);
     3538      list commFactInIv = imap(tempRing, commFactInIv);
     3539      poly tempEntry;
     3540      for (i = 1; i<=size(commFactInIv); i++)
     3541      {
     3542    tempEntry = 0;
     3543    for (j=1; j<=size(commFactInIv[i]); j++)
     3544    {
     3545      if (size(commFactInIv[i][j]) == 1)
     3546      {//simply a number
     3547        tempEntry = tempEntry + commFactInIv[i][j][1];
     3548      }//simply a number
     3549      else
     3550      {
     3551        tempEntry = tempEntry + commFactInIv[i][j][1]*iv2lp(commFactInIv[i][j][2]);
     3552      }
     3553    }
     3554    factorizeOutput[1][i] = tempEntry;
     3555      }
     3556    }//Letterplace case
    34853557  }//commutative subring case;
    3486   dbprint(p,dbprintWhitespace + "Done commutatively factorizing.
    3487  The result is:");
     3558  dbprint(p,dbprintWhitespace + "Done commutatively factorizing. The result isssssss:");
    34883559  dbprint(p,factorizeOutput);
    34893560  dbprint(p,dbprintWhitespace+"Computing all permutations of this factorization.");
     
    35263597  }
    35273598  kill R;
    3528   //Test 2: Non-commutative ring, constant
     3599  //Test 2: G-Algebra, constant
    35293600  ring R = 0,(x,d),dp;
    35303601  def r = nc_algebra(1,1);
     
    35423613  }
    35433614  kill r; kill R;
    3544   //Test 3: Non-commutative ring, definitely commutative subring, irreducible
     3615  //Test 3: G-Algebra, definitely commutative subring, irreducible
    35453616  ring R = 0,(x1,x2,d1,d2),dp;
    35463617  def r = Weyl();
     
    35583629  }
    35593630  kill r; kill R;
    3560   //Test 4: Non-commutative ring, definitely commutative subring,
     3631  //Test 4: G-Algebra, definitely commutative subring,
    35613632  //reducible
    35623633  ring R = 0,(x1,x2,d1,d2),dp;
     
    35793650  }
    35803651  kill r; kill R;
     3652  //Test 5: Letterplace ring, constant
     3653  ring r = 0,(x,y,z),dp;
     3654  int d =4; // degree bound
     3655  def R = makeLetterplaceRing(d);
     3656  setring R;
     3657  list expected = list(list(poly(3445)));
     3658  list obtained = factor_commutative(3445);
     3659  if (!isListEqual(expected,obtained))
     3660  {
     3661    print("Test 5 for factor_commutative failed.");
     3662    print("Expected:\n");
     3663    print(expected);
     3664    print("obtained:\n");
     3665    print(obtained);
     3666    result = 0;
     3667  }
     3668  //Test 6: Letterplace ring, definitely commutative subring, irreducible
     3669  expected = list(list(poly(1), x*x+ 2*x + 2));
     3670  obtained = factor_commutative(x*x+ 2*x + 2);
     3671  if (!isListEqual(expected,obtained))
     3672  {
     3673    print("Test 6 for factor_commutative failed.");
     3674    print("Expected:\n");
     3675    print(expected);
     3676    print("obtained:\n");
     3677    print(obtained);
     3678    result = 0;
     3679  }
     3680  //Test 7: Letterplace ring, definitely commutative subring,
     3681  //reducible
     3682  expected = list(list(poly(1), x*x+ 2*x + 2, x*x- 2*x - 2),
     3683            list(poly(1), x*x- 2*x - 2, x*x+ 2*x + 2));
     3684  obtained = factor_commutative((x*x+ 2*x + 2)*(x*x- 2*x - 2));
     3685  if (!isListEqual(expected,obtained))
     3686  {
     3687    print("Test 7 for factor_commutative failed.");
     3688    print("Expected:\n");
     3689    print(expected);
     3690    print("obtained:\n");
     3691    print(obtained);
     3692    result = 0;
     3693  }
     3694  //Test 8: Letterplace ring, using last variable
     3695  expected = list(list(poly(1), z*z+ 2*z + 2, z*z - 2*z - 2),
     3696            list(poly(1), z*z - 2*z - 2, z*z+ 2*z + 2));
     3697  obtained = factor_commutative((z*z+ 2*z + 2)*(z*z - 2*z - 2));
     3698  if (!isListEqual(expected,obtained))
     3699  {
     3700    print("Test 8 for factor_commutative failed.");
     3701    print("Expected:\n");
     3702    print(expected);
     3703    print("obtained:\n");
     3704    print(obtained);
     3705    result = 0;
     3706  }
    35813707  return(result);
    35823708}//testing factor_commutative
     
    67306856
    67316857  result = delete_duplicates_noteval_and_sort(result);
    6732   //print(M);
    67336858  if (size(result) == 0)
    67346859  {//no factorization found
     
    68947019  }
    68957020  hZeroinR = tempHList;
    6896   //hBetweenDegrees = reverse(hBetweenDegrees);
    68977021  dbprint(p,dbprintWhitespace+" Done!");
    68987022  dbprint(p,dbprintWhitespace+" Moving everything into the ring K[theta]");
     
    82448368  list tempList = list();
    82458369  //First, we are going to deal with our most hated guys: The Coefficients.
    8246   //
    82478370  dbprint(p,dbprintWhitespace + "We get all combinations for the coefficient of the
    82488371maximal homogeneous part");
     
    97469869  rlist[3][2][2]=intvec(0);
    97479870  rlist = insert(rlist,ideal(0),3);
    9748   //The following lines of code will become obsolete once bug #753 in
    9749   //Singular is fixed. Until then, this measure is unfortunately
    9750   //necessary.
    9751   //begin
    9752   intvec perms = 0:nvars(@r);
    9753   for (i =1; i<=nvars(@r);i++)
    9754   {//finding the right position of each input variable
    9755     for (j = 1; j<=size(inpList); j++)
    9756     {
    9757       if (var(i)==inpList[j])
    9758       {//found the correct spot
    9759     perms[i] = j;
    9760     break;
    9761       }//found the correct spot
    9762     }
    9763   }//finding the right position of each input variable
    97649871  def @r2 = ring(rlist);
    97659872  setring(@r2);
    97669873  def @r3 = Weyl();
    97679874  setring(@r3);
    9768   ideal mappingIdeal;
    9769   for (i = 1; i<=size(perms); i++)
    9770   {//generating the mapping ideal
    9771     if (perms[i]>0)
    9772     {//only variables that are in the input list are permitted
    9773       mappingIdeal[i] = var(perms[i]);
    9774     }//only variables that are in the input list are permitted
    9775   }//generating the mapping ideal
    9776   map toR3 = @r, mappingIdeal;
    9777   poly h = toR3(h);
     9875  poly h = imap(@r,h);
    97789876  list result = facWeyl(h);
    97799877  setring(@r);
    9780   ideal mappingIdeal;
    9781   for (i = 1; i<=size(perms);i++)
    9782   {//finding the correct permutation
    9783     for (j = 1; j<=size(perms); j++)
    9784     {//the spot needs to coincide
    9785       if (perms[j]==i)
    9786       {//found it
    9787     mappingIdeal[i] = var(j);
    9788     break;
    9789       }//found it
    9790     }//the spot needs to coincide
    9791   }//finding the correct permutation
    9792   map toR = @r3, mappingIdeal;
    9793   list result = toR(result);
    9794   //end
    9795   //once bug is fixed, please uncomment the following lines and
    9796   //discard the above
    9797   /* def @r2 = ring(rlist); */
    9798   /* setring(@r2); */
    9799   /* def @r3 = Weyl(); */
    9800   /* setring(@r3); */
    9801   /* poly h = imap(@r,h); */
    9802   /* list result = facWeyl(h); */
    9803   /* setring(@r); */
    9804   /* list result = imap(@r3,result); */
     9878  list result = imap(@r3,result);
    98059879  return(result);
    98069880}//proc facSubWeyl
     
    1047410548 - We have n parameters q_1,..., q_n given.
    1047510549
    10476 SEE ALSO: homogfacFirstQWeyl, homogfacFirstQWeyl_all
     10550SEE ALSO: homogfacNthWeyl, homogfacFirstQWeyl, homogfacFirstQWeyl_all
    1047710551"
    1047810552{//proc homogfacNthQWeyl_all
     
    1099211066- There exists at least one variable in the ring.
    1099311067NOTE:
     11068- works for both PLURAL and LETTERPLACE subsystems
    1099411069- Every entry of the output list is a list with factors for one possible factorization.
    1099511070  The first factor is always a constant (1, if no nontrivial constant
     
    1100211077  for (i = 1; i<=voice;i++)
    1100311078  {dbprintWhitespace = dbprintWhitespace + " ";}
    11004   dbprint(p,dbprintWhitespace + "Checking if the field fulfills
     11079  dbprint(p,dbprintWhitespace + "Checking if the field fulfills\
    1100511080 everything we assume.");
    1100611081  if (nvars(basering)<1)
     
    1101011085    if (minpoly !=0)
    1101111086    {
    11012       ERROR("factorize does not support fields of type (p^n,a)");
     11087      ERROR("factorize does not support fields of type (p^n,a) yet");
    1101311088      return list(list());
    1101411089    }
    1101511090  }
    11016   dbprint(p,dbprintWhitespace + "Everything seems to be alright with
     11091  dbprint(p,dbprintWhitespace + "Everything seems to be alright with\
    1101711092 the ground field.");
    1101811093  if (deg(h)<=0)
     
    1102411099  dbprint(p,dbprintWhitespace+"Checking if a more improved algorithm\
    1102511100 is available other than the naive ansatz-method.");
    11026   dbprint(p,dbprintWhitespace+"1. Checking if h in commutative
    11027  (sub)-ring");
     11101  dbprint(p,dbprintWhitespace+"1. Checking if h in commutative (sub)-ring");
    1102811102  if (isInCommutativeSubRing(h))
    1102911103  {//h is in a commutative subring
    1103011104    return(factor_commutative(h));
    1103111105  }//h is in a commutative subring
    11032   dbprint(p,dbprintWhitespace+"h was not in a commutative
     11106  dbprint(p,dbprintWhitespace+"h was not in a commutative\
    1103311107 (sub)-ring.");
    11034   dbprint(p,dbprintWhitespace+"2. Checking if h is in Weyl-Algebra
    11035  over QQ");
     11108  dbprint(p,dbprintWhitespace+"2. Checking if h was in a letterplace ring");
     11109  if ( attrib(basering, "isLetterplaceRing") >= 1 )
     11110  {
     11111    dbprint(p,dbprintWhitespace+
     11112            "We are indeed in a letterplace ring. Forwarding the computation " +
     11113            "to ncfactor-without-opt-letterplace");
     11114    return(ncfactor_without_opt_letterplace(h));
     11115  }
     11116  dbprint(p,dbprintWhitespace+"2. Checking if h is in Weyl-Algebra over QQ");
    1103611117  if (ncfactor_isWeyl()&&npars(basering)==0&&char(basering)==0)
    1103711118  {
    11038     dbprint(p,dbprintWhitespace + "We are indeed in a Weyl
    11039  algebra. Forwarding computation to facWeyl");
     11119    dbprint(p,dbprintWhitespace +
     11120            "We are indeed in a Weyl algebra. Forwarding computation to facWeyl");
    1104011121    return(facWeyl(h));
    1104111122  }
    1104211123  dbprint(p,dbprintWhitespace+"Our ring is not a Weyl algebra over QQ.");
    11043   dbprint(p,dbprintWhitespace+"3. Checking if we are in a q-Weyl
    11044  algebra over QQ.");
     11124  dbprint(p,dbprintWhitespace+"3. Checking if we are in a q-Weyl algebra over QQ.");
    1104511125  if (ncfactor_isQWeyl()&&char(basering)==0)
    1104611126  {
    11047     dbprint(p,dbprintWhitespace + "We are indeed in a q-Weyl
     11127    dbprint(p,dbprintWhitespace + "We are indeed in a q-Weyl\
    1104811128 algebra over QQ. Checking if homogeneous.");
    1104911129    if(homogwithorderNthWeyl(h))
    1105011130    {
    11051       dbprint(p,dbprintWhitespace+"h was homogeneous. Forwarding
     11131      dbprint(p,dbprintWhitespace+"h was homogeneous. Forwarding\
    1105211132 computation to homogfacqweyl.");
    1105311133      return(homogfacNthQWeyl_all(h));
     
    1105511135  }
    1105611136  dbprint(p,dbprintWhitespace+"Our ring is not a q-Weyl algebra.");
    11057   dbprint(p,dbprintWhitespace+"4. Checking if h is in a subalgebra
     11137  dbprint(p,dbprintWhitespace+"4. Checking if h is in a subalgebra\
    1105811138 that resembles the Weyl algebra");
    1105911139  if(isInWeylSubAlg(h)&&npars(basering)==0&&char(basering)==0)
    1106011140  {
    11061     dbprint(p,dbprintWhitespace+"We are indeed in a subalgebra that is
     11141    dbprint(p,dbprintWhitespace+"We are indeed in a subalgebra that is\
    1106211142 isomorphic to a Weyl algebra. Forwarding to facSubWeyl.");
    1106311143    return(facSubWeyl(h));
    1106411144  }
    11065   dbprint(p,dbprintWhitespace+"No optimized algorithm available. Going
     11145  dbprint(p,dbprintWhitespace+"No optimized algorithm available. Going \
    1106611146 for the ansatz method without optimization.");
    1106711147  return(ncfactor_without_opt(h));
     
    1107011150{
    1107111151  "EXAMPLE:";echo=2;
     11152  // first, an example with PLURAL
    1107211153  def R = makeUsl2();
    1107311154  setring(R);
    1107411155  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
    1107511156           +e*f+f^2-4*e*h-2*f*h-7*e+f-h;
     11157  ncfactor(p);
     11158  kill R;
     11159  // an example with LETTERPLACE
     11160  LIB "freegb.lib";
     11161  ring r = 0,(x,y),Dp;
     11162  def R = freeAlgebra(r,5); setring(R);
     11163  poly p = x*y*x - x;
    1107611164  ncfactor(p);
    1107711165}
     
    1128611374  {
    1128711375    print("Test 10 for ncfactor failed.");
     11376    print("Expected:\n");
     11377    print(expected);
     11378    print("obtained:\n");
     11379    print(obtained);
     11380    result = 0;
     11381  }
     11382  kill r;
     11383  //Test 11: Generic Letterplace example
     11384  ring r = 0,(x,y,z),dp;
     11385  int d =4; // degree bound
     11386  def R = makeLetterplaceRing(d);
     11387  setring R;
     11388  poly f1 = 6*x*y*x + 9*x;
     11389  list obtained = ncfactor(f1);
     11390  list expected = sortFactorizations(
     11391    list(
     11392      list(number(3), x, 2*y*x + 3),
     11393      list(number(3), 2*x*y + 3, x)
     11394      ));
     11395  if (!isListEqual(expected,obtained))
     11396  {
     11397    print("Test 11 for ncfactor failed.");
    1128811398    print("Expected:\n");
    1128911399    print(expected);
     
    1198412094}//testing factorize_nc_s
    1198512095
     12096
     12097static proc getMaxDegreeVecLetterPlace(poly h)
     12098"USAGE: getMaxDegreeVecLetterPlace(h); h is a polynomial in a
     12099        Letterplace ring.
     12100RETURN: intvec
     12101PURPOSE: Returns for each variable in the ring the maximal
     12102         degree in which it appears in h.
     12103ASSUMING: The basering is
     12104"
     12105{//proc getMaxDegreeVecLetterPlace
     12106  int lv = attrib(basering, "isLetterplaceRing"); // nvars of orig ring
     12107  if (h == 0) { return (0:lv); }
     12108  intvec tempIntVec1 = 0:lv;
     12109  intvec maxDegrees = 0:lv;
     12110  intvec tempIntVec2;
     12111  int i; int j;
     12112  for (i = 1; i<=size(h); i++)
     12113  {//going through each monomial in h and finding the degree in each var
     12114    tempIntVec2 = lp2iv(h[i]);
     12115    if (tempIntVec2 == 0)
     12116    {
     12117      i++; continue;
     12118    }
     12119    tempIntVec1 = 0:lv;
     12120    for (j=1; j<=size(tempIntVec2); j++)
     12121    {//filling in the number of occurrences
     12122      tempIntVec1[tempIntVec2[j]] = tempIntVec1[tempIntVec2[j]] + 1;
     12123    }//filling in the number of occurrences
     12124    for (j = 1; j<=lv; j++)
     12125    {//putting the max into maxDegrees
     12126      maxDegrees[j] = max(maxDegrees[j], tempIntVec1[j]);
     12127    }//putting the max into maxDegrees
     12128  }//going through each monomial in h and finding the degree in each var
     12129  return(maxDegrees);
     12130}//proc getMaxDegreeVecLetterPlace
     12131
     12132static proc test_getMaxDegreeVecLetterPlace()
     12133{//testing getMaxDegreeVecLetterPlace
     12134  int result = 1;
     12135  ring r = 0,(x,y,z),dp;
     12136  int d =4; // degree bound
     12137  def R = makeLetterplaceRing(d);
     12138  setring R;
     12139  //Test 1: 0
     12140  intvec expected = 0:3;
     12141  intvec obtained = getMaxDegreeVecLetterPlace(0);
     12142  if (expected!=obtained)
     12143  {
     12144    print("Test 1 for getMaxDegreeVecLetterPlace failed.");
     12145    print("Expected:\n");
     12146    print(expected);
     12147    print("obtained:\n");
     12148    print(obtained);
     12149    result = 0;
     12150  }
     12151  //Test 2: Constant neq 0
     12152  expected = 0:3;
     12153  obtained = getMaxDegreeVecLetterPlace(3);
     12154  if (expected!=obtained)
     12155  {
     12156    print("Test 2 for getMaxDegreeVecLetterPlace failed.");
     12157    print("Expected:\n");
     12158    print(expected);
     12159    print("obtained:\n");
     12160    print(obtained);
     12161    result = 0;
     12162  }
     12163  //Test 3: univariate, first variable
     12164  expected = 2, 0, 0;
     12165  obtained = getMaxDegreeVecLetterPlace(5*x*x + x + 1);
     12166  if (expected!=obtained)
     12167  {
     12168    print("Test 3 for getMaxDegreeVecLetterPlace failed.");
     12169    print("Expected:\n");
     12170    print(expected);
     12171    print("obtained:\n");
     12172    print(obtained);
     12173    result = 0;
     12174  }
     12175  //Test 4: univariate, another variable
     12176  expected = 0, 0, 3;
     12177  obtained = getMaxDegreeVecLetterPlace(5*z*z*z + z*z + 1);
     12178  if (expected!=obtained)
     12179  {
     12180    print("Test 4 for getMaxDegreeVecLetterPlace failed.");
     12181    print("Expected:\n");
     12182    print(expected);
     12183    print("obtained:\n");
     12184    print(obtained);
     12185    result = 0;
     12186  }
     12187  //Test 5: random polynomial
     12188  expected = 3, 1, 2;
     12189  obtained = getMaxDegreeVecLetterPlace(2*x*y*x*x + 4*y*z*z);
     12190  if (expected!=obtained)
     12191  {
     12192    print("Test 5 for getMaxDegreeVecLetterPlace failed.");
     12193    print("Expected:\n");
     12194    print(expected);
     12195    print("obtained:\n");
     12196    print(obtained);
     12197    result = 0;
     12198  }
     12199  return(result);
     12200}//testing getMaxDegreeVecLetterPlace
     12201
     12202static proc wordsWithMaxAppearance(intvec maxDegInCoordinates, int upToDeg)
     12203"USAGE: wordsWithMaxAppearance(maxDegInCoordinates);
     12204maxDegreeInCoordinates is an intvec.
     12205RETURN: list
     12206PURPOSE: maxDegInCoordinates is a vector representing
     12207the maximum times a variable is allowed to appear in a monomial in
     12208letterplace representation. This function computes all possible words
     12209given this restriction.
     12210ASSUME: maxDegInCoordinates only has non-negative entries
     12211"{//wordsWithMaxAppearance
     12212  int p=printlevel-voice+2;//for dbprint
     12213  int i; int j;
     12214  string dbprintWhitespace = "";
     12215  for (i = 1; i<=voice;i++)
     12216  {dbprintWhitespace = dbprintWhitespace + " ";}
     12217  list result;
     12218  intvec tempMaxDegs;
     12219  list recResult;
     12220  for (i = 1; i<=size(maxDegInCoordinates); i++)
     12221  {//For each coordinate not equal to zero, do a recursive call and concatenate
     12222    if (maxDegInCoordinates[i] <= 0)
     12223    {//Done with coordinate i
     12224      i++; continue;
     12225    }//Done with coordinate i
     12226    tempMaxDegs = maxDegInCoordinates;
     12227    tempMaxDegs[i] = tempMaxDegs[i] - 1;
     12228    recResult = wordsWithMaxAppearance(tempMaxDegs, upToDeg);
     12229    if (size(recResult) == 0 && upToDeg>=1)
     12230    {//Single entry just needs to be there
     12231      result = result + list(intvec(i));
     12232    }//Single entry just needs to be there
     12233    result = result + recResult;
     12234    for (j = 1; j<=size(recResult); j++)
     12235    {//concatenate i to all elements in recResult
     12236      if (size(recResult[j]) + 1 <= upToDeg)
     12237      {//only concatenate if uptodeg is not exceeded
     12238    recResult[j] = intvec(i, recResult[j]);
     12239      }//only concatenate if uptodeg is not exceeded
     12240    }//concatenate i to all elements in recResult
     12241    result = result + recResult;
     12242  }//For each coordinate not equal to zero, do a recursive call and concatenate
     12243  return(delete_duplicates_noteval_and_sort(result));
     12244}//wordsWithMaxAppearance
     12245
     12246static proc test_wordsWithMaxAppearance()
     12247{//test_wordsWithMaxAppearance
     12248  int result = 1;
     12249  //Test 1: 0 intvec
     12250  list expected = list();
     12251  list obtained = wordsWithMaxAppearance(intvec(0), 4);
     12252  if (!isListEqual(expected,obtained))
     12253  {
     12254    print("Test 1 for wordsWithMaxAppearance failed.");
     12255    print("Expected:\n");
     12256    print(expected);
     12257    print("obtained:\n");
     12258    print(obtained);
     12259    result = 0;
     12260  }
     12261  //Test 2: 0 multiple entries intvec
     12262  expected = list();
     12263  obtained = wordsWithMaxAppearance(0:10, 4);
     12264  if (!isListEqual(expected,obtained))
     12265  {
     12266    print("Test 2 for wordsWithMaxAppearance failed.");
     12267    print("Expected:\n");
     12268    print(expected);
     12269    print("obtained:\n");
     12270    print(obtained);
     12271    result = 0;
     12272  }
     12273  //Test 3: Single letter
     12274  expected = list(intvec(4));
     12275  obtained = wordsWithMaxAppearance(intvec(0, 0, 0, 1, 0, 0), 4);
     12276  if (!isListEqual(expected,obtained))
     12277  {
     12278    print("Test 3 for wordsWithMaxAppearance failed.");
     12279    print("Expected:\n");
     12280    print(expected);
     12281    print("obtained:\n");
     12282    print(obtained);
     12283    result = 0;
     12284  }
     12285  //Test 4: Two letters, one appearance
     12286  expected = list(intvec(3), intvec(3,4), intvec(4), intvec(4,3));
     12287  obtained = wordsWithMaxAppearance(intvec(0, 0, 1, 1, 0, 0), 4);
     12288  if (!isListEqual(expected,obtained))
     12289  {
     12290    print("Test 4 for wordsWithMaxAppearance failed.");
     12291    print("Expected:\n");
     12292    print(expected);
     12293    print("obtained:\n");
     12294    print(obtained);
     12295    result = 0;
     12296  }
     12297  //Test 5: One letter, degree 2
     12298  expected = list(intvec(4), intvec(4,4));
     12299  obtained = wordsWithMaxAppearance(intvec(0, 0, 0, 2, 0, 0), 4);
     12300  if (!isListEqual(expected,obtained))
     12301  {
     12302    print("Test 5 for wordsWithMaxAppearance failed.");
     12303    print("Expected:\n");
     12304    print(expected);
     12305    print("obtained:\n");
     12306    print(obtained);
     12307    result = 0;
     12308  }
     12309  //Test 6: random example
     12310  expected = list(intvec(1),
     12311          intvec(1,4),
     12312          intvec(1,4,4),
     12313          intvec(4),
     12314          intvec(4,1),
     12315          intvec(4,1,4),
     12316          intvec(4,4),
     12317          intvec(4,4,1));
     12318  obtained = wordsWithMaxAppearance(intvec(1, 0, 0, 2, 0, 0), 4);
     12319  if (!isListEqual(expected,obtained))
     12320  {
     12321    print("Test 6 for wordsWithMaxAppearance failed.");
     12322    print("Expected:\n");
     12323    print(expected);
     12324    print("obtained:\n");
     12325    print(obtained);
     12326    result = 0;
     12327  }
     12328  return(result);
     12329}//test_wordsWithMaxAppearance
     12330
     12331static proc monsSmallerThanLetterPlace(poly e, intvec maxDegInCoordinates, int upToDeg)
     12332"USAGE: monsSmallerThanLetterPlace(e, maxDegInCoordinates); e is a
     12333monomial.
     12334maxDegreeInCoordinates encodes the maximal degree we wish to encounter
     12335in each variable.
     12336RETURN: list
     12337PURPOSE: Computes all monomials in the basering which are degree-wise
     12338smaller than the leading monomial of e.
     12339"{//monsSmallerThanLetterPlace
     12340  int p=printlevel-voice+2;//for dbprint
     12341  int i;
     12342  string dbprintWhitespace = "";
     12343  for (i = 1; i<=voice;i++)
     12344  {dbprintWhitespace = dbprintWhitespace + " ";}
     12345  list result;
     12346  int maxLen = min(sum(maxDegInCoordinates), lpDegBound(basering));
     12347  dbprint(p,dbprintWhitespace + "maxLength: " + string(maxLen));
     12348  list allPossibilities = wordsWithMaxAppearance(maxDegInCoordinates, upToDeg);
     12349  dbprint(p,dbprintWhitespace + "words with max appearance: " + string(allPossibilities));
     12350  poly candidate;
     12351  intvec candidateMaxDeg;
     12352  for (i = 1; i<=size(allPossibilities); i++)
     12353  {//checking for monomials with smaller degree than e
     12354    candidate = iv2lp(allPossibilities[i]);
     12355    dbprint(p,dbprintWhitespace + "Checking candidate: " + string(candidate));
     12356    candidateMaxDeg = getMaxDegreeVecLetterPlace(candidate);
     12357    if (candidate < e && candidateMaxDeg <= maxDegInCoordinates)
     12358    {//successfully found a candidate
     12359      result = insert(result, candidate);
     12360    }//successfully found a candidate
     12361  }//checking for monomials with smaller degree than e
     12362  return(result);
     12363}//monsSmallerThanLetterPlace
     12364
     12365static proc test_monsSmallerThanLetterPlace()
     12366{//test_monsSmallerThanLetterPlace
     12367  int result = 1;
     12368  ring r = 0,(x,y,z,d,w),dp;
     12369  int upToDegBound = 10; // degree bound
     12370  def R = makeLetterplaceRing(upToDegBound);
     12371  setring R;
     12372  //Test 1: 0, 0
     12373  poly input1 = 0;
     12374  intvec input2 = intvec(0,0,0,0,0);
     12375  list expected = list();
     12376  list obtained = monsSmallerThanLetterPlace(input1, input2, upToDegBound);
     12377  if (!isListEqual(expected,obtained))
     12378  {
     12379    print("Test 1 for monsSmallerThanLetterPlace failed.");
     12380    print("Expected:\n");
     12381    print(expected);
     12382    print("obtained:\n");
     12383    print(obtained);
     12384    result = 0;
     12385  }
     12386  //Test 2: 0, nontrivial maxdegree
     12387  input1 = 0;
     12388  input2 = intvec(0,0,2,1,0);
     12389  expected = list();
     12390  obtained = monsSmallerThanLetterPlace(input1, input2, upToDegBound );
     12391  if (!isListEqual(expected,obtained))
     12392  {
     12393    print("Test 2 for monsSmallerThanLetterPlace failed.");
     12394    print("Expected:\n");
     12395    print(expected);
     12396    print("obtained:\n");
     12397    print(obtained);
     12398    result = 0;
     12399  }
     12400  //Test 3: constant, nontrivial maxdegree
     12401  input1 = 7;
     12402  input2 = intvec(0,0,2,1,0);
     12403  expected = list();
     12404  obtained = monsSmallerThanLetterPlace(input1, input2, upToDegBound);
     12405  if (!isListEqual(expected,obtained))
     12406  {
     12407    print("Test 3 for monsSmallerThanLetterPlace failed.");
     12408    print("Expected:\n");
     12409    print(expected);
     12410    print("obtained:\n");
     12411    print(obtained);
     12412    result = 0;
     12413  }
     12414  //Test 4: single variable smallest, nontrivial maxdegree
     12415  input1 = w;
     12416  input2 = intvec(0,0,2,1,0);
     12417  expected = list();
     12418  obtained = monsSmallerThanLetterPlace(input1, input2, upToDegBound );
     12419  if (!isListEqual(expected,obtained))
     12420  {
     12421    print("Test 4 for monsSmallerThanLetterPlace failed.");
     12422    print("Expected:\n");
     12423    print(expected);
     12424    print("obtained:\n");
     12425    print(obtained);
     12426    result = 0;
     12427  }
     12428  //Test 5: single variable highest, nontrivial maxdegree
     12429  input1 = x;
     12430  input2 = intvec(0,0,2,1,0);
     12431  expected = list(d, z);
     12432  obtained = monsSmallerThanLetterPlace(input1, input2, upToDegBound);
     12433  if (!isListEqual(expected,obtained))
     12434  {
     12435    print("Test 5 for monsSmallerThanLetterPlace failed.");
     12436    print("Expected:\n");
     12437    print(expected);
     12438    print("obtained:\n");
     12439    print(obtained);
     12440    result = 0;
     12441  }
     12442  //Test 6: single variable highest, nontrivial maxdegree
     12443  input1 = x;
     12444  input2 = intvec(0,0,2,1,0);
     12445  expected = list(d, z);
     12446  obtained = monsSmallerThanLetterPlace(input1, input2, upToDegBound );
     12447  if (!isListEqual(expected,obtained))
     12448  {
     12449    print("Test 6 for monsSmallerThanLetterPlace failed.");
     12450    print("Expected:\n");
     12451    print(expected);
     12452    print("obtained:\n");
     12453    print(obtained);
     12454    result = 0;
     12455  }
     12456  //Test 7: nontrivial monomial, nontrivial maxdegree
     12457  input1 = z*z*d*d;
     12458  input2 = intvec(0,0,2,1,0);
     12459  expected = list(d*z*z,
     12460          d*z,
     12461          d,
     12462          z*d*z,
     12463          z*d,
     12464          z*z*d,
     12465          z*z,
     12466          z);
     12467  obtained = monsSmallerThanLetterPlace(input1, input2, upToDegBound);
     12468  if (!isListEqual(expected,obtained))
     12469  {
     12470    print("Test 7 for monsSmallerThanLetterPlace failed.");
     12471    print("Expected:\n");
     12472    print(expected);
     12473    print("obtained:\n");
     12474    print(obtained);
     12475    result = 0;
     12476  }
     12477  return(result);
     12478}//test_monsSmallerThanLetterPlace
     12479
     12480static proc ncfactor_letterplace_poly_s(poly h)
     12481"USAGE: ncfactor_letterplace_poly_s(h); h is a polynomial in a
     12482        letterplace algebra
     12483RETURN: list(list)
     12484PURPOSE: Compute all factorizations of h
     12485THEORY: Implements an ansatz-driven factorization method as outlined
     12486by Bell, Heinle and Levandovskyy in \"On Noncommutative Finite
     12487Factorization Domains\".
     12488ASSUME:
     12489- basering is a Letterplace ring
     12490- basefield is such, that factorize() can factor any univariate and
     12491  multivariate commutative polynomial over it.
     12492- h is not a constant or 0.
     12493NOTE:
     12494- Every entry of the output list is a list with factors for one possible factorization.
     12495  The first factor is always a constant (1, if no nontrivial constant
     12496  could be excluded).
     12497SEE ALSO: ncfactor
     12498"{//proc ncfactor_letterplace_poly_s
     12499  int p=printlevel-voice+2;//for dbprint
     12500  int i; int j; int k; int l;
     12501  string dbprintWhitespace = "";
     12502  for (i = 1; i<=voice;i++)
     12503  {dbprintWhitespace = dbprintWhitespace + " ";}
     12504  list result;
     12505  // Producing the set M of the paper (permutation of the variables in
     12506  // the leading monomial)
     12507  dbprint(p,dbprintWhitespace + "Generating the set M.");
     12508  def r = basering;
     12509  intvec maxDegrees = getMaxDegreeVecLetterPlace(h);
     12510  dbprint(p,dbprintWhitespace + "The maximum degrees for each var are given by: "+
     12511      string(maxDegrees));
     12512  intvec expVec = lp2iv(leadmonom(h));
     12513  dbprint(p, dbprintWhitespace + "The leading monomial of h is: " + string(expVec));
     12514  list M;
     12515  for (i = 1; i<size(expVec); i++)
     12516  {//The set M consists of all posssible two-word-combinations of the leading monomial
     12517    M = M + list(list(intvec(expVec[1..i]), intvec(expVec[i+1..size(expVec)])));
     12518  }
     12519  dbprint(p,dbprintWhitespace+"The set M is:");
     12520  dbprint(p, M);
     12521  list list_UpToA;
     12522  list list_UpToB;
     12523  list tempSringlist = ringlist(r);
     12524  list clearSlateRingList = ringlist(r);
     12525  clearSlateRingList[2] = list();
     12526  clearSlateRingList[3] = list();
     12527  if (size(clearSlateRingList) == 6)
     12528  {//some non-commutative relations defined
     12529    clearSlateRingList = delete(clearSlateRingList, 6);
     12530    clearSlateRingList = delete(clearSlateRingList, 5);
     12531  }
     12532  else
     12533  {//It is still possible that we have a 5th entry
     12534    if (size(clearSlateRingList) == 5)
     12535    {
     12536      clearSlateRingList = delete(clearSlateRingList, 5);
     12537    }
     12538  }
     12539  intvec tempIntVec;
     12540  def S; def W; def W2;
     12541  list MEntry;
     12542  poly tempA;
     12543  poly tempB;
     12544  int filterFlag;
     12545  int jj = 1; int sizeOfSol = 1;
     12546  for (i = 1; i<=size(M); i++)
     12547  {//Iterating over all two-combinations in the set M
     12548    MEntry = M[i];
     12549    tempA = iv2lp(MEntry[1]);
     12550    tempB = iv2lp(MEntry[2]);
     12551    dbprint(p,dbprintWhitespace + "The potential leading combination of a is " + string(tempA));
     12552    dbprint(p,dbprintWhitespace + "The potential leading combination of b is " + string(tempB));
     12553    dbprint(p,dbprintWhitespace + "Calculating the monomials smaller than A");
     12554    list_UpToA = monsSmallerThanLetterPlace(leadmonom(tempA),
     12555                        maxDegrees - getMaxDegreeVecLetterPlace(tempB),
     12556                        lpDegBound(r));
     12557    dbprint(p,dbprintWhitespace + "Done, they are: " + string(list_UpToA));
     12558    dbprint(p,dbprintWhitespace + "Calculating the monomials smaller than B");
     12559    list_UpToB = monsSmallerThanLetterPlace(leadmonom(tempB),
     12560                        maxDegrees - getMaxDegreeVecLetterPlace(tempA),
     12561                        lpDegBound(r));
     12562    dbprint(p,dbprintWhitespace + "Done, they are: " + string(list_UpToB));
     12563    //we need to filter out lm(tempA) and lm(tempB);
     12564    for (k = size(list_UpToA); k>0; k--)
     12565    {//removing the leading monomial from list_UpToA and invalid parts
     12566      if (list_UpToA[k] == leadmonom(tempA))
     12567      {//found it
     12568    list_UpToA = delete(list_UpToA,k);
     12569    continue;
     12570      }//found it
     12571      if(sum(getMaxDegreeVecLetterPlace(h)) < sum(getMaxDegreeVecLetterPlace(list_UpToA[k])))
     12572      {//total degree exceeds
     12573    list_UpToA = delete(list_UpToA,k);
     12574    continue;
     12575      }//total degree exceeds
     12576    }//removing the leading monomial from list_UpToA and invalid parts
     12577    for (k = size(list_UpToB); k>0; k--)
     12578    {//removing the leading monomial from list_UpToA
     12579      if (list_UpToB[k] == leadmonom(tempB))
     12580      {//found it
     12581    list_UpToB = delete(list_UpToB,k);
     12582    continue;
     12583      }//found it
     12584      if(sum(getMaxDegreeVecLetterPlace(h)) < sum(getMaxDegreeVecLetterPlace(list_UpToB[k])))
     12585      {//total degree exceeds
     12586    list_UpToB = delete(list_UpToB,k);
     12587    continue;
     12588      }//total degree exceeds
     12589    }//removing the leading monomial from list_UpToA
     12590    if (typeof(tempSringlist[1]) == "int")
     12591    {//No extra parameters in the original ring
     12592      tempSringlist[1] = list(tempSringlist[1],list(), list(list()));
     12593    }//No extra parameters in the original ring
     12594    for (k = size(list_UpToB)+1; k>=0; k--)
     12595    {//fill in b-coefficients as variables
     12596      tempSringlist[1][2] = insert(tempSringlist[1][2],"@b("+string(k)+")");
     12597      clearSlateRingList[2] = insert(clearSlateRingList[2],"@b("+string(k)+")");
     12598    }//fill in b-coefficients as variables
     12599    for (k = size(list_UpToA); k>=0; k--)
     12600    {//fill in a-coefficients as variables
     12601      tempSringlist[1][2] = insert(tempSringlist[1][2],"@a("+string(k)+")");
     12602      clearSlateRingList[2] = insert(clearSlateRingList[2], "@a("+string(k)+")");
     12603    }//fill in a-coefficients as variables
     12604    tempIntVec = 0;
     12605    for(k=1; k<=size(list_UpToA) + size(list_UpToB)+3; k++)
     12606    {tempIntVec[k] = 1;}
     12607    clearSlateRingList[3] =
     12608      list(list("lp",tempIntVec),list("C",intvec(0)));
     12609    if (size(tempSringlist[1][3][1]) == 0)
     12610    {//No values in there before
     12611      tempSringlist[1][3][1] =
     12612    list("lp", tempIntVec);
     12613      tempSringlist[1][4] = ideal(0);
     12614    }//No values in there before
     12615    else
     12616    {//there were other parameters
     12617      tempSringlist[1][3][1][2] = tempSringlist[1][3][1][2], tempIntVec;
     12618    }//there were other parameters
     12619    attrib(tempSringlist, "isLetterplaceRing", attrib(r,"isLetterplaceRing"));
     12620    attrib(tempSringlist, "maxExp", 1);
     12621    if (defined(S)) {
     12622      kill S;
     12623    }
     12624    def S = ring(tempSringlist); setring S;
     12625    attrib(S, "uptodeg", lpDegBound(r));
     12626    attrib(S, "isLetterplaceRing", attrib(r,"isLetterplaceRing"));
     12627    dbprint(p,dbprintWhitespace+"Done generating ring S:");
     12628    dbprint(p,dbprintWhitespace+string(S));
     12629    dbprint(p,dbprintWhitespace+"Generate the ansatz.");
     12630    dbprint(p,dbprintWhitespace+"The new ring is: " + string(basering));
     12631    setring(S);
     12632    poly h = imap(r, h);
     12633    poly a = imap(r,tempA);
     12634    poly b = imap(r,tempB);
     12635    if (!defined(list_UpToA))
     12636    {list list_UpToA = imap(r,list_UpToA);}
     12637    if (!defined(list_UpToB))
     12638    {list list_UpToB = imap(r,list_UpToB);}
     12639    b = b*par(size(list_UpToA)+size(list_UpToB)+3);
     12640    for (k = size(list_UpToB); k>0; k--)
     12641    {b = b + par(size(list_UpToA)+2+k)*list_UpToB[k];}
     12642    b = b + par(size(list_UpToA) + 2);
     12643    dbprint(p,dbprintWhitespace + "The ansatz for b is " + string(b));
     12644    for (k = size(list_UpToA); k>0; k--)
     12645    {a = a + par(k+1)*list_UpToA[k];}
     12646    a = a + par(1);
     12647    dbprint(p,dbprintWhitespace + "The ansatz for a is " + string(a));
     12648    poly ansatzPoly = a*b - h;
     12649    dbprint(p,dbprintWhitespace + "The ansatzpoly is " + string(ansatzPoly));
     12650    ideal listOfRelations = coeffs(ansatzPoly, var(1));
     12651    for (k = 2;k<=nvars(r);k++)
     12652    {listOfRelations = coeffs(listOfRelations,var(k));}
     12653    setring(r);
     12654    W = ring(clearSlateRingList); // comm ring of coeffs of the ansatz
     12655    W2 = W+r; // first coeffs, then orig letterplace vars
     12656    setring(W);
     12657    ideal listOfRelations = imap(S, listOfRelations);
     12658    option(redSB);
     12659    option(redTail);
     12660    dbprint(p,dbprintWhitespace + "Calculating the solutions of:");
     12661    dbprint(p,listOfRelations);
     12662    if (!defined(sol))
     12663    {
     12664      def sol = facstd(listOfRelations);
     12665    }
     12666    else
     12667    {
     12668      sol = facstd(listOfRelations);
     12669    }
     12670    dbprint(p,dbprintWhitespace + "Filtering the solutions that are " +
     12671      "not in the base-field.");
     12672    for(k = 1; k <=size(sol);k++)
     12673    {//filtering what is not in the ground-field
     12674      filterFlag = 0;
     12675      for (l=1; l<=size(sol[k]); l++)
     12676      {
     12677        if ((deg(sol[k][l])>1) or ((sol[k][l]/leadcoef(sol[k][l])==1)))
     12678        {//Not in the ground field
     12679          filterFlag = 1;
     12680          break;
     12681        }//Not in the ground field
     12682      }
     12683      if (filterFlag or (vdim(std(sol[k]))<0))
     12684      {//In this case, we can delete that whole entry and move on
     12685        sol= delete(sol,k);
     12686        continue;
     12687      }//In this case, we can delete that whole entry and move on
     12688    }//filtering what is not in the ground-field
     12689    dbprint(p,dbprintWhitespace + "Solutions for the coefficients are:");
     12690    dbprint(p,sol);
     12691    setring S;
     12692    ideal a_coef; jj=1;
     12693    while (a[jj]!=0)
     12694    {
     12695      a_coef[jj]=leadcoef(a[jj]);
     12696      jj++;
     12697    }
     12698    ideal b_coef;
     12699    jj=1;
     12700    while (b[jj]!=0)
     12701    {
     12702      b_coef[jj]=leadcoef(b[jj]);
     12703      jj++;
     12704    }
     12705    setring W; //W = ring of coeffs_variables
     12706    ideal a_coef = imap(S, a_coef);
     12707    ideal b_coef = imap(S, b_coef);
     12708    sizeOfSol = size(sol);
     12709    if (!defined(tempResultCoeffs)) {
     12710      list tempResultCoeffs;
     12711    }
     12712    tempResultCoeffs = list();
     12713    for (k=1; k<=sizeOfSol; k++)
     12714    {
     12715      sol[k] = std(sol[k]);
     12716      tempResultCoeffs = insert(tempResultCoeffs, list(
     12717      NF(a_coef, sol[k]), // element-wise
     12718      NF(b_coef, sol[k]))); // element-wise
     12719    }
     12720    setring S;
     12721    if(!defined(tempResultCoeffs)) {
     12722      list tempResultCoeffs = imap(W, tempResultCoeffs);
     12723    }
     12724    if (!(defined(tempResult)))
     12725    {list tempResult;}
     12726    poly ared;
     12727    poly bred;
     12728    for (k = 1; k <= size(tempResultCoeffs); k++)
     12729    {//Creating the resulting polynomials with the respective coeffs.
     12730      jj=1;
     12731      ared=0;
     12732      bred=0;
     12733      while (a[jj]!=0)
     12734      {//Going through all monomials of a
     12735        ared= ared+leadcoef(tempResultCoeffs[k][1][jj])*leadmonom(a[jj]);
     12736        jj++;
     12737      }//Going through all monomials of a
     12738      jj=1;
     12739      while (b[jj]!=0)
     12740      {//Going through all monomials of b
     12741        bred= bred+leadcoef(tempResultCoeffs[k][2][jj])*leadmonom(b[jj]);
     12742        jj++;
     12743      }//Going through all monomials of b
     12744      tempResult = insert(tempResult,list(ared,bred));
     12745    }//Creating the resulting polynomials with the respective coeffs.
     12746    setring(r);
     12747    if (!defined(tempResult))
     12748    {def tempResult = imap(S,tempResult);}
     12749    for (k=1; k<= size(tempResult);k++)
     12750    {
     12751      result = insert(result,tempResult[k]);
     12752    }
     12753    kill tempResult;
     12754    clearSlateRingList[2] = list();
     12755    clearSlateRingList[3] = list();
     12756    tempSringlist = ringlist(r);
     12757  }//Iterating over all two-combinations in the set M
     12758  if(size(result)==0)
     12759  {
     12760    return (list(list(h)));
     12761  }
     12762  return(delete_duplicates_noteval_and_sort(result));
     12763}//proc ncfactor_letterplace_poly_s
     12764
     12765
     12766static proc test_ncfactor_letterplace_poly_s()
     12767"Tests the basic functionality."
     12768{//proc test_ncfactor_letterplace_poly_s()
     12769  int result = 1;
     12770  ring r = 0,(x,y,z),dp;
     12771  int d =4; // degree bound
     12772  def R = makeLetterplaceRing(d);
     12773  setring R;
     12774  //TEST 1: power of 2
     12775  poly f1 = (x + y)*(x + y);
     12776  list obtained = ncfactor_letterplace_poly_s(f1);
     12777  list expected = sortFactorizations(
     12778    list(
     12779      list(x + y, x + y)
     12780      ));
     12781  if (!isListEqual(expected,obtained))
     12782  {
     12783    print("Test 1 for ncfactor_letterplace_poly_s failed.");
     12784    print("Expected:\n");
     12785    print(expected);
     12786    print("obtained:\n");
     12787    print(obtained);
     12788    result = 0;
     12789  }
     12790  //TEST 2: Monomial
     12791  f1 = x*z;
     12792  obtained = ncfactor_letterplace_poly_s(f1);
     12793  expected = sortFactorizations(
     12794    list(
     12795      list(x, z)
     12796      ));
     12797  if (!isListEqual(expected,obtained))
     12798  {
     12799    print("Test 2 for ncfactor_letterplace_poly_s failed.");
     12800    print("Expected:\n");
     12801    print(expected);
     12802    print("obtained:\n");
     12803    print(obtained);
     12804    result = 0;
     12805  }
     12806  //TEST 3: Generic product with all variables
     12807  f1 = (x*y + z*x)*(x+ z+ y);
     12808  obtained = ncfactor_letterplace_poly_s(f1);
     12809  expected = sortFactorizations(
     12810    list(
     12811      list(
     12812      x*y + z*x,
     12813      x+ z+ y))
     12814      );
     12815  if (!isListEqual(expected,obtained))
     12816  {
     12817    print("Test 3 for ncfactor_letterplace_poly_s failed.");
     12818    print("Expected:\n");
     12819    print(expected);
     12820    print("obtained:\n");
     12821    print(obtained);
     12822    result = 0;
     12823  }
     12824  //TEST 4: More than one factorization
     12825  f1 = x*y*x + x;
     12826  obtained = ncfactor_letterplace_poly_s(f1);
     12827  expected = sortFactorizations(
     12828    list(
     12829      list(x, y*x + 1),
     12830      list(x*y + 1, x))
     12831      );
     12832  if (!isListEqual(expected,obtained))
     12833  {
     12834    print("Test 4 for ncfactor_letterplace_poly_s failed.");
     12835    print("Expected:\n");
     12836    print(expected);
     12837    print("obtained:\n");
     12838    print(obtained);
     12839    result = 0;
     12840  }
     12841  return (result);
     12842}//proc test_ncfactor_letterplace_poly_s()
     12843
     12844static proc ncfactor_without_opt_letterplace(poly h)
     12845"USAGE: ncfactor_without_opt_letterplace(h); h is a polynomial in a
     12846        letterplace ring over a field k.
     12847RETURN: list(list)
     12848PURPOSE: Compute all factorizations of h, without making any
     12849         sanity-checks
     12850THEORY: Implements an ansatz-driven factorization method as outlined
     12851by Bell, Heinle and Levandovskyy in \"On Noncommutative Finite
     12852Factorization Domains\".
     12853ASSUME:
     12854- the basering is a Letterplace ring.
     12855- k is a ring, such that factorize can factor any univariate and
     12856  multivariate commutative polynomial over k.
     12857- There exists at least one variable in the ring.
     12858- h is not a constant or 0.
     12859NOTE:
     12860- Every entry of the output list is a list with factors for one possible factorization.
     12861  The first factor is always a constant (1, if no nontrivial constant
     12862  could be excluded).
     12863SEE ALSO: facWeyl, facSubWeyl, testNCfac, ncfactor
     12864"{//ncfactor_without_opt_letterplace
     12865  int p = printlevel-voice+2;
     12866  int i; int j; int k; int l;
     12867  string dbprintWhitespace = "";
     12868  for (i = 1; i<=voice;i++)
     12869  {dbprintWhitespace = dbprintWhitespace + " ";}
     12870  number commonCoefficient = content(h);
     12871  poly hath = h/commonCoefficient;
     12872  dbprint(p,dbprintWhitespace + "Calculating all possibilities of h as
     12873 a combination of two factors.");
     12874  list result = ncfactor_letterplace_poly_s(hath);
     12875  result = delete_duplicates_noteval_and_sort(result);
     12876  dbprint(p,dbprintWhitespace + "Done. The result is:");
     12877  dbprint(p,result);
     12878  dbprint(p,dbprintWhitespace+"Recursively check factors for
     12879 irreducibility");
     12880  list recursivetemp;
     12881  int changedSomething;
     12882  for(i = 1; i<=size(result);i++)
     12883  {//recursively factorize factors
     12884    if(size(result[i])>1)
     12885    {//Nontrivial factorization
     12886      for (j=1;j<=size(result[i]);j++)
     12887      {//Factorize every factor
     12888        recursivetemp = ncfactor_letterplace_poly_s(result[i][j]);
     12889        recursivetemp = delete_duplicates_noteval(recursivetemp);
     12890        changedSomething = 0;
     12891        for(k=1; k<=size(recursivetemp);k++)
     12892        {//insert factorized factors
     12893          if(size(recursivetemp[k])>1)
     12894          {//nontrivial
     12895            changedSomething = 1;
     12896            result = insert(result,result[i],i);
     12897            for(l = size(recursivetemp[k]);l>=1;l--)
     12898            {
     12899              result[i+1] = insert(result[i+1],recursivetemp[k][l],j);
     12900            }
     12901            result[i+1] = delete(result[i+1],j);
     12902          }//nontrivial
     12903        }//insert factorized factors
     12904        if (changedSomething)
     12905        {break;}
     12906      }//Factorize every factor
     12907      if(changedSomething)
     12908      {
     12909        result = delete(result,i);
     12910        continue;
     12911      }
     12912    }//Nontrivial factorization
     12913  }//recursively factorize factors
     12914  dbprint(p,dbprintWhitespace +" Done");
     12915  dbprint(p,dbprintWhitespace + "Removing duplicates from the list");
     12916  result = delete_duplicates_noteval_and_sort(result);
     12917  for (i = 1; i<=size(result);i++)
     12918  {//Putting the content everywhere
     12919    result[i] = insert(result[i],commonCoefficient);
     12920  }//Putting the content everywhere
     12921  result = normalizeFactors(result);
     12922  result = delete_duplicates_noteval_and_sort(result);
     12923  dbprint(p,dbprintWhitespace +" Done");
     12924  return(result);
     12925}//ncfactor_without_opt_letterplace
     12926
     12927static proc test_ncfactor_without_opt_letterplace()
     12928"Tests the basic functionality."
     12929{//test_ncfactor_without_opt_letterplace
     12930  int result = 1;
     12931  ring r = 0,(x,y,z),dp;
     12932  int d =4; // degree bound
     12933  def R = makeLetterplaceRing(d);
     12934  setring R;
     12935  //TEST 1: power of 2
     12936  poly f1 = 4*(x + y)*(x + y);
     12937  list obtained = ncfactor_without_opt_letterplace(f1);
     12938  list expected = sortFactorizations(
     12939    list(
     12940      list(number(4), x + y, x + y)
     12941      ));
     12942  if (!isListEqual(expected,obtained))
     12943  {
     12944    print("Test 1 for ncfactor_without_opt_letterplace failed.");
     12945    print("Expected:\n");
     12946    print(expected);
     12947    print("obtained:\n");
     12948    print(obtained);
     12949    result = 0;
     12950  }
     12951  //TEST 2: Monomial
     12952  f1 = 11*x*z;
     12953  obtained = ncfactor_without_opt_letterplace(f1);
     12954  expected = sortFactorizations(
     12955    list(
     12956      list(number(11), x, z)
     12957      ));
     12958  if (!isListEqual(expected,obtained))
     12959  {
     12960    print("Test 2 for ncfactor_without_opt_letterplace failed.");
     12961    print("Expected:\n");
     12962    print(expected);
     12963    print("obtained:\n");
     12964    print(obtained);
     12965    result = 0;
     12966  }
     12967  //TEST 3: Generic product with all variables
     12968  f1 = (2*x*y + 4*z*x)*(x+z+y);
     12969  obtained = ncfactor_without_opt_letterplace(f1);
     12970  expected = sortFactorizations(
     12971    list(
     12972      list(number(2), x*y + 2*z*x, x+z+y)
     12973      ));
     12974  if (!isListEqual(expected,obtained))
     12975  {
     12976    print("Test 3 for ncfactor_without_opt_letterplace failed.");
     12977    print("Expected:\n");
     12978    print(expected);
     12979    print("obtained:\n");
     12980    print(obtained);
     12981    result = 0;
     12982  }
     12983  //TEST 4: More than one factorization
     12984  f1 = 6*x*y*x + 9*x;
     12985  obtained = ncfactor_without_opt_letterplace(f1);
     12986  expected = sortFactorizations(
     12987    list(
     12988      list(number(3), x, 2*y*x + 3),
     12989      list(number(3), 2*x*y + 3, x)
     12990      ));
     12991  if (!isListEqual(expected,obtained))
     12992  {
     12993    print("Test 4 for ncfactor_without_opt_letterplace failed.");
     12994    print("Expected:\n");
     12995    print(expected);
     12996    print("obtained:\n");
     12997    print(obtained);
     12998    result = 0;
     12999  }
     13000  //Test 5: At least one recursive call
     13001  f1 = f1*(x + y);
     13002  obtained = ncfactor_without_opt_letterplace(f1);
     13003  expected = sortFactorizations(
     13004    list(
     13005      list(number(3), x, 2*y*x + 3, x + y),
     13006      list(number(3), 2*x*y + 3, x, x + y)
     13007      ));
     13008  if (!isListEqual(expected,obtained))
     13009  {
     13010    print("Test 5 for ncfactor_without_opt_letterplace failed.");
     13011    print("Expected:\n");
     13012    print(expected);
     13013    print("obtained:\n");
     13014    print(obtained);
     13015    result = 0;
     13016  }
     13017  return (result);
     13018}//test_ncfactor_without_opt_letterplace
     13019
     13020
    1198613021//==================================================
    1198713022// EASY EXAMPLES FOR WEYL ALGEBRA
     
    1221713252
    1221813253 /* recent bufgixes (2) Jan 2018; exs from Viktor and Johannes Hoffmann
    12219  // Original bug: found only (x+d)^2*x as faktorization
     13254 // Original bug: found only (x+d)^2*x as factorization
    1222013255LIB "nctools.lib";
    1222113256ring r = 0,(x,d),dp;
     
    1222513260
    1222613261//======================================================================
    12227 // Hard examples not yet calculatable in feasible amount of time
     13262// Hard examples not yet computable in feasible amount of time
    1222813263//======================================================================
    1222913264
  • Singular/LIB/nctools.lib

    re5c565 r454d97a  
    17641764RETURN:  ring
    17651765PURPOSE: create a copy of a given ring equipped with the
    1766 @* elimination ordering for module components @code{(c,<)}
     1766  elimination ordering for module components @code{(c,<)}
    17671767NOTE: usually the list argument contains a ring to work with
    17681768EXAMPLE: example makeModElimRing; shows an example
  • Singular/checklibs.c

    re5c565 r454d97a  
    77#define LINE_LEN 200
    88#define RECOMMENDED_LEN 100
    9 VAR FILE *f;
    10 VAR int trailing_spaces=0;
    11 VAR int tabs=0;
    12 VAR int verylong_lines=0;
    13 VAR int lines=0;
    14 VAR unsigned char buf[LINE_LEN];
    15 VAR int proc_cnt=0;
    16 VAR unsigned char *proc[NUM_PROC];
    17 VAR unsigned char have_doc[NUM_PROC];
    18 VAR unsigned char have_example[NUM_PROC];
    19 VAR unsigned char proc_found[NUM_PROC];
    20 VAR int non_ascii=0;
    21 VAR int non_ascii_line=0;
    22 VAR int star_nl=0;
    23 VAR int footer=0;
    24 VAR int header=0;
    25 VAR int crlf=0;
    26 VAR int proc_help_lines=0;
    27 VAR int proc_help_texinfo=0;
     9FILE *f;
     10int trailing_spaces=0;
     11int tabs=0;
     12int verylong_lines=0;
     13int lines=0;
     14unsigned char buf[LINE_LEN];
     15int proc_cnt=0;
     16unsigned char *proc[NUM_PROC];
     17unsigned char have_doc[NUM_PROC];
     18unsigned char have_example[NUM_PROC];
     19unsigned char proc_found[NUM_PROC];
     20int non_ascii=0;
     21int non_ascii_line=0;
     22int star_nl=0;
     23int footer=0;
     24int header=0;
     25int crlf=0;
     26int proc_help_lines=0;
     27int proc_help_texinfo=0;
    2828
    2929void get_next()
  • Singular/dyn_modules/freealgebra/freealgebra.cc

    re5c565 r454d97a  
    128128//------------------------------------------------------------------------
    129129// initialisation of the module
    130 extern "C" int SI_MOD_INIT(freegb)(SModulFunctions* p)
     130extern "C" int SI_MOD_INIT(freealgebra)(SModulFunctions* p)
    131131{
    132132#ifdef HAVE_SHIFTBBA
  • Singular/iparith.cc

    re5c565 r454d97a  
    4444#include "kernel/GBEngine/syz.h"
    4545#include "kernel/GBEngine/kstd1.h"
    46 #include "kernel/GBEngine/kutil.h"
    4746#include "kernel/GBEngine/units.h"
    4847#include "kernel/GBEngine/tgb.h"
  • Singular/table.h

    re5c565 r454d97a  
    11741174  { "return",      0, RETURN ,            RETURN},
    11751175  { "RETURN",      0, END_GRAMMAR ,       RETURN},
    1176 #ifdef HAVE_PLURAL
     1176#ifdef HAVE_SHIFTBBA
    11771177  { "rightstd",    0, RIGHTSTD_CMD ,      CMD_1},
    11781178#endif /* HAVE_PLURAL */
  • doc/Makefile.bsp

    re5c565 r454d97a  
    134134info: singular.hlp
    135135
    136 singular.hlp: ${MANUAL_FILES} singular.tex s-plural.tex s-plulibs.tex
     136singular.hlp: ${MANUAL_FILES} singular.tex s-plural.tex s-plulibs.tex s-letterplace.tex
    137137        - ${MAKEINFO} --no-split singular.tex
    138138
     
    140140dvi: manual.dvi usercard.dvi
    141141
    142 singular.dvi: ${MANUAL_FILES} singular.tex s-plural.tex s-plulibs.tex
     142singular.dvi: ${MANUAL_FILES} singular.tex s-plural.tex s-plulibs.tex s-letterplace.tex
    143143        tex singular.tex
    144144        texindex singular.cp
     
    147147        tex singular.tex
    148148
    149 singular.pdf: ${MANUAL_FILES} singular.tex s-plural.tex s-plulibs.tex
     149singular.pdf: ${MANUAL_FILES} singular.tex s-plural.tex s-plulibs.tex s-letterplace.tex
    150150        ${TEXI2PDF} singular.tex
    151151
    152 manual.dvi: ${MANUAL_FILES} manual.tex s-plural.tex s-plulibs.tex
     152manual.dvi: ${MANUAL_FILES} manual.tex s-plural.tex s-plulibs.tex  s-letterplace.tex
    153153        tex manual.tex
    154154        texindex manual.cp
     
    174174        sed -e "s/BR_PLURAL_BR/(plural)/g" <plulibs.tex >s-plulibs.tex
    175175
     176s-letterplace.tex: letterplace.tex
     177        sed -e "s/BR_LETTERPLACE_BR/(letterplace)/g" <letterplace.tex >s-letterplace.tex
     178       
    176179# postscript stuff
    177180ps: dvi manual.ps usercard.ps
     
    270273#
    271274html: ${TMP_DIR} ${HTML_SUBDIR}/${HTML_MANUAL_TOP} ${IMAGES_HTML} $(STANDALONE_TEXI_FILES)
    272 ${HTML_SUBDIR}/${HTML_MANUAL_TOP}: ${TEXI2HTML_INIT} ${TEXI2HTML} singular.tex s-plural.tex
     275${HTML_SUBDIR}/${HTML_MANUAL_TOP}: ${TEXI2HTML_INIT} ${TEXI2HTML} singular.tex s-plural.tex s-letterplace.tex
    273276        ${PERL} ${TEXI2HTML} ${TEXI2HTML_OPTS} -prefix ${HTML_MANUAL_PREFIX} \
    274277        -top_file ${HTML_MANUAL_TOP} singular.tex
     
    384387        /bin/rm -f *.fn *.fns *.ky *.kys *.log *.pg *.pgs *.toc *.tp
    385388        /bin/rm -f *.tps *.vr *.vrs *.dvi *.ps
    386         /bin/rm -f s-plural.tex
     389        /bin/rm -f s-plural.tex s-plulibs.tex s-letterplace.tex
    387390        /bin/rm -f singular.hlp manual.hlp  ${DOC2TEX_FILES} singular.idx
    388391        /bin/rm -f manual.hlp
  • kernel/GBEngine/kstd1.h

    re5c565 r454d97a  
    4141ideal kStdShift(ideal F, ideal Q, tHomog h,intvec ** mw, intvec *hilb=NULL,
    4242    int syzComp=0, int newIdeal=0, intvec *vw=NULL, BOOLEAN rightGB=FALSE);
     43
     44ideal freegb(ideal F, ideal Q);
     45ideal rightgb(ideal F, ideal Q);
    4346
    4447/* the following global data are defined in kutil.cc */
  • kernel/GBEngine/kutil.h

    re5c565 r454d97a  
    861861int redFirstShift (LObject* h,kStrategy strat); // ok
    862862
    863 ideal freegb(ideal F, ideal Q);
    864 ideal rightgb(ideal F, ideal Q);
    865 
    866863ideal bbaShift(ideal F, ideal Q,intvec *w,intvec *hilb,kStrategy strat);
    867864// test syz strategy: // will be removed soon
Note: See TracChangeset for help on using the changeset viewer.