Changeset 5bccba in git


Ignore:
Timestamp:
Feb 11, 2019, 5:41:21 PM (5 years ago)
Author:
Viktor Levandovskyy <levandov@…>
Branches:
(u'fieker-DuVal', '117eb8c30fc9e991c4decca4832b1d19036c4c65')(u'spielwiese', 'd25190065115c859833252500a64cfb7b11e3a50')
Children:
77624bdb8f875aa938e9fda67d8720405651c08d
Parents:
1bd40025d3997a6d11d72e7f8e2834d3fdd83ef9dfa15b9f0da1b32d9c4aff3f6014b3b03d8a72c2
Message:
Merge remote-tracking branch 'upstream/spielwiese' into spielwiese
Files:
29 edited
2 moved

Legend:

Unmodified
Added
Removed
  • Singular/LIB/fpadim.lib

    r1bd400 r5bccba  
    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

    r1bd400 r5bccba  
    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

    r1bd400 r5bccba  
    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

    r1bd400 r5bccba  
    2323
    2424PROCEDURES:
    25 freeAlgebra(r, d);               creates a Letterplace ring out of given data
    2625isFreeAlgebra(r);                check whether r is a letterplace ring (free algebra)
    2726lpDegBound(R);                   returns the degree bound of a letterplace ring
    2827lpVarBlockSize(R);               returns the size of the letterplace blocks
    29 
    30 letplaceGBasis(I);               (deprecated, use twostd) two-sided Groebner basis of a letterplace ideal I
    31 
     28letplaceGBasis(I);               (deprecated) two-sided Groebner basis of a letterplace ideal I
    3229lpDivision(f,I);                 two-sided division with remainder
    3330lpGBPres2Poly(L,I);              reconstructs a polynomial from the output of lpDivision
    34 
    3531lieBracket(a,b[, N]);            Lie bracket ab-ba of two letterplace polynomials
    3632isOrderingShiftInvariant(i);     tests shift-invariance of the monomial ordering
    3733isVar(p);                        check whether p is a power of a single variable
    38 
    39 lpLmDivides(ideal I, poly p);    tests whether there exists q in I, such that LM(q)|LM(p)
    40 lpVarAt(poly p, int pos);        returns the variable (as a poly) at position pos of the poly p
    41 
    42 makeLetterplaceRing(d);          (deprecated, use freeAlgebra) creates a Letterplace ring out of given data
     34makeLetterplaceRing(d);          (deprecated) creates a Letterplace ring out of given data
    4335setLetterplaceAttributes(R,d,b); (for testing purposes) supplies ring R with the letterplace structure
    4436
     
    6254
    6355LIB "qhmoduli.lib"; // for Max
    64 LIB "bfun.lib"; // for inForm
    65 LIB "fpadim.lib"; // for intvec conversion
    6656LIB "fpalgebras.lib"; // for compatibility
    6757
     
    8474  example isVar;
    8575
    86   example lpLmDivides;
    87   example lpVarAt;
    88 
    8976  example ivL2lpI;
    9077  example iv2lp;
     
    10087RETURN: ring with special attributes set
    10188PURPOSE: sets attributes for a letterplace ring:
    102 @*      'isLetterplaceRing' = true, 'uptodeg' = d, 'lV' = b, where
    103 @*      'uptodeg' stands for the degree bound,
    104 @*      '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.
    10592NOTE: Activate the resulting ring by using @code{setring}
    10693"
     
    340327RETURN:  int
    341328PURPOSE: check, whether leading monomial of p is a power of a single variable
    342 @* 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.
    343330EXAMPLE: example isVar; shows examples
    344331"
     
    380367}
    381368
    382 proc lpLmDivides(ideal I, poly p)
    383 "USAGE: lpLmDivides(I); I an ideal
    384 RETURN: boolean
    385 ASSUME: basering is a Letterplace ring
    386 PURPOSE: tests if there is a polynomial q in I with LM(q)|LM(p)
    387 EXAMPLE: example lpLmDivides; shows examples
    388 "
    389 {
    390   ERROR(" freegb.so not loaded");
    391 }
    392 example
    393 {
    394   "EXAMPLE:"; echo = 2;
    395   ring r = 0,(x,y),dp;
    396   def R = freeAlgebra(r, 5);
    397   setring R;
    398   poly p = x*y*y;
    399   lpLmDivides(y*y, p);
    400   lpLmDivides(y*x, p);
    401   lpLmDivides(ideal(y*y, y*x), p);
    402 }
    403 
    404 proc lpVarAt(poly p, int pos)
    405 "USAGE: lpVarAt(p, pos); p a poly, pos an int
    406 RETURN: poly
    407 ASSUME: basering is a Letterplace ring
    408 PURPOSE: returns the variable (as a poly) at position pos of the poly p
    409 EXAMPLE: example lpVarAt; shows examples
    410 "
    411 {
    412   ERROR(" freegb.so not loaded");
    413 }
    414 example
    415 {
    416   "EXAMPLE:"; echo = 2;
    417   ring r = 0,(x,y),dp;
    418   def R = freeAlgebra(r, 5);
    419   setring R;
    420   poly p = y*y*x;
    421   lpVarAt(p, 3);
    422 }
    423 
    424369proc letplaceGBasis(def I)
    425370"USAGE: letplaceGBasis(I);  I an ideal/module
    426371RETURN: ideal/module
    427 ASSUME: basering is a Letterplace ring, input consists of Letterplace
    428 @*      polynomials
    429 PURPOSE: compute the two-sided Groebner basis of I via Letterplace
    430 @*       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)
    431374NOTE: the degree bound for this computation is read off the letterplace
    432 @*    structure of basering
     375      structure of basering
    433376EXAMPLE: example letplaceGBasis; shows examples
    434377"
     
    469412PURPOSE:compute the Lie bracket [a,b] = ab - ba between letterplace polynomials
    470413NOTE: if N>1 is specified, then the left normed bracket [a,[...[a,b]]]] is
    471 @*    computed.
     414computed.
    472415EXAMPLE: example lieBracket; shows examples
    473416"
     
    566509RETURN:  ring
    567510ASSUME: L has a special form. Namely, it is a list of modules, where
    568 
    569511 - each generator of every module stands for a monomial times coefficient in
    570 @* free algebra,
    571 
     512   free algebra,
    572513 - in such a vector generator, the 1st entry is a nonzero coefficient from the
    573 @* ground field
    574 
     514   ground field
    575515 - and each next entry hosts a variable from the basering.
    576516PURPOSE: compute the two-sided Groebner basis of an ideal, encoded by L
    577 @* in the free associative algebra, up to degree d
     517  in the free associative algebra, up to degree d
    578518NOTE: Apply @code{lst2str} to the output in order to obtain a better readable
    579 @*    presentation
     519   presentation
    580520EXAMPLE: example freeGBasis; shows examples
    581521"
     
    1054994  def R = freeAlgebra(r, 7);
    1055995  isFreeAlgebra(R);
    1056 }
    1057 
    1058 proc freeAlgebra(def r, int d)
    1059 "USAGE:  freeAlgebra(r, d); r a ring, d an integer
    1060 RETURN:  ring
    1061 PURPOSE: creates a letterplace ring with the ordering of r
    1062 EXAMPLE: example freeAlgebra; shows examples
    1063 "
    1064 {
    1065   ERROR(" freegb.so not loaded");
    1066 }
    1067 example
    1068 {
    1069   "EXAMPLE:"; echo = 2;
    1070   ring r = 0,(x,y,z),dp;
    1071   def R = freeAlgebra(r, 7);
    1072   R;
    1073   ring r2 = 0,(x,y,z),lp;
    1074   def R2 = freeAlgebra(r2, 7);
    1075   R2;
    1076996}
    1077997
     
    32313151RETURN: int
    32323152NOTE: 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.
    3233 @*      If withHoles != 0 even Letterplace polynomials with holes (eg. x(1)*y(4)) are considered.
     3153
     3154If withHoles != 0 even Letterplace polynomials with holes (eg. x(1)*y(4)) are considered.
    32343155ASSUME: - basering is a Letterplace ring.
    32353156"
     
    38863807static proc mod_init()
    38873808{
    3888   LIB"freegb.so";
    3889 }
     3809  LIB"freealgebra.so";
     3810}
  • Singular/LIB/ncfactor.lib

    rdfa15b r5bccba  
    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

    r1bd400 r5bccba  
    13961396
    13971397///////////////////////////////////////////////////////////////////////////////
    1398 proc rightStd(def I)
     1398proc rightStd(def I)// just an alias for compatibility
    13991399"USAGE:  rightStd(I); I an ideal/ module
    14001400PURPOSE: compute a right Groebner basis of I
     
    14031403"
    14041404{
    1405   def A = basering;
    1406   def Aopp = opposite(A);
    1407   setring Aopp;
    1408   def Iopp = oppose(A,I);
    1409   def Jopp = groebner(Iopp);
    1410   setring A;
    1411   def J = oppose(Aopp,Jopp);
    1412   return(J);
     1405  return(rightstd(I));
    14131406}
    14141407example
     
    17711764RETURN:  ring
    17721765PURPOSE: create a copy of a given ring equipped with the
    1773 @* elimination ordering for module components @code{(c,<)}
     1766  elimination ordering for module components @code{(c,<)}
    17741767NOTE: usually the list argument contains a ring to work with
    17751768EXAMPLE: example makeModElimRing; shows an example
  • Singular/checklibs.c

    r1bd400 r5bccba  
    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/Makefile.am

    r1bd400 r5bccba  
    11ACLOCAL_AMFLAGS = -I ../m4
    22
    3 SUBDIRS=staticdemo bigintm subsets syzextra pyobject customstd gfanlib python gitfan polymake singmathic Order interval cohomo freegb
     3SUBDIRS=staticdemo bigintm subsets syzextra pyobject customstd gfanlib python gitfan polymake singmathic Order interval cohomo freealgebra
  • Singular/dyn_modules/freealgebra/Makefile.am

    r1bd400 r5bccba  
    11ACLOCAL_AMFLAGS = -I ../../m4
    22
    3 if SI_BUILTIN_FREEGB
    4   noinst_LTLIBRARIES=freegb.la
     3if SI_BUILTIN_FREEALGEBRA
     4  noinst_LTLIBRARIES=freealgebra.la
    55  P_PROCS_MODULE_LDFLAGS = -module
    66  P_PROCS_CPPFLAGS_COMMON = -DSTATIC_VERSION
    77else
    8   module_LTLIBRARIES=freegb.la
     8  module_LTLIBRARIES=freealgebra.la
    99  moduledir = $(libexecdir)/singular/MOD
    1010  P_PROCS_CPPFLAGS_COMMON = -DDYNAMIC_VERSION
     
    1818
    1919
    20 freegb_la_CPPFLAGS  = ${MYINCLUDES} ${P_PROCS_CPPFLAGS_COMMON}
    21 freegb_la_LDFLAGS   = ${AM_LDFLAGS} ${P_PROCS_MODULE_LDFLAGS} $(SINGULAR_LDFLAGS)
    22 SOURCES = freegb.cc
    23 freegb_la_SOURCES   = $(SOURCES)
     20freealgebra_la_CPPFLAGS  = ${MYINCLUDES} ${P_PROCS_CPPFLAGS_COMMON}
     21freealgebra_la_LDFLAGS   = ${AM_LDFLAGS} ${P_PROCS_MODULE_LDFLAGS} $(SINGULAR_LDFLAGS)
     22SOURCES = freealgebra.cc
     23freealgebra_la_SOURCES   = $(SOURCES)
    2424
  • Singular/dyn_modules/freealgebra/freealgebra.cc

    r1bd400 r5bccba  
    22
    33#ifdef HAVE_SHIFTBBA
    4 static BOOLEAN freegb(leftv res, leftv args)
     4static BOOLEAN freeAlgebra(leftv res, leftv args)
    55{
    66  const short t1[]={2,RING_CMD,INT_CMD};
     
    8080}
    8181
    82 /*==================== divide-test for freeGB  =================*/
    8382static BOOLEAN lpLmDivides(leftv res, leftv h)
    8483{
     
    112111}
    113112
    114 /*==================== get var for freeGB  ====================*/
    115113static BOOLEAN lpVarAt(leftv res, leftv h)
    116114{
     
    130128//------------------------------------------------------------------------
    131129// initialisation of the module
    132 extern "C" int SI_MOD_INIT(freegb)(SModulFunctions* p)
     130extern "C" int SI_MOD_INIT(freealgebra)(SModulFunctions* p)
    133131{
    134132#ifdef HAVE_SHIFTBBA
    135   p->iiAddCproc("freegb.so","freeAlgebra",FALSE,freegb);
    136   p->iiAddCproc("freegb.so","lpLmDivides",FALSE,lpLmDivides);
    137   p->iiAddCproc("freegb.so","lpVarAt",FALSE,lpVarAt);
    138   p->iiAddCproc("freegb.so","stest",TRUE,stest);
    139   p->iiAddCproc("freegb.so","btest",TRUE,btest);
     133  p->iiAddCproc("freealgebra.so","freeAlgebra",FALSE,freeAlgebra);
     134  p->iiAddCproc("freealgebra.so","lpLmDivides",FALSE,lpLmDivides);
     135  p->iiAddCproc("freealgebra.so","lpVarAt",FALSE,lpVarAt);
     136  p->iiAddCproc("freealgebra.so","stest",TRUE,stest);
     137  p->iiAddCproc("freealgebra.so","btest",TRUE,btest);
    140138#endif
    141139  return (MAX_TOK);
  • Singular/iparith.cc

    r1bd400 r5bccba  
    51165116}
    51175117#endif
    5118 
     5118#ifdef HAVE_SHIFTBBA // do not place above jjSTD in this file because we need to reference it
     5119static BOOLEAN jjRIGHTSTD(leftv res, leftv v)
     5120{
     5121  if (rIsLPRing(currRing))
     5122  {
     5123    if (rField_is_numeric(currRing))
     5124      WarnS("groebner base computations with inexact coefficients can not be trusted due to rounding errors");
     5125    ideal result;
     5126    ideal v_id=(ideal)v->Data();
     5127    /* intvec *w=(intvec *)atGet(v,"isHomog",INTVEC_CMD); */
     5128    /* tHomog hom=testHomog; */
     5129    /* if (w!=NULL) */
     5130    /* { */
     5131    /*   if (!idTestHomModule(v_id,currRing->qideal,w)) */
     5132    /*   { */
     5133    /*     WarnS("wrong weights"); */
     5134    /*     w=NULL; */
     5135    /*   } */
     5136    /*   else */
     5137    /*   { */
     5138    /*     hom=isHomog; */
     5139    /*     w=ivCopy(w); */
     5140    /*   } */
     5141    /* } */
     5142    /* result=kStd(v_id,currRing->qideal,hom,&w); */
     5143    result = rightgb(v_id, currRing->qideal);
     5144    idSkipZeroes(result);
     5145    res->data = (char *)result;
     5146    if(!TEST_OPT_DEGBOUND) setFlag(res,FLAG_STD);
     5147    /* if (w!=NULL) atSet(res,omStrDup("isHomog"),w,INTVEC_CMD); */
     5148    return FALSE;
     5149  }
     5150  else if (rIsPluralRing(currRing))
     5151  {
     5152    ideal I=(ideal)v->Data();
     5153
     5154    ring A = currRing;
     5155    ring Aopp = rOpposite(A);
     5156    currRing = Aopp;
     5157    ideal Iopp = idOppose(A, I, Aopp);
     5158    ideal Jopp = kStd(Iopp,currRing->qideal,testHomog,NULL);
     5159    currRing = A;
     5160    ideal J = idOppose(Aopp, Jopp, A);
     5161
     5162    id_Delete(&Iopp, Aopp);
     5163    id_Delete(&Jopp, Aopp);
     5164    rDelete(Aopp);
     5165
     5166    idSkipZeroes(J);
     5167    res->data = (char *)J;
     5168    if(!TEST_OPT_DEGBOUND) setFlag(res,FLAG_STD);
     5169    return FALSE;
     5170  }
     5171  else
     5172  {
     5173    return jjSTD(res, v);
     5174  }
     5175}
     5176#endif
    51195177static BOOLEAN jjTYPEOF(leftv res, leftv v)
    51205178{
  • Singular/table.h

    r1bd400 r5bccba  
    245245,{D(jjDUMMY),      RESOLUTION_CMD,  RESOLUTION_CMD, RESOLUTION_CMD, ALLOW_PLURAL |ALLOW_RING}
    246246,{D(jjRESTART),    RESTART_CMD,     NONE,           INT_CMD,        ALLOW_NC |ALLOW_RING}
     247#ifdef HAVE_SHIFTBBA
     248,{D(jjRIGHTSTD),   RIGHTSTD_CMD,    IDEAL_CMD,      IDEAL_CMD     , ALLOW_NC |NO_RING}
     249#endif
    247250,{D(jjRINGLIST),   RINGLIST_CMD,    LIST_CMD,       RING_CMD      , ALLOW_NC |ALLOW_RING}
    248251,{D(jjRINGLIST_C), RING_LIST_CMD,   LIST_CMD,       CRING_CMD     , ALLOW_NC |ALLOW_RING}
     
    11681171  { "return",      0, RETURN ,            RETURN},
    11691172  { "RETURN",      0, END_GRAMMAR ,       RETURN},
     1173#ifdef HAVE_SHIFTBBA
     1174  { "rightstd",    0, RIGHTSTD_CMD ,      CMD_1},
     1175#endif /* HAVE_PLURAL */
    11701176  { "ring",        0, RING_CMD ,          RING_CMD},
    11711177  { "ringlist",    0, RINGLIST_CMD ,      CMD_1},
  • Singular/tok.h

    r1bd400 r5bccba  
    169169  RESTART_CMD,
    170170  RESULTANT_CMD,
     171  RIGHTSTD_CMD,
    171172  RINGLIST_CMD,
    172173  RING_LIST_CMD,
  • configure.ac

    r1bd400 r5bccba  
    249249AC_CONFIG_FILES([Singular/dyn_modules/staticdemo/Makefile])
    250250AC_CONFIG_FILES([Singular/dyn_modules/subsets/Makefile])
    251 AC_CONFIG_FILES([Singular/dyn_modules/freegb/Makefile])
     251AC_CONFIG_FILES([Singular/dyn_modules/freealgebra/Makefile])
    252252AC_CONFIG_FILES([Singular/dyn_modules/gitfan/Makefile])
    253253AC_CONFIG_FILES([Singular/dyn_modules/interval/Makefile])
  • doc/Makefile.bsp

    rdfa15b r5bccba  
    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.cc

    r1bd400 r5bccba  
    20932093
    20942094#ifdef HAVE_SHIFTBBA
    2095   if(rIsLPRing(currRing)) return freegb(F);
     2095  if(rIsLPRing(currRing)) return freegb(F, Q);
    20962096#endif
    20972097
  • kernel/GBEngine/kstd1.h

    r1bd400 r5bccba  
    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/kstd2.cc

    r1bd400 r5bccba  
    44594459
    44604460
    4461 ideal freegb(ideal F)
     4461ideal freegb(ideal F, ideal Q)
    44624462{
    44634463  assume(rIsLPRing(currRing));
    44644464  assume(idIsInV(F));
    4465   ideal RS = kStdShift(F, NULL, testHomog, NULL);
     4465  ideal RS = kStdShift(F, Q, testHomog, NULL);
    44664466  idSkipZeroes(RS); // is this even necessary?
    44674467  assume(idIsInV(RS));
  • kernel/GBEngine/kutil.h

    r1bd400 r5bccba  
    861861int redFirstShift (LObject* h,kStrategy strat); // ok
    862862
    863 ideal freegb(ideal F);
    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
  • kernel/ideals.h

    r1bd400 r5bccba  
    140140ideal   idLiftStd  (ideal h1, matrix *m, tHomog h=testHomog, ideal *syz=NULL, GbVariant a=GbDefault);
    141141
    142 ideal   idLift (ideal mod, ideal sumod,ideal * rest=NULL,
     142ideal   idLift (ideal mod, ideal submod,ideal * rest=NULL,
    143143             BOOLEAN goodShape=FALSE, BOOLEAN isSB=TRUE,BOOLEAN divide=FALSE,
    144144             matrix *unit=NULL, GbVariant a=GbDefault);
  • kernel/polys.cc

    r1bd400 r5bccba  
    77#include "kernel/ideals.h"
    88#include "polys/clapsing.h"
     9#include "polys/clapconv.h"
    910
    1011/// Widely used global variable which specifies the current polynomial ring for Singular interpreter and legacy implementatins.
     
    5051    if(p_GetComp(p,r)==0)
    5152    {
    52       if ((r->cf->convSingNFactoryN!=ndConvSingNFactoryN)
     53      if((rFieldType(r)==n_transExt)
     54      &&(convSingTrP(p,r))
     55      &&(convSingTrP(q,r)))
     56      {
     57        poly res=singclap_pdivide(p, q, r);
     58        p_Delete(&p,r);
     59        p_Delete(&q,r);
     60        return res;
     61      }
     62      else if ((r->cf->convSingNFactoryN!=ndConvSingNFactoryN)
    5363      &&(!rField_is_Ring(r)))
    5464      {
     
    7181        SI_RESTORE_OPT1(save_opt);
    7282        if (r!=save_ring) rChangeCurrRing(save_ring);
    73         if (idIs0(R))
    74         {
    75           matrix T = id_Module2formatedMatrix(m,1,1,r);
    76           p=MATELEM(T,1,1); MATELEM(T,1,1)=NULL;
    77           id_Delete((ideal *)&T,r);
    78         }
    79         else p=NULL;
     83        matrix T = id_Module2formatedMatrix(m,1,1,r);
     84        p=MATELEM(T,1,1); MATELEM(T,1,1)=NULL;
     85        id_Delete((ideal *)&T,r);
    8086        id_Delete((ideal *)&U,r);
    8187        id_Delete(&R,r);
     
    109115        if (I->m[i]!=NULL)
    110116        {
    111           if ((r->cf->convSingNFactoryN!=ndConvSingNFactoryN)
     117          if((rFieldType(r)==n_transExt)
     118          &&(convSingTrP(I->m[i],r))
     119          &&(convSingTrP(q,r)))
     120          {
     121            h=singclap_pdivide(I->m[i],q,r);
     122          }
     123          else if ((r->cf->convSingNFactoryN!=ndConvSingNFactoryN)
    112124          &&(!rField_is_Ring(r)))
    113125            h=singclap_pdivide(I->m[i],q,r);
     
    164176    return p_DivideM(p,q,r);
    165177  }
    166   return FALSE;
     178  return NULL;
     179}
     180
     181poly p_DivRem(poly p, poly q, poly &rest, const ring r)
     182{
     183  assume(q!=NULL);
     184  rest=NULL;
     185  if (q==NULL)
     186  {
     187    WerrorS("div. by 0");
     188    return NULL;
     189  }
     190  if (p==NULL)
     191  {
     192    p_Delete(&q,r);
     193    return NULL;
     194  }
     195  if (rIsLPRing(r))
     196  {
     197    WerrorS("not implemented for letterplace rings");
     198    return NULL;
     199  }
     200  if(p_GetComp(p,r)==0)
     201  {
     202    if((rFieldType(r)==n_transExt)
     203    &&(convSingTrP(p,r))
     204    &&(convSingTrP(q,r)))
     205    {
     206      poly res=singclap_pdivide(p, q, r);
     207      rest=singclap_pmod(p,q,r);
     208      p_Delete(&p,r);
     209      p_Delete(&q,r);
     210      return res;
     211    }
     212    else if ((r->cf->convSingNFactoryN!=ndConvSingNFactoryN)
     213    &&(!rField_is_Ring(r)))
     214    {
     215      poly res=singclap_pdivide(p, q, r);
     216      rest=singclap_pmod(p,q,r);
     217      p_Delete(&p,r);
     218      p_Delete(&q,r);
     219      return res;
     220    }
     221    else
     222    {
     223      ideal vi=idInit(1,1); vi->m[0]=q;
     224      ideal ui=idInit(1,1); ui->m[0]=p;
     225      ideal R; matrix U;
     226      ring save_ring=currRing;
     227      if (r!=currRing) rChangeCurrRing(r);
     228      int save_opt;
     229      SI_SAVE_OPT1(save_opt);
     230      si_opt_1 &= ~(Sy_bit(OPT_PROT));
     231      ideal m = idLift(vi,ui,&R, FALSE,TRUE,TRUE,&U);
     232      SI_RESTORE_OPT1(save_opt);
     233      if (r!=save_ring) rChangeCurrRing(save_ring);
     234      matrix T = id_Module2formatedMatrix(m,1,1,r);
     235      p=MATELEM(T,1,1); MATELEM(T,1,1)=NULL;
     236      id_Delete((ideal *)&T,r);
     237      T = id_Module2formatedMatrix(R,1,1,r);
     238      rest=MATELEM(T,1,1); MATELEM(T,1,1)=NULL;
     239      id_Delete((ideal *)&T,r);
     240      id_Delete((ideal *)&U,r);
     241      id_Delete(&R,r);
     242      //vi->m[0]=NULL; ui->m[0]=NULL;
     243      id_Delete(&vi,r);
     244      id_Delete(&ui,r);
     245      return p;
     246    }
     247  }
     248  return NULL;
    167249}
    168250
  • kernel/polys.h

    r1bd400 r5bccba  
    160160#endif
    161161
    162 /// polynomial division, ignoring the rest
     162/// polynomial division a/b, ignoring the rest
    163163/// via singclap_pdivide resp. idLift
    164164/// destroyes a,b
    165165poly p_Divide(poly a, poly b, const ring r);
     166poly p_DivRem(poly a, poly b, poly &rest, const ring r); /*julia*/
    166167
    167168/// polynomial gcd
  • libpolys/polys/clapconv.cc

    r1bd400 r5bccba  
    290290  while ( p!=NULL )
    291291  {
    292     n_Normalize(p_GetCoeff(p, r), r->cf);
     292    //n_Normalize(p_GetCoeff(p, r), r->cf);
    293293
    294294    // test if denominator is constant
    295     if (!p_IsConstantPoly(DEN ((fraction)p_GetCoeff (p,r)),r->cf->extRing) && !errorreported)
     295    if (!errorreported && !p_IsConstantPoly(DEN ((fraction)p_GetCoeff (p,r)),r->cf->extRing))
    296296      WerrorS("conversion error: denominator!= 1");
    297297
     
    316316  }
    317317  return result;
     318}
     319
     320BOOLEAN convSingTrP(poly p, const ring r )
     321{
     322  while ( p!=NULL )
     323  {
     324    n_Normalize(p_GetCoeff(p, r), r->cf);
     325
     326    // test if denominator is constant
     327    if (!p_IsConstantPoly(DEN ((fraction)p_GetCoeff (p,r)),r->cf->extRing))
     328      return FALSE;
     329    pIter(p);
     330  }
     331  return TRUE;
    318332}
    319333
  • libpolys/polys/clapconv.h

    r1bd400 r5bccba  
    3030
    3131CanonicalForm convSingTrPFactoryP ( poly p, const ring r );
     32BOOLEAN convSingTrP(poly p, const ring r );
    3233poly convFactoryPSingTrP ( const CanonicalForm & f, const ring r );
    3334
  • libpolys/polys/clapsing.cc

    r1bd400 r5bccba  
    8484    else
    8585    {
     86      convSingTrP(f,r);
     87      convSingTrP(g,r);
    8688      CanonicalForm F( convSingTrPFactoryP( f,r ) ), G( convSingTrPFactoryP( g,r ) );
    8789      res= convFactoryPSingTrP( gcd( F, G ),r );
  • libpolys/polys/monomials/ring.cc

    r1bd400 r5bccba  
    51305130  int lb = rBlocks(r) - 2;
    51315131  return (r->order[lb] == ringorder_c || r->order[lb] == ringorder_C);
    5132 }
    5133 
    5134 n_coeffType rFieldType(ring r)
    5135 {
    5136   return (r->cf->type);
    5137   if (rField_is_Zp(r))     return n_Zp;
    5138   if (rField_is_Q(r))      return n_Q;
    5139   if (rField_is_R(r))      return n_R;
    5140   if (rField_is_GF(r))     return n_GF;
    5141   if (rField_is_long_R(r)) return n_long_R;
    5142   if (rField_is_Zp_a(r))   return getCoeffType(r->cf);
    5143   if (rField_is_Q_a(r))    return getCoeffType(r->cf);
    5144   if (rField_is_long_C(r)) return n_long_C;
    5145   if (rField_is_Z(r))         return n_Z;
    5146   if (rField_is_Zn(r))        return n_Zn;
    5147   if (rField_is_Ring_PtoM(r)) return n_Znm;
    5148   if (rField_is_Ring_2toM(r)) return  n_Z2m;
    5149 
    5150   return n_unknown;
    51515132}
    51525133
  • libpolys/polys/monomials/ring.h

    r1bd400 r5bccba  
    548548{ assume(r != NULL); assume(r->cf != NULL); return nCoeff_has_simple_Alloc(r->cf); }
    549549
    550 n_coeffType rFieldType(const ring r);
     550/// the type of the coefficient filed of r (n_Zp, n_Q, etc)
     551static inline n_coeffType rFieldType(const ring r) { return (r->cf->type); }
    551552
    552553/// this needs to be called whenever a new ring is created: new fields
  • m4/options.m4

    r1bd400 r5bccba  
    321321  bi_staticdemo=false
    322322  bi_subsets=false
    323   bi_freegb=false
     323  bi_freealgebra=false
    324324  bi_syzextra=false
    325325  bi_pyobject=false
     
    357357       staticdemo ) bi_staticdemo=true;;
    358358       subsets ) bi_subsets=true;;
    359        freegb ) bi_freegb=true;;
     359       freealgebra ) bi_freealgebra=true;;
    360360       syzextra ) bi_syzextra=true ;;
    361361       pyobject ) bi_pyobject=true ;;
     
    396396 AM_CONDITIONAL([SI_BUILTIN_STATICDEMO], [test x$bi_staticdemo = xtrue])
    397397 AM_CONDITIONAL([SI_BUILTIN_SUBSETS], [test x$bi_subsets = xtrue])
    398  AM_CONDITIONAL([SI_BUILTIN_FREEGB], [test x$bi_freegb = xtrue])
     398 AM_CONDITIONAL([SI_BUILTIN_FREEALGEBRA], [test x$bi_freealgebra = xtrue])
    399399 AM_CONDITIONAL([SI_BUILTIN_SYZEXTRA], [test x$bi_syzextra = xtrue])
    400400 AM_CONDITIONAL([SI_BUILTIN_PYOBJECT], [test x$bi_pyobject = xtrue])
Note: See TracChangeset for help on using the changeset viewer.