Changeset 578051 – Singular

Singular/LIB/fpadim.lib

-                      r179aaba
+                      r578051
 info="
 LIBRARY: fpadim.lib     Algorithms for quotient algebras in the letterplace case
+AUTHORS: Grischa Studzinski,       grischa.studzinski@rwth-aachen.de
+AUTHORS: Grischa Studzinski,       grischa.studzinski at rwth-aachen.de
+@*       Viktor Levandovskyy,      viktor.levandovskyy at math.rwth-aachen.de
+@*       Karim Abou Zeid,          karim.abou.zeid at rwth-aachen.de
 Support: Joint projects LE 2697/2-1 and KR 1907/3-1 of the Priority Programme SPP 1489:
+@* 'Algorithmische und Experimentelle Methoden in Algebra, Geometrie und Zahlentheorie'
+@* of the German DFG
+OVERVIEW: Given the free algebra A = K<x_1,...,x_n> and a (finite) Groebner basis
+'Algorithmische und Experimentelle Methoden in Algebra, Geometrie und Zahlentheorie'
+of the German DFG
+and Project II.6 of the transregional collaborative research centre
+SFB-TRR 195 'Symbolic Tools in Mathematics and their Application' of the German DFG
+OVERVIEW: Given the free associative algebra A = K<x_1,...,x_n> and a (finite) Groebner basis
       GB = {g_1,..,g_w}, one is interested in the K-dimension and in the
       explicit K-basis of A/<GB>.
       Therefore one is interested in the following data:
+@*      - the Ufnarovskij graph induced by GB
+@*      - the mistletoes of A/<GB>
+@*      - the K-dimension of A/<GB>
+@*      - the Hilbert series of A/<GB>
+      The Ufnarovskij graph is used to determine whether A/<GB> has finite
+      K-dimension. One has to check if the graph contains cycles.
+      For the whole theory we refer to [ufna]. Given a
+      reduced set of monomials GB one can define the basis tree, whose vertex
+      set V consists of all normal monomials w.r.t. GB. For every two
+      monomials m_1, m_2 in V there is a direct edge from m_1 to m_2, if and
+      only if there exists x_k in {x_1,..,x_n}, such that m_1*x_k = m_2. The
+      set M = {m in V | there is no edge from m to another monomial in V} is
+      called the set of mistletoes. As one can easily see it consists of
+      the endpoints of the graph. Since there is a unique path to every
+      monomial in V the whole graph can be described only from the knowledge
+      of the mistletoes. Note that V corresponds to a basis of A/<GB>, so
+      knowing the mistletoes we know a K-basis. The name mistletoes was given
+      to those points because of these miraculous value and the algorithm is
+      named sickle, because a sickle is the tool to harvest mistletoes.
+      For more details see [studzins]. This package uses the Letterplace
+      format introduced by [lls]. The algebra can either be represented as a
+      Letterplace ring or via integer vectors: Every variable will only be
+      represented by its number, so variable one is represented as 1,
+      variable two as 2 and so on. The monomial x_1*x_3*x_2 for example will
+      be stored as (1,3,2). Multiplication is concatenation. Note that there
+      is no algorithm for computing the normal form needed for our case.
+      Note that the name fpadim.lib is short for dimensions of finite
+      presented algebras.
+      - the Ufnarovskij graph induced by GB
+      - the mistletoes of A/<GB> (special monomials in a basis)
+      - the K-dimension of A/<GB>
+      - the Hilbert series of A/<GB>
+@*      The Ufnarovskij graph is used to determine whether A/<GB> has finite
+@*      K-dimension. One has to check if the graph contains cycles.
+@*      For the whole theory we refer to [ufna]. Given a
+@*      reduced set of monomials GB one can define the basis tree, whose vertex
+@*      set V consists of all normal monomials w.r.t. GB. For every two
+@*      monomials m_1, m_2 in V there is a direct edge from m_1 to m_2, if and
+@*      only if there exists x_k in {x_1,..,x_n}, such that m_1*x_k = m_2. The
+@*      set M = {m in V | there is no edge from m to another monomial in V} is
+@*      called the set of mistletoes. As one can easily see it consists of
+@*      the endpoints of the graph. Since there is a unique path to every
+@*      monomial in V the whole graph can be described only from the knowledge
+@*      of the mistletoes. Note that V corresponds to a basis of A/<GB>, so
+@*      knowing the mistletoes we know a K-basis. The name mistletoes was given
+@*      to those points because of these miraculous value and the algorithm is
+@*      named sickle, because a sickle is the tool to harvest mistletoes.
+@*      For more details see [studzins]. This package uses the Letterplace
+@*      format introduced by [lls]. The algebra can either be represented as a
+@*      Letterplace ring or via integer vectors: Every variable will only be
+@*      represented by its number, so variable one is represented as 1,
+@*      variable two as 2 and so on. The monomial x_1*x_3*x_2 for example will
+@*      be stored as (1,3,2). Multiplication is concatenation. Note that the
+@*      approach in this library does not need an algorithm for computing the normal
+@*      form yet. Note that the name fpadim.lib is short for dimensions of
+@*      finite presented algebras.
+@*
 REFERENCES:
 …
 @*   [ufna] Ufnarovskij: Combinatorical and asymptotic methods in algebra, 1990
 @*   [lls] Levandovskyy, La Scala: Letterplace ideals and non-commutative
           Groebner bases, 2009
+Groebner bases, 2009
 @*   [studzins] Studzinski: Dimension computations in non-commutative,
                      associative algebras, Diploma thesis, RWTH Aachen, 2010
 Assumptions:
 @* - basering is always a Letterplace ring
 @* - all intvecs correspond to Letterplace monomials
+@* - if you specify a different degree bound d,
+     d <= attrib(basering,uptodeg) should hold.
 @* In the procedures below, 'iv' stands for intvec representation
   and 'lp' for the letterplace representation of monomials
+associative algebras, Diploma thesis, RWTH Aachen, 2010
+NOTE:
+- basering is always a Letterplace ring
+- all intvecs correspond to Letterplace monomials
+- if you specify a different degree bound d, d <= attrib(basering,uptodeg) holds
+In the procedures below, 'iv' stands for intvec representation
+and 'lp' for the letterplace representation of monomials
 PROCEDURES:
 …
 sickle(G[,m,d,h]);         can be used to access all lp main procedures
 ivL2lpI(L);           transforms a list of intvecs into an ideal of lp monomials
 iv2lp(I);             transforms an intvec into the corresponding monomial
 …
     {for (i3 = 1; i3 <= n; i3++)
       {for (i4 = 1; i4 <= (n^(i1-1)); i4++)
+      {
+        M[i2,i1] = i3;
+        {M[i2,i1] = i3;
           i2 = i2 + 1;
+       }
+        }
+      }
+    }
 …
 "PURPOSE:checks, if all entries in M are variable-related
+"
+{if ((nrows(M) == 1) && (ncols(M) == 1)) {if (M[1,1] == 0){return(0);}}
+ int i,j;
+{int i,j;
   for (i = 1; i <= nrows(M); i++)
   {for (j = 1; j <= ncols(M); j++)
 …
+}
+static proc findCycleDFS(int i, intmat T, intvec V)
+"
+PURPOSE:
+this is a classical deep-first search for cycles contained in a graph given by an intmat
+"
+{
+  intvec rV;
+  int k,k1,t;
+  int j = V[size(V)];
+  if (T[j,i] > 0) {return(V);}
+  else
+  {
+    for (k = 1; k <= ncols(T); k++)
+    {
+      t = 0;
+      if (T[j,k] > 0)
+      {
+        for (k1 = 1; k1 <= size(V); k1++) {if (V[k1] == k) {t = 1; break;}}
+        if (t == 0)
+        {
+          rV = V;
+          rV[size(rV)+1] = k;
+          rV = findCycleDFS(i,T,rV);
+          if (rV[1] > -1) {return(rV);}
+        }
+      }
+    }
+  }
+  return(intvec(-1));
+}
 static proc findHCoeff(intvec V,int n,list L,intvec P,intvec H,list #)
 "USAGE: findHCoeff(V,n,L,P,H,degbound); L a list of intmats, degbound an integer
 …
+      }
       return(R);
+    }
+  }
 …
+}
+static proc growthAlg(intmat T, list #)
+"
+real algorithm for checking the growth of an algebra
+"
+{
+  int s = 1;
+  if (size(#) > 0) { s = #[1];}
+  int j;
+  int n = ncols(T);
+  intvec NV,C; NV[n] = 0; int m,i;
+  intmat T2[n][n] = T[1..n,1..n]; intmat N[n][n];
+  if (T2 == N)
+  {
+    for (i = 1; i <= n; i++)
+    {
+      if (m <  T[n+1,i]) { m = T[n+1,i];}
+    }
+    return(m);
+  }
+  //first part: the diagonals
+  for (i = s; i <= n; i++)
+  {
+    if (T[i,i] > 0)
+    {
+      if ((T[i,i] >= 1) && (T[n+1,i] > 0)) {return(-1);}
+      if ((T[i,i] == 1) && (T[n+1,i] == 0))
+      {
+        T[i,i] = 0;
+        T[n+1,i] = 1;
+        return(growthAlg(T));
+      }
+    }
+  }
+  //second part: searching for the last but one vertices
+  T2 = T2*T2;
+  for (i = s; i <= n; i++)
+  {
+    if ((intvec(T[i,1..n]) <> intvec(0)) && (intvec(T2[i,1..n]) == intvec(0)))
+    {
+      for (j = 1; j <= n; j++)
+      {
+        if ((T[i,j] > 0) && (m < T[n+1,j])) {m = T[n+1,j];}
+      }
+      T[n+1,i] = T[n+1,i] + m;
+      T[i,1..n] = NV;
+      return(growthAlg(T));
+    }
+  }
+  m = 0;
+  //third part: searching for circles
+  for (i = s; i <= n; i++)
+  {
+    T2 = T[1..n,1..n];
+    C = findCycleDFS(i,T2, intvec(i));
+    if (C[1] > 0)
+    {
+      for (j = 2; j <= size(C); j++)
+      {
+        T[i,1..n] = T[i,1..n] + T[C[j],1..n];
+        T[C[j],1..n] = NV;
+      }
+      for (j = 2; j <= size(C); j++)
+      {
+        T[1..n,i] = T[1..n,i] + T[1..n,C[j]];
+        T[1..n,C[j]] = NV;
+      }
+      T[i,i] = T[i,i] - size(C) + 1;
+      m = 0;
+      for (j = 1; j <= size(C); j++)
+      {
+        m = m + T[n+1,C[j]];
+      }
+      for (j = 1; j <= size(C); j++)
+      {
+        T[n+1,C[j]] = m;
+      }
+      return(growthAlg(T,i));
+    }
+    else {ERROR("No Cycle found, something seems wrong! Please contact the authors.");}
+  }
+  m = 0;
+  for (i = 1; i <= n; i++)
+  {
+    if (m < T[n+1,i])
+    {
+      m = T[n+1,i];
+    }
+  }
+  return(m);
+}
+static proc GlDimSuffix(intvec v, intvec g)
+{
+  //Computes the shortest r such that g is a suffix for vr
+  //only valid for lex orderings?
+  intvec r,gt,vt,lt,g2;
+  int lg,lv,l,i,c,f;
+  lg = size(g); lv = size(v);
+  if (lg <= lv)
+  {
+    l = lv-lg;
+  }
+  else
+  {
+    l = 0; g2 = g[(lv+1)..lg];
+    g = g[1..lv]; lg = size(g);
+    c = 1;
+  }
+  while (l < lv)
+  {
+    vt = v[(l+1)..lv];
+    gt = g[1..(lv-l)];
+    lt = size(gt);
+    for (i = 1; i <= lt; i++)
+    {
+      if (vt[i]<>gt[i]) {l++; break;}
+    }
+    if (lt <=i ) { f = 1; break;}
+  }
+  if (f == 0) {return(g);}
+  r = g[(lv-l+1)..lg];
+  if (c == 1) {r = r,g2;}
+  return(r);
+}
+static proc isNormal(intvec V, list G)
+{
+  int i,j,k,l;
+  k = 0;
+  for (i = 1; i <= size(G); i++)
+  {
+    if ( size(G[i]) <= size(V) )
+    {
+      while ( size(G[i])+k <= size(V) )
+      {
+        if ( G[i] == V[(1+k)..size(V)] ) {return(1);}
+      }
+    }
+  }
+  return(0);
+}
+static proc findDChain(list L)
+{
+  list Li; int i,j;
+  for (i = 1; i <= size(L); i++) {Li[i] = size(L[i]);}
+  Li = sort(Li); Li = Li[1];
+  return(Li[size(Li)]);
+}
 static proc isInList(intvec V, list L)
 "USAGE: isInList(V,L); V an intvec, L a list of intvecs
 …
+}
+static proc isPF(intvec P, intvec I)
+"
+PURPOSE:
+checks, if a word P is a praefix of another word I
+"
+{
+  int n = size(P);
+  if (n <= 0 || P == 0) {return(1);}
+  if (size(I) < n) {return(0);}
+  intvec IP = I[1..n];
+  if (IP == P) {return(1);}
+  else {return(0);}
+}
 proc ivL2lpI(list L)
 "USAGE: ivL2lpI(L); L a list of intvecs
 RETURN: ideal
+PURPOSE:Transforming a list of intvecs into an ideal of Letterplace monomials.
+@*      For the encoding of the variables see the overview.
+PURPOSE:Transforming a list of intvecs into an ideal of Letterplace monomials
 ASSUME: - Intvec corresponds to a Letterplace monomial
 @*      - basering has to be a Letterplace ring
+NOTE:   - Assumptions will not be checked!
 EXAMPLE: example ivL2lpI; shows examples
+"
 {checkAssumptions(0,L);
+{
   int i; ideal G;
   poly p;
 …
 RETURN: poly
 PURPOSE:Transforming an intvec into the corresponding Letterplace polynomial
-@*      For the encoding of the variables see the overview.
 ASSUME: - Intvec corresponds to a Letterplace monomial
 @*      - basering has to be a Letterplace ring
 …
 RETURN: ideal
 PURPOSE:Converting a list of intmats into an ideal of corresponding monomials
-@*      The rows of the intmat corresponds to an intvec, which stores the
-@*      monomial.
-@*      For the encoding of the variables see the overview.
 ASSUME: - The rows of each intmat in L must correspond to a Letterplace monomial
 @*      - basering has to be a Letterplace ring
 …
 "USAGE: iv2lpMat(M); M an intmat
 RETURN: ideal
+PURPOSE:Converting an intmat into an ideal of the corresponding monomials.
+@*      The rows of the intmat corresponds to an intvec, which stores the
+@*      monomial.
+@*      For the encoding of the variables see the overview.
+PURPOSE:Converting an intmat into an ideal of the corresponding monomials
 ASSUME: - The rows of M must correspond to Letterplace monomials
 @*      - basering has to be a Letterplace ring
 …
 "USAGE: lpId2ivLi(G); G an ideal
 RETURN: list
+PURPOSE:Transforming an ideal into the corresponding list of intvecs.
+@*      For the encoding of the variables see the overview.
+PURPOSE:Transforming an ideal into the corresponding list of intvecs
 ASSUME: - basering has to be a Letterplace ring
 EXAMPLE: example lpId2ivLi; shows examples
+"
+{int i,j,k;
+{
+  int i,j,k;
   list M;
   checkAssumptions(0,M);
 …
 "USAGE: lp2iv(p); p a poly
 RETURN: intvec
+PURPOSE:Transforming a monomial into the corresponding intvec.
+@*      For the encoding of the variables see the overview.
+PURPOSE:Transforming a monomial into the corresponding intvec
 ASSUME: - basering has to be a Letterplace ring
 NOTE:   - Assumptions will not be checked!
 …
 RETURN: list
 PURPOSE:Converting an ideal into an list of intmats,
+@*      the corresponding intvecs forming the rows.
+@*      For the encoding of the variables see the overview.
+@*      the corresponding intvecs forming the rows
 ASSUME: - basering has to be a Letterplace ring
 EXAMPLE: example lp2ivId; shows examples
 …
 // -----------------main procedures----------------------
+static proc lpGraphOfNormalWords(ideal G)
+"USAGE: lpGraphOfNormalWords(G); G a set of monomials in a letterplace ring
+RETURN: intmat
+PURPOSE: Constructs the graph of normal words induced by G
+@*:      the adjacency matrix of the graph of normal words induced by G
+ASSUME: - basering is a Letterplace ring
+- G are the leading monomials of a Groebner basis
+"
+{
+  // construct the Graph of normal words [Studzinski page 78]
+  // construct set of vertices
+  int v = attrib(basering,"lV"); int d = attrib(basering,"uptodeg");
+  ideal V; poly p,q,w;
+  ideal LG = lead(G);
+  int i,j,k,b; intvec E,Et;
+  for (i = 1; i <= v; i++){V = V, var(i);}
+  for (i = 1; i <= size(LG); i++)
+  {
+    E = leadexp(LG[i]);
+    if (E == intvec(0)) {V = V,monomial(intvec(0));}
+    else
+    {
+      for (j = 1; j < d; j++)
+      {
+        Et = E[(j*v+1)..(d*v)];
+        if (Et == intvec(0)) {break;}
+        else {V = V, monomial(Et);}
+      }
+    }
+  }
+  V = simplify(V,2+4);
+  printf("V = %p", V);
+  // construct incidence matrix
+  list LV = lpId2ivLi(V);
+  intvec Ip,Iw;
+  int n = size(V);
+  intmat T[n+1][n];
+  for (i = 1; i <= n; i++)
+  {
+    // printf("for1 (i=%p, n=%p)", i, n);
+    p = V[i]; Ip = lp2iv(p);
+    for (j = 1; j <= n; j++)
+    {
+      // printf("for2 (j=%p, n=%p)", j, n);
+      k = 1; b = 1;
+      q = V[j];
+      w = lpNF(lpMult(p,q),LG);
+      if (w <> 0)
+      {
+        Iw = lp2iv(w);
+        while (k <= n)
+        {
+          // printf("while (k=%p, n=%p)", k, n);
+          if (isPF(LV[k],Iw) > 0)
+          {if (isPF(LV[k],Ip) == 0) {b = 0; k = n+1;} else {k++;}
+          }
+          else {k++;}
+        }
+        T[i,j] = b;
+        //  print("Incidence Matrix:");
+        // print(T);
+      }
+    }
+  }
+  return(T);
+}
+// This proc is deprecated, see lpGkDim() in fpaprops.lib
+/* proc lpGkDim(ideal G) */
+/* "USAGE: lpGkDim(G); G an ideal in a letterplace ring */
+/* RETURN: int */
+/* PURPOSE: Determines the Gelfand Kirillov dimension of A/<G> */
+/* @*:     -1 means it is infinite */
+/* ASSUME: - basering is a Letterplace ring */
+/* - G is a Groebner basis */
+/* NOTE: see fpaprops.lib for a faster and more up to date version of this method */
+/* " */
+/* { */
+/*   return(growthAlg(lpGraphOfNormalWords(G))); */
+/* } */
 proc ivDHilbert(list L, int n, list #)
 "USAGE: ivDHilbert(L,n[,degbound]); L a list of intmats, n an integer,
 …
 ASSUME: - basering is a Letterplace ring
 @*      - all rows of each intmat correspond to a Letterplace monomial
-@*        for the encoding of the variables see the overview
 @*      - if you specify a different degree bound degbound,
 @*        degbound <= attrib(basering,uptodeg) should hold.
+@*        degbound <= attrib(basering,uptodeg) holds
 NOTE: - If L is the list returned, then L[1] is an integer corresponding to the
 @*      dimension, L[2] is an intvec which contains the coefficients of the
 …
 ASSUME: - basering is a Letterplace ring.
 @*      - All rows of each intmat correspond to a Letterplace monomial.
-@*        for the encoding of the variables see the overview
 @*      - If you specify a different degree bound degbound,
 @*        degbound <= attrib(basering,uptodeg) should hold.
+@*        degbound <= attrib(basering,uptodeg) holds.
 NOTE: - If L is the list returned, then L[1] is an integer, L[2] is an intvec
 @*      which contains the coefficients of the Hilbert series and L[3]
 …
 RETURN: int, 0 if the dimension is finite, or 1 otherwise
 PURPOSE:Decides, whether the K-dimension is finite or not
+ASSUME: - basering is a Letterplace ring
+@*      - All rows of each intmat correspond to a Letterplace monomial
+@*        For the encoding of the variables see the overview.
+NOTE:   - n is the number of variables
+ASSUME: - basering is a Letterplace ring.
+@*      - All rows of each intmat correspond to a Letterplace monomial.
+NOTE:   - n is the number of variables.
 EXAMPLE: example ivDimCheck; shows examples
+"
 …
 ASSUME: - basering is a Letterplace ring.
 @*      - all rows of each intmat correspond to a Letterplace monomial
-@*        for the encoding of the variables see the overview
 @*      - if you specify a different degree bound degbound,
 @*       degbound <= attrib(basering,uptodeg) should hold.
+@*       degbound <= attrib(basering,uptodeg) holds.
 NOTE: - If degbound is set, a degree bound  will be added. By default there
 @*      is no degree bound.
 …
 ASSUME: - basering is a Letterplace ring.
 @*      - all rows of each intmat correspond to a Letterplace monomial
-@*        for the encoding of the variables see the overview
 @*      - if you specify a different degree bound degbound,
 @*        degbound <= attrib(basering,uptodeg) should hold.
+@*        degbound <= attrib(basering,uptodeg) holds.
 NOTE: - If degbound is set, a degree bound will be added. By default there
 @*      is no degree bound.
 …
+"
+{
 //checkAssumptions(0,M);
+  //checkAssumptions(0,M);
   intvec L,A;
   if (size(M) == 0){ERROR("There are no mistletoes, so it appears your dimension is infinite!");}
 …
   for (i = 2; i <= size(M); i++)
   {A = M[i]; L = M[i-1];
    s = size(A);
    if (s > size(L))
    {d = size(L);
     for (j = s; j > d; j--) {Rt = insert(Rt,intvec(A[1..j]));}
     A = A[1..d];
+   }
    if (size(L) > s){L = L[1..s];}
    while (A <> L)
    {Rt = insert(Rt, intvec(A));
     if (size(A) > 1)
     {A = A[1..(size(A)-1)];
      L = L[1..(size(L)-1)];
+    }
     else {break;}
+   }
+    s = size(A);
+    if (s > size(L))
+    {d = size(L);
+      for (j = s; j > d; j--) {Rt = insert(Rt,intvec(A[1..j]));}
+      A = A[1..d];
+    }
+    if (size(L) > s){L = L[1..s];}
+    while (A <> L)
+    {Rt = insert(Rt, intvec(A));
+      if (size(A) > 1)
+      {A = A[1..(size(A)-1)];
+        L = L[1..(size(L)-1)];
+      }
+      else {break;}
+    }
+  }
   return(Rt);
 …
 @*        Otherwise the returned value may differ from the K-dimension.
 @*      - basering is a Letterplace ring.
-@*      - mistletoes are stored as intvecs, as described in the overview
 EXAMPLE: example ivMis2Dim; shows examples
+"
 …
   if (isInList(L,M) > 0) {print("1 is a mistletoe, therefore dim = 1"); return(1);}
   int i,j,d,s;
+  j = 1;
   d = 1 + size(M[1]);
   for (i = 1; i < size(M); i++)
+  {j = 1;
+   s = size(M[i]); if (s > size(M[i+1])){s = size(M[i+1]);}
+   while ((M[i][j] == M[i+1][j]) && (j <= s)){j = j + 1;}
+   d = d + size(M[i+1])- j + 1;
+  {s = size(M[i]); if (s > size(M[i+1])){s = size(M[i+1]);}
+    while ((M[i][j] == M[i+1][j]) && (j <= s)){j = j + 1;}
+    d = d + size(M[i+1])- j + 1;
+  }
   return(d);
 …
 PURPOSE:Orders a given set of mistletoes lexicographically
 ASSUME: - basering is a Letterplace ring.
+@*      - intvecs correspond to monomials, as explained in the overview
+- intvecs correspond to monomials
 NOTE:   - This is preprocessing, it's not needed if the mistletoes are returned
 @*        from the sickle algorithm.
 …
 @*      optional integer
 RETURN: list, containing intvecs, the mistletoes of A/<L>
 PURPOSE:Computing the mistletoes for a given Groebner basis L, given by intmats
+PURPOSE:Computing the mistletoes for a given Groebner basis L
 ASSUME: - basering is a Letterplace ring.
 @*      - all rows of each intmat correspond to a Letterplace monomial
-@*        as explained in the overview
 @*      - if you specify a different degree bound degbound,
 @*        degbound <= attrib(basering,uptodeg) should hold.
+@*        degbound <= attrib(basering,uptodeg) holds.
 NOTE: - If degbound is set, a degree bound will be added. By default there
 @*      is no degree bound.
 …
 ASSUME: - basering is a Letterplace ring.
 @*      - all rows of each intmat correspond to a Letterplace monomial
-@*        as explained in the overview
 @*      - if you specify a different degree bound degbound,
 @*        degbound <= attrib(basering,uptodeg) should hold.
+@*        degbound <= attrib(basering,uptodeg) holds.
 NOTE: - If L is the list returned, then L[1] is an integer, L[2] is a list,
 @*      containing the mistletoes as intvecs.
 …
 ASSUME: - basering is a Letterplace ring.
 @*      - all rows of each intmat correspond to a Letterplace monomial
-@*        as explained in the overview
 @*      - if you specify a different degree bound degbound,
 @*        degbound <= attrib(basering,uptodeg) should hold.
+@*        degbound <= attrib(basering,uptodeg) holds.
 NOTE: - If L is the list returned, then L[1] is an intvec, L[2] is a list,
 @*      containing the mistletoes as intvecs.
 …
 RETURN: list
 PURPOSE:Computing K-dimension and Hilbert series, starting with a lp-ideal
 ASSUME: - basering is a Letterplace ring. G is a Letterplace ideal.
+ASSUME: - basering is a Letterplace ring.
 @*      - if you specify a different degree bound degbound,
 @*        degbound <= attrib(basering,uptodeg) should hold.
+@*        degbound <= attrib(basering,uptodeg) holds.
 NOTE: - If L is the list returned, then L[1] is an integer corresponding to the
 @*      dimension, L[2] is an intvec which contains the coefficients of the
 …
 RETURN: list
 PURPOSE:Computing K-dimension, Hilbert series and mistletoes at once
 ASSUME: - basering is a Letterplace ring.  G is a Letterplace ideal.
+ASSUME: - basering is a Letterplace ring.
 @*      - if you specify a different degree bound degbound,
 @*        degbound <= attrib(basering,uptodeg) should hold.
+@*        degbound <= attrib(basering,uptodeg) holds.
 NOTE: - If L is the list returned, then L[1] is an integer, the K-dimension,
 @*      L[2] is an intvec, the Hilbert series and L[3] is an ideal,
 …
 RETURN: intvec, containing the coefficients of the Hilbert series
 PURPOSE:Computing the Hilbert series
 ASSUME: - basering is a Letterplace ring.  G is a Letterplace ideal.
+ASSUME: - basering is a Letterplace ring.
 @*      - if you specify a different degree bound degbound,
 @*        degbound <= attrib(basering,uptodeg) should hold.
+@*        degbound <= attrib(basering,uptodeg) holds.
 NOTE: - If degbound is set, there will be a degree bound added. 0 means no
 @*      degree bound. Default: attrib(basering,uptodeg).
 …
 RETURN: int, 1 if K-dimension of the factor algebra is infinite, 0 otherwise
 PURPOSE:Checking a factor algebra for finiteness of the K-dimension
 ASSUME: - basering is a Letterplace ring.  G is a Letterplace ideal.
+ASSUME: - basering is a Letterplace ring.
 EXAMPLE: example lpDimCheck; shows examples
+"
 …
 RETURN: int, the K-dimension of the factor algebra
 PURPOSE:Computing the K-dimension of a factor algebra, given via an ideal
 ASSUME: - basering is a Letterplace ring. G is a Letterplace ideal.
+ASSUME: - basering is a Letterplace ring
 @*      - if you specify a different degree bound degbound,
 @*        degbound <= attrib(basering,uptodeg) should hold.
+@*        degbound <= attrib(basering,uptodeg) holds.
 NOTE: - If degbound is set, there will be a degree bound added. 0 means no
 @*      degree bound. Default: attrib(basering, uptodeg).
 …
 RETURN: int, the K-dimension of the factor algebra
 PURPOSE:Computing the K-dimension out of given mistletoes
 ASSUME: - basering is a Letterplace ring. G is a Letterplace ideal.
+ASSUME: - basering is a Letterplace ring.
 @*      - M contains only monomials
 NOTE:   - The mistletoes have to be ordered lexicographically -> OrdMisLex.
 …
 RETURN: ideal, containing the mistletoes, ordered lexicographically
 PURPOSE:A given set of mistletoes is ordered lexicographically
 ASSUME: - basering is a Letterplace ring. G is a Letterplace ideal.
+ASSUME: - basering is a Letterplace ring.
 NOTE:   This is preprocessing, it is not needed if the mistletoes are returned
 @*      from the sickle algorithm.
 …
 RETURN: ideal
 PURPOSE:Computing the mistletoes of K[X]/<G>
 ASSUME: - basering is a Letterplace ring. G is a Letterplace ideal.
+ASSUME: - basering is a Letterplace ring.
 @*      - if you specify a different degree bound degbound,
 @*        degbound <= attrib(basering,uptodeg) should hold.
+@*        degbound <= attrib(basering,uptodeg) holds.
 NOTE: - If degbound is set, there will be a degree bound added. 0 means no
 @*      degree bound. Default: attrib(basering,uptodeg).
 …
 RETURN: list
 PURPOSE:Computing the K-dimension and the mistletoes
 ASSUME: - basering is a Letterplace ring. G is a Letterplace ideal.
+ASSUME: - basering is a Letterplace ring.
 @*      - if you specify a different degree bound degbound,
 @*        degbound <= attrib(basering,uptodeg) should hold.
+@*        degbound <= attrib(basering,uptodeg) holds.
 NOTE: - If L is the list returned, then L[1] is an integer, the K-dimension,
 @*      L[2] is an ideal, the mistletoes.
 …
 RETURN: list
 PURPOSE:Computing the Hilbert series and the mistletoes
 ASSUME: - basering is a Letterplace ring. G is a Letterplace ideal.
+ASSUME: - basering is a Letterplace ring.
 @*      - if you specify a different degree bound degbound,
 @*        degbound <= attrib(basering,uptodeg) should hold.
+@*        degbound <= attrib(basering,uptodeg) holds.
 NOTE: - If L is the list returned, then L[1] is an intvec, corresponding to the
 @*      Hilbert series, L[2] is an ideal, the mistletoes.
 …
 RETURN: list
 PURPOSE:Allowing the user to access all procs with one command
 ASSUME: - basering is a Letterplace ring. G is a Letterplace ideal.
+ASSUME: - basering is a Letterplace ring.
 @*      - if you specify a different degree bound degbound,
 @*        degbound <= attrib(basering,uptodeg) should hold.
+@*        degbound <= attrib(basering,uptodeg) holds.
 NOTE:   The returned object will always be a list, but the entries of the
 @*      returned list may be very different
 …
   sickle(G,0,0,1); // computes Hilbert series only
+}
+proc ivMaxIdeal(int l, int lonly)
+  "USAGE: lpMaxIdeal(l, lonly); l an integer, lonly an integer
+  RETURN: list
+  PURPOSE: computes a list of free monomials in intvec presentation
+  @*       with length <= l
+  @*       if donly <> 0, only monomials of degree d are returned
+  ASSUME: - basering is a Letterplace ring.
+  NOTE: see also lpMaxIdeal()
+  "
+{
+  if (l < 0) {
+    ERROR("l must not be negative")
+  }
+  list words;
+  if (l == 0) {
+     words = 0;
+     return (words);
+  }
+  int lV = attrib(basering, "lV"); // variable count
+  list prevWords;
+  if (l > 1) {
+    prevWords = ivMaxIdeal(l - 1, lonly);
+  } else {
+    prevWords = 0;
+  }
+  for (int i = 1; i <= size(prevWords); i++) {
+    if (size(prevWords[i]) >= l - 1) {
+      for (int j = 1; j <= lV; j++) {
+        intvec word = prevWords[i];
+        word[l] = j;
+        words = insert(words, word);
+        kill word;
+      } kill j;
+    }
+  } kill i;
+  if (!lonly && l > 1) {
+    words = prevWords + words;
+  }
+  return (words);
+}
+example {
+  "EXAMPLE:"; echo = 2;
+  ring r = 0,(a,b,c),dp;
+  def R = makeLetterplaceRing(7); setring R;
+  ivMaxIdeal(1,0);
+  ivMaxIdeal(2,0);
+  ivMaxIdeal(2,1);
+  ivMaxIdeal(4,0);
+  ivMaxIdeal(4,1);
+}
+proc lpMaxIdeal(int d, int donly)
+  "USAGE: lpMaxIdeal(d, donly); d an integer, donly an integer
+  RETURN: ideal
+  PURPOSE: computes a list of free monomials of degree at most d
+  @*       if donly <> 0, only monomials of degree d are returned
+  ASSUME: - basering is a Letterplace ring.
+  @*      - d <= attrib(basering,uptodeg) holds.
+  NOTE: analogous to maxideal(d) in the commutative case
+  "
+{
+  ivL2lpI(ivMaxIdeal(d, donly));
+}
+example {
+  "EXAMPLE:"; echo = 2;
+  ring r = 0,(a,b,c),dp;
+  def R = makeLetterplaceRing(7); setring R;
+  lpMaxIdeal(1,0);
+  lpMaxIdeal(2,0);
+  lpMaxIdeal(2,1);
+  lpMaxIdeal(4,0);
+  lpMaxIdeal(4,1);
+}
+proc monomialBasis(int d, int donly, ideal J)
+  "USAGE: monomialBasis(d, donly, J); d, donly integers, J an ideal
+  RETURN: ideal
+  PURPOSE: computes a list of free monomials in a Letterplace
+  @*       basering R of degree at most d and not contained in <LM(J)>
+  @*       if donly <> 0, only monomials of degree d are returned
+  ASSUME: - basering is a Letterplace ring.
+  @*      - d <= attrib(basering,uptodeg) holds.
+  @*      - J is a Groebner basis
+  "
+{
+  int nv = attrib(basering,"uptodeg");
+  if ((d>nv) || (d<0) )
+  {
+    ERROR("incorrect degree");
+  }
+  nv = attrib(basering,"lV"); // nvars
+  if (d==0)
+  {
+    return(ideal(1));
+  }
+  /* from now on d>=1 */
+  ideal I;
+  if (size(J)==0)
+  {
+    I = lpMaxIdeal(d,donly);
+    if (!donly)
+    {
+      // append 1 as the first element; d>=1
+      I = 1, I;
+    }
+    return( I );
+  }
+  // ok, Sickle misbehaves: have to remove all
+  // elts from J of degree >d
+  ideal JJ;
+  int j; int sj = ncols(J);
+  int cnt=0;
+  for(j=1;j<=sj;j++)
+  {
+    if (deg(J[j]) <= d)
+    {
+      cnt++;
+      JJ[cnt]=lead(J[j]); // only LMs are needed
+    }
+  }
+  if (cnt==0)
+  {
+    // there are no elements in J of degree <= d
+    // return free stuff and the 1
+    I = monomialBasis(d, donly, std(0));
+    if (!donly)
+    {
+      I = 1, I;
+    }
+    return(I);
+  }
+  // from here on, Ibase is not zero
+  ideal Ibase = lpMis2Base(lpSickle(JJ,d)); // the complete K-basis modulo J up to d
+  if (!donly)
+  {
+    // for not donly, give everything back
+    // sort by DP starting with smaller terms
+    Ibase = sort(Ibase,"Dp")[1];
+    return(Ibase);
+  }
+  /* !donly: pick out only monomials of degree d */
+  int i; int si = ncols(Ibase);
+  cnt=0;
+  I=0;
+  for(i=1;i<=si;i++)
+  {
+    if (deg(Ibase[i]) == d)
+    {
+      cnt++;
+      I[cnt]=Ibase[i];
+    }
+  }
+  kill Ibase;
+  return(I);
+}
+example {
+  "EXAMPLE:"; echo = 2;
+  ring r = 0,(x,y),dp;
+  def R = makeLetterplaceRing(7); setring R;
+  ideal J = x(1)*y(2)*x(3) - y(1)*x(2)*y(3);
+  option(redSB); option(redTail);
+  J = letplaceGBasis(J);
+  J;
+  monomialBasis(2,1,std(0));
+  monomialBasis(2,0,std(0));
+  monomialBasis(3,1,J);
+  monomialBasis(3,0,J);
+}
+///////////////////////////////////////////////////////////////////////////////
+/* vl: stuff for conversion to Magma and to SD
+todo: doc, example
+ */
+static proc extractVars(r)
+{
+  int i = 1;
+  int j = 1;
+  string candidate;
+  list result = list();
+  for (i = 1; i<=nvars(r);i++)
+  {
+    candidate = string(var(i))[1,find(string(var(i)),"(")-1];
+    if (!inList(result, candidate))
+    {
+      result = insert(result,candidate,size(result));
+    }
+  }
+  return(result);
+}
+static proc letterPlacePoly2MagmaString(poly h)
+{
+  int pos;
+  string s = string(h);
+  while(find(s,"("))
+  {
+    pos = find(s,"(");
+    while(s[pos]!=")")
+    {
+      s = s[1,pos-1]+s[pos+1,size(s)-pos];
+    }
+    if (size(s)!=pos)
+    {
+      s = s[1,pos-1]+s[pos+1,size(s)-pos]; // The last (")")
+    }
+    else
+    {
+      s = s[1,pos-1];
+    }
+  }
+  return(s);
+}
+static proc letterPlaceIdeal2SD(ideal I, int upToDeg)
+{
+  int i;
+  print("Don't forget to fill in the formal Data in the file");
+  string result = "<?xml version=\"1.0\"?>"+newline+"<FREEALGEBRA createdAt=\"\" createdBy=\"Singular\" id=\"FREEALGEBRA/\">"+newline;
+  result = result + "<vars>"+string(extractVars(basering))+"</vars>"+newline;
+  result = result + "<basis>"+newline;
+  for (i = 1;i<=size(I);i++)
+  {
+    result = result + "<poly>"+letterPlacePoly2MagmaString(I[i])+"</poly>"+newline;
+  }
+  result = result + "</basis>"+newline;
+  result = result + "<uptoDeg>"+ string(upToDeg)+"</uptoDeg>"+newline;
+  result = result + "<Comment></Comment>"+newline;
+  result = result + "<Version></Version>"+newline;
+  result = result + "</FREEALGEBRA>";
+  return(result);
+}
 ///////////////////////////////////////////////////////////////////////////////
 …
   example lp2ivId;
   example lpId2ivLi;
+}
+  example lpSubstitute;
+}
 /*
+  Here are some examples one may try. Just copy them into your console.
+  These are relations for braid groups, up to degree d:
+  LIB "fpadim.lib";
+  ring r = 0,(x,y,z),dp;
+  int d =10; // degree
+  def R = makeLetterplaceRing(d);
+  setring R;
+  ideal I = y(1)*x(2)*y(3) - z(1)*y(2)*z(3), x(1)*y(2)*x(3) - z(1)*x(2)*y(3),
+  z(1)*x(2)*z(3) - y(1)*z(2)*x(3), x(1)*x(2)*x(3) + y(1)*y(2)*y(3) +
+  z(1)*z(2)*z(3) + x(1)*y(2)*z(3);
+  option(prot);
+  option(redSB);option(redTail);option(mem);
+  ideal J = system("freegb",I,d,3);
+  lpDimCheck(J);
+  sickle(J,1,1,1,d);//Computes mistletoes, K-dimension and the Hilbert series
+  LIB "fpadim.lib";
+  ring r = 0,(x,y,z),dp;
+  int d =11; // degree
+  def R = makeLetterplaceRing(d);
+  setring R;
+  ideal I = y(1)*x(2)*y(3) - z(1)*y(2)*z(3), x(1)*y(2)*z(3) - z(1)*x(2)*y(3),
+  z(1)*x(2)*z(3) - y(1)*z(2)*x(3), x(1)*x(2)*x(3) + y(1)*y(2)*y(3) +
+  z(1)*z(2)*z(3) + x(1)*y(2)*z(3);
+  option(prot);
+  option(redSB);option(redTail);option(mem);
+  ideal J = system("freegb",I,d,3);
+  lpDimCheck(J);
+  sickle(J,1,1,1,d);
+  LIB "fpadim.lib";
+  ring r = 0,(x,y,z),dp;
+  int d  = 6; // degree
+  def R  = makeLetterplaceRing(d);
+  setring R;
+  ideal I = y(1)*x(2)*y(3) - z(1)*y(2)*z(3), x(1)*y(2)*x(3) - z(1)*x(2)*y(3),
+  z(1)*x(2)*z(3) - y(1)*z(2)*x(3), x(1)*x(2)*x(3) -2*y(1)*y(2)*y(3) + 3*z(1)*z(2)*z(3) -4*x(1)*y(2)*z(3) + 5*x(1)*z(2)*z(3)- 6*x(1)*y(2)*y(3) +7*x(1)*x(2)*z(3) - 8*x(1)*x(2)*y(3);
+  option(prot);
+  option(redSB);option(redTail);option(mem);
+  ideal J = system("freegb",I,d,3);
+  lpDimCheck(J);
+  sickle(J,1,1,1,d);
+   Here are some examples one may try. Just copy them into your console.
+   These are relations for braid groups, up to degree d:
+   LIB "fpadim.lib";
+   ring r = 0,(x,y,z),dp;
+   int d =10; // degree
+   def R = makeLetterplaceRing(d);
+   setring R;
+   ideal I = y(1)*x(2)*y(3) - z(1)*y(2)*z(3), x(1)*y(2)*x(3) - z(1)*x(2)*y(3),
+   z(1)*x(2)*z(3) - y(1)*z(2)*x(3), x(1)*x(2)*x(3) + y(1)*y(2)*y(3) +
+   z(1)*z(2)*z(3) + x(1)*y(2)*z(3);
+   option(prot);
+   option(redSB);option(redTail);option(mem);
+   ideal J = system("freegb",I,d,3);
+   lpDimCheck(J);
+   sickle(J,1,1,1,d);//Computes mistletoes, K-dimension and the Hilbert series
+   LIB "fpadim.lib";
+   ring r = 0,(x,y,z),dp;
+   int d =11; // degree
+   def R = makeLetterplaceRing(d);
+   setring R;
+   ideal I = y(1)*x(2)*y(3) - z(1)*y(2)*z(3), x(1)*y(2)*z(3) - z(1)*x(2)*y(3),
+   z(1)*x(2)*z(3) - y(1)*z(2)*x(3), x(1)*x(2)*x(3) + y(1)*y(2)*y(3) +
+   z(1)*z(2)*z(3) + x(1)*y(2)*z(3);
+   option(prot);
+   option(redSB);option(redTail);option(mem);
+   ideal J = system("freegb",I,d,3);
+   lpDimCheck(J);
+   sickle(J,1,1,1,d);
+   LIB "fpadim.lib";
+   ring r = 0,(x,y,z),dp;
+   int d  = 6; // degree
+   def R  = makeLetterplaceRing(d);
+   setring R;
+   ideal I = y(1)*x(2)*y(3) - z(1)*y(2)*z(3), x(1)*y(2)*x(3) - z(1)*x(2)*y(3),
+   z(1)*x(2)*z(3) - y(1)*z(2)*x(3), x(1)*x(2)*x(3) -2*y(1)*y(2)*y(3) + 3*z(1)*z(2)*z(3) -4*x(1)*y(2)*z(3) + 5*x(1)*z(2)*z(3)- 6*x(1)*y(2)*y(3) +7*x(1)*x(2)*z(3) - 8*x(1)*x(2)*y(3);
+   option(prot);
+   option(redSB);option(redTail);option(mem);
+   ideal J = system("freegb",I,d,3);
+   lpDimCheck(J);
+   sickle(J,1,1,1,d);
+ */
+/*
+   Here are some examples, which can also be found in [studzins]:
+// takes up to 880Mb of memory
+LIB "fpadim.lib";
+ring r = 0,(x,y,z),dp;
+int d =10; // degree
+def R = makeLetterplaceRing(d);
+setring R;
+ideal I =
+z(1)*z(2)*z(3)*z(4) + y(1)*x(2)*y(3)*x(4) - x(1)*y(2)*y(3)*x(4) - 3*z(1)*y(2)*x(3)*z(4), x(1)*x(2)*x(3) + y(1)*x(2)*y(3) - x(1)*y(2)*x(3), z(1)*y(2)*x(3)-x(1)*y(2)*z(3) + z(1)*x(2)*z(3);
+option(prot);
+option(redSB);option(redTail);option(mem);
+ideal J = system("freegb",I,d,nvars(r));
+lpDimCheck(J);
+sickle(J,1,1,1,d); // dimension is 24872
+LIB "fpadim.lib";
+ring r = 0,(x,y,z),dp;
+int d =10; // degree
+def R = makeLetterplaceRing(d);
+setring R;
+ideal I = x(1)*y(2) + y(1)*z(2), x(1)*x(2) + x(1)*y(2) - y(1)*x(2) - y(1)*y(2);
+option(prot);
+option(redSB);option(redTail);option(mem);
+ideal J = system("freegb",I,d,3);
+lpDimCheck(J);
+sickle(J,1,1,1,d);
+ */
+/*
+   Example for computing GK dimension:
+   returns a ring which contains an ideal I
+   run gkDim(I) inside this ring and it should return 2n (the GK dimension
+   of n-th Weyl algebra including evaluation operators).
+   static proc createWeylEx(int n, int d)
+   "
+   "
+   {
+   int baseringdef;
+   if (defined(basering)) // if a basering is defined, it should be saved for later use
+   {
+   def save = basering;
+   baseringdef = 1;
+   }
+   ring r = 0,(d(1..n),x(1..n),e(1..n)),dp;
+   def R = makeLetterplaceRing(d);
+   setring R;
+   ideal I; int i,j;
+   for (i = 1; i <= n; i++)
+   {
+   for (j = i+1; j<= n; j++)
+   {
+   I[size(I)+1] = lpMult(var(i),var(j));
+   }
+   }
+   for (i = 1; i <= n; i++)
+   {
+   for (j = i+1; j<= n; j++)
+   {
+   I[size(I)+1] = lpMult(var(n+i),var(n+j));
+   }
+   }
+   for (i = 1; i <= n; i++)
+   {
+   for (j = 1; j<= n; j++)
+   {
+   I[size(I)+1] = lpMult(var(i),var(n+j));
+   }
+   }
+   for (i = 1; i <= n; i++)
+   {
+   for (j = 1; j<= n; j++)
+   {
+   I[size(I)+1] = lpMult(var(i),var(2*n+j));
+   }
+   }
+   for (i = 1; i <= n; i++)
+   {
+   for (j = 1; j<= n; j++)
+   {
+   I[size(I)+1] = lpMult(var(2*n+i),var(n+j));
+   }
+   }
+   for (i = 1; i <= n; i++)
+   {
+   for (j = 1; j<= n; j++)
+   {
+   I[size(I)+1] = lpMult(var(2*n+i),var(2*n+j));
+   }
+   }
+   I = simplify(I,2+4);
+   I = letplaceGBasis(I);
+   export(I);
+   if (baseringdef == 1) {setring save;}
+   return(R);
+   }
+proc TestGKAuslander3()
+{
+  ring r = (0,q),(z,x,y),(dp(1),dp(2));
+  def R = makeLetterplaceRing(5); // constructs a Letterplace ring
+  R; setring R; // sets basering to Letterplace ring
+  ideal I;
+  I = q*x(1)*y(2) - y(1)*x(2), z(1)*y(2) - y(1)*z(2), z(1)*x(2) - x(1)*z(2);
+  I = letplaceGBasis(I);
+  lpGkDim(I); // must be 3
+  I = x(1)*y(2)*z(3) - y(1)*x(2), z(1)*y(2) - y(1)*z(2), z(1)*x(2) - x(1)*z(2);//gkDim = 2
+  I = letplaceGBasis(I); // not finite BUT contains a poly in x,y only
+  lpGkDim(I); // must be 4
+  ring r = 0,(y,x,z),dp;
+  def R = makeLetterplaceRing(10); // constructs a Letterplace ring
+  R; setring R; // sets basering to Letterplace ring
+  ideal I;
+  I = x(1)*y(2)*z(3) - y(1)*x(2), z(1)*y(2) - y(1)*z(2), z(1)*x(2) - x(1)*z(2);//gkDim = 2
+  I = letplaceGBasis(I); // computed as it would be homogenized; infinite
+  poly p = x(1)*y(2)*y(3)*x(4)-y(1)*x(2)*x(3)*y(4);
+  lpNF(p, I); // 0 as expected
+  // with inverse of z
+  ring r = 0,(iz,z,x,y),dp;
+  def R = makeLetterplaceRing(11); // constructs a Letterplace ring
+  R; setring R; // sets basering to Letterplace ring
+  ideal I;
+  I = x(1)*y(2)*z(3) - y(1)*x(2), z(1)*y(2) - y(1)*z(2), z(1)*x(2) - x(1)*z(2),
+    iz(1)*y(2) - y(1)*iz(2), iz(1)*x(2) - x(1)*iz(2), iz(1)*z(2)-1, z(1)*iz(2) -1;
+  I = letplaceGBasis(I); //
+  setring r;
+  def R2 = makeLetterplaceRing(23); // constructs a Letterplace ring
+  setring R2; // sets basering to Letterplace ring
+  ideal I = imap(R,I);
+  lpGkDim(I);
+  ring r = 0,(t,z,x,y),(dp(2),dp(2));
+  def R = makeLetterplaceRing(20); // constructs a Letterplace ring
+  R; setring R; // sets basering to Letterplace ring
+  ideal I;
+  I = x(1)*y(2)*z(3) - y(1)*x(2)*t(3), z(1)*y(2) - y(1)*z(2), z(1)*x(2) - x(1)*z(2),
+    t(1)*y(2) - y(1)*t(2), t(1)*x(2) - x(1)*t(2), t(1)*z(2) - z(1)*t(2);//gkDim = 2
+  I = letplaceGBasis(I); // computed as it would be homogenized; infinite
+  LIB "elim.lib";
+  ideal Inoz = nselect(I,intvec(2,6,10,14,18,22,26,30));
+  for(int i=1; i<=20; i++)
+  {
+    Inoz=subst(Inoz,t(i),1);
+  }
+  ideal J = x(1)*y(2)*y(3)*x(4)-y(1)*x(2)*x(3)*y(4);
+  J = letplaceGBasis(J);
+  poly p = x(1)*y(2)*y(3)*x(4)-y(1)*x(2)*x(3)*y(4);
+  lpNF(p, I); // 0 as expected
+  ring r2 = 0,(x,y),dp;
+  def R2 = makeLetterplaceRing(50); // constructs a Letterplace ring
+  setring R2;
+  ideal J = x(1)*y(2)*y(3)*x(4)-y(1)*x(2)*x(3)*y(4);
+  J = letplaceGBasis(J);
+}
 */
+/*
+  Here are some examples, which can also be found in [studzins]:
+  // takes up to 880Mb of memory
+  LIB "fpadim.lib";
+  ring r = 0,(x,y,z),dp;
+  int d =10; // degree
+  def R = makeLetterplaceRing(d);
+  setring R;
+  ideal I =
+  z(1)*z(2)*z(3)*z(4) + y(1)*x(2)*y(3)*x(4) - x(1)*y(2)*y(3)*x(4) - 3*z(1)*y(2)*x(3)*z(4), x(1)*x(2)*x(3) + y(1)*x(2)*y(3) - x(1)*y(2)*x(3), z(1)*y(2)*x(3)-x(1)*y(2)*z(3) + z(1)*x(2)*z(3);
+  option(prot);
+  option(redSB);option(redTail);option(mem);
+  ideal J = system("freegb",I,d,nvars(r));
+  lpDimCheck(J);
+  sickle(J,1,1,1,d); // dimension is 24872
+  LIB "fpadim.lib";
+  ring r = 0,(x,y,z),dp;
+  int d =10; // degree
+  def R = makeLetterplaceRing(d);
+  setring R;
+  ideal I = x(1)*y(2) + y(1)*z(2), x(1)*x(2) + x(1)*y(2) - y(1)*x(2) - y(1)*y(2);
+  option(prot);
+  option(redSB);option(redTail);option(mem);
+  ideal J = system("freegb",I,d,3);
+  lpDimCheck(J);
+  sickle(J,1,1,1,d);
+*/
+/*   actual work:
+// downup algebra A
+LIB "fpadim.lib";
+ring r = (0,a,b,g),(x,y),Dp;
+def R = makeLetterplaceRing(6); // constructs a Letterplace ring
+setring R;
+poly F1 = g*x(1);
+poly F2 = g*y(1);
+ideal J = x(1)*x(2)*y(3)-a*x(1)*y(2)*x(3) - b*y(1)*x(2)*x(3) - F1,
+x(1)*y(2)*y(3)-a*y(1)*x(2)*y(3) - b*y(1)*y(2)*x(3) - F2;
+J = letplaceGBasis(J);
+lpGkDim(J); // 3 == correct
+// downup algebra B
+LIB "fpadim.lib";
+ring r = (0,a,b,g, p(1..7),q(1..7)),(x,y),Dp;
+def R = makeLetterplaceRing(6); // constructs a Letterplace ring
+setring R;
+ideal imn = 1, y(1)*y(2)*y(3), x(1)*y(2), y(1)*x(2), x(1)*x(2), y(1)*y(2), x(1), y(1);
+int i;
+poly F1, F2;
+for(i=1;i<=7;i++)
+{
+F1 = F1 + p(i)*imn[i];
+F2 = F2 + q(i)*imn[i];
+}
+ideal J = x(1)*x(2)*y(3)-a*x(1)*y(2)*x(3) - b*y(1)*x(2)*x(3) - F1,
+x(1)*y(2)*y(3)-a*y(1)*x(2)*y(3) - b*y(1)*y(2)*x(3) - F2;
+J = letplaceGBasis(J);
+lpGkDim(J); // 3 == correct
+ */

Singular/LIB/freegb.lib

-                      r179aaba
+                      r578051
 category="Noncommutative";
 info="
+LIBRARY: freegb.lib   Compute two-sided Groebner bases in free algebras via
+@*                    letterplace
+LIBRARY: freegb.lib   Compute two-sided Groebner bases in free algebras via letterplace approach
 AUTHORS: Viktor Levandovskyy,     viktor.levandovskyy@math.rwth-aachen.de
 @*       Grischa Studzinski,      grischa.studzinski@math.rwth-aachen.de
 OVERVIEW: For the theory, see chapter 'Letterplace' in the Singular Manual
+       Grischa Studzinski,      grischa.studzinski@math.rwth-aachen.de
+OVERVIEW: For the theory, see chapter 'Letterplace' in the @sc{Singular} Manual
 PROCEDURES:
+makeLetterplaceRing(d);    creates a ring with d blocks of shifted original
+@*                         variables
+letplaceGBasis(I); computes two-sided Groebner basis of a letterplace ideal I
+@*                 up to a degree bound
+lpNF(f,I);      normal form of f with respect to ideal I
+freeGBasis(L, n);  computes two-sided Groebner basis of an ideal, encoded via
+@*                 list L, up to degree n
+makeLetterplaceRing(d); creates a ring with d blocks of shifted original variables
+letplaceGBasis(I); computes two-sided Groebner basis of a letterplace ideal I up to a degree bound
+lpNF(f,I); two-sided normal form of f with respect to ideal I
 setLetterplaceAttributes(R,d,b); supplies ring R with the letterplace structure
+freeGBasis(L, n);  computes two-sided Groebner basis of an ideal, encoded via list L, up to degree n
 lpMult(f,g);    letterplace multiplication of letterplace polynomials
 shiftPoly(p,i); compute the i-th shift of letterplace polynomial p
 lpPower(f,n);   natural power of a letterplace polynomial
+lp2lstr(K, s);      convert letter-place ideal to a list of modules
+lst2str(L[, n]);   convert a list (of modules) into polynomials in free algebra
+mod2str(M[, n]); convert a module into a polynomial in free algebra
+lieBracket(a,b[, N]);  compute Lie bracket ab-ba of two letterplace polynomials
+lp2lstr(K, s);  convert a letterplace ideal into a list of modules
+lst2str(L[, n]); convert a list (of modules) into polynomials in free algebra via strings
+mod2str(M[, n]); convert a module into a polynomial in free algebra via strings
 vct2str(M[, n]);   convert a vector into a word in free algebra
+lieBracket(a,b[, N]);  compute Lie bracket ab-ba of two letterplace polynomials
+serreRelations(A,z);   compute the homogeneous part of Serre's relations
+@*                     associated to a generalized Cartan matrix A
+fullSerreRelations(A,N,C,P,d); compute the ideal of all Serre's relations
+@*                             associated to a generalized Cartan matrix A
+isVar(p);                   check whether p is a power of a single variable
+serreRelations(A,z); compute the homogeneous part of Serre's relations associated to a generalized Cartan matrix A
+fullSerreRelations(A,N,C,P,d); compute the ideal of all Serre's relations associated to a generalized Cartan matrix A
+isVar(p);              check whether p is a power of a single variable
 ademRelations(i,j);    compute the ideal of Adem relations for i<2j in char 0
 …
+"
+{
   int use_old_mlr = 0;
+  int alternativeVersion = 0;
   if ( size(#)>0 )
+  {
+    if (( typeof(#[1]) == "int" ) || ( typeof(#[1]) == "poly" ) )
+    {
+      poly x = poly(#[1]);
+      if (x!=0)
+      {
+        use_old_mlr = 1;
+      }
+    }
+  }
+  if (use_old_mlr)
+    if (typeof(#[1]) == "int")
+    {
+      alternativeVersion = #[1];
+    }
+  }
+  if (alternativeVersion == 1)
+  {
     def @A = makeLetterplaceRing1(d);
+  }
+  else
+  {
+    def @A = makeLetterplaceRing2(d);
+  else {
+    if (alternativeVersion == 2)
+    {
+      def @A = makeLetterplaceRing2(d);
+    }
+    else {
+      def @A = makeLetterplaceRing4(d);
+    }
+  }
   return(@A);
 …
+}
+static proc makeLetterplaceRing4(int d)
+"USAGE:  makeLetterplaceRing2(d); d an integer
+RETURN:  ring
+PURPOSE: creates a Letterplace ring with a Dp ordering, suitable for
+@* the use of non-homogeneous letterplace
+NOTE: the matrix for the ordering looks as follows: first row is 1,1,...,1
+EXAMPLE: example makeLetterplaceRing2; shows examples
+"
+{
+  // ToDo future: inherit positive weights in the orig ring
+  // complain on nonpositive ones
+  // d = up to degree, will be shifted to d+1
+  if (d<1) {"bad d"; return(0);}
+  int uptodeg = d; int lV = nvars(basering);
+  int ppl = printlevel-voice+2;
+  string err = "";
+  int i,j,s;
+  def save = basering;
+  int D = d-1;
+  list LR  = ringlist(save);
+  list L, tmp, tmp2, tmp3;
+  L[1] = LR[1]; // ground field
+  L[4] = LR[4]; // quotient ideal
+  tmp  = LR[2]; // varnames
+  s = size(LR[2]);
+  for (i=1; i<=D; i++)
+  {
+    for (j=1; j<=s; j++)
+    {
+      tmp[i*s+j] = string(tmp[j])+"("+string(i+1)+")";
+    }
+  }
+  for (i=1; i<=s; i++)
+  {
+    tmp[i] = string(tmp[i])+"("+string(1)+")";
+  }
+  L[2] = tmp;
+  list OrigNames = LR[2];
+  s = size(LR[3]);
+  list ordering;
+  ordering[1] = list("Dp",intvec(1: int(d*lV)));
+  ordering[2] = LR[3][s]; // module ord to place at the very end
+  LR[3] = ordering;
+  L[3] = LR[3];
+  attrib(L,"maxExp",1);
+  def @R = ring(L);
+  def @@R = setLetterplaceAttributes(@R,uptodeg,lV);
+  return (@@R);
+}
+example
+{
+  "EXAMPLE:"; echo = 2;
+  ring r = 0,(x,y,z),(dp(1),dp(2));
+  def A = makeLetterplaceRing2(2);
+  setring A;
+  A;
+  attrib(A,"isLetterplaceRing");
+  attrib(A,"uptodeg");  // degree bound
+  attrib(A,"lV"); // number of variables in the main block
+}
 // P[s;sigma] approach
 static proc makeLetterplaceRing3(int d)
 …
   attrib(A,"lV"); // number of variables in the main block
+}
 /* EXAMPLES:
 …
   if (i>N)
+  {
+    ERROR("The total number of elements in input ideals must not exceed the dimension of the ground ring");
+    string s1="The total number of elements in input ideals";
+    string s2="must not exceed the dimension of the ground ring";
+    ERROR(s1+s2);
+  }
   if (i < N)
 …
 */
+//static
+proc lpMultX(poly f, poly g)
+static proc lpMultX(poly f, poly g)
+{
   /* multiplies two polys in a very general setting correctly */
 …
+}
-// TODO:
 // multiply two letterplace polynomials, lpMult: done
 // reduction/ Normalform? needs kernel stuff
 …
 //@* else there wouldn't be an dvec representation
 //Mainprocedure for the user
+//Main procedure for the user
 proc lpNF(poly p, ideal G)
 …
 being a Letterplace Groebner basis (no check for this will be done)
 NOTE: Strategy: take the smallest monomial wrt ordering for reduction
 @*     For homogenous ideals the shift does not matter
 @*     For non-homogenous ideals the first shift will be the smallest monomial
+-     For homogenous ideals the shift does not matter
+-     For non-homogenous ideals the first shift will be the smallest monomial
 EXAMPLE: example lpNF; shows examples
+"
 …
  G = sort(G)[1];
  list L = makeDVecI(G);
  return(normalize(lpNormalForm1(p,G,L)));
+ return(normalize(lpNormalForm2(p,G,L)));
+}
 example
 …
 RETURN: list of intvecs
 PURPOSE: convert G into a list of intvecs, corresponding to the exponent vector
 @* of the leading monomials of G
+ of the leading monomials of G
+"
 {int i; list L;
 …
  return(L);
+}
 static proc delSupZero(intvec I)
 …
+}
 static proc delSupZeroList(list L)
 "USUAGE:delSupZeroList(L); L a list, containing intvecs
 …
+}
+//the actual normalform procedure, if a user want not to presort the ideal, just make it not static
+//the first normal form procedure, if a user want not to presort the ideal, just make it not static
 static proc lpNormalForm1(poly p, ideal G, list L)
 …
+// new VL; called from lpNF
+static proc lpNormalForm2(poly pp, ideal G, list L)
+"USUAGE:lpNormalForm2(p,G);
+RETURN:poly
+PURPOSE:computation of the normal form of p w.r.t. G
+ASSUME: p is a Letterplace polynomial, G is a set of Letterplace polynomials
+NOTE: Taking the first possible reduction
+"
+{
+ poly one = 1;
+ if ( (pp == 0) || (leadmonom(pp) == one) ) { return(pp); }
+ poly p = pp; poly q;
+ int i; int s; intvec V;
+ while ( (p != 0) && (leadmonom(p) != one) )
+ {
+   //"entered while with p="; p;
+   V = makeDVec(delSupZero(leadexp(p)));
+   i = 0;
+   s = -1;
+   //"look for divisor";
+   while ( (s == -1) && (i<size(L)) )
+   {
+     i = i+1;
+     s = dShiftDiv(V, L[i])[1];
+   }
+ // now, out of here: either i=size(L) and s==-1 => no reduction
+ // otherwise: i<=size(L) and s!= -1 => reduction
+    //"out of divisor search: s="; s; "i="; i;
+    if (s != -1)
+    {
+    //"start reducing with G[i]:";
+      p = lpReduce(p,G[i],s); // lm-reduction
+      //"reduced to p="; p;
+    }
+    else
+    {
+      // ie no lm-reduction possible; proceed with the tail reduction
+      q = p-lead(p);
+      p = lead(p);
+      if (q!=0)
+      {
+        p = p + lpNormalForm2(q,G,L);
+      }
+      return(p);
+    }
+ }
+ // out of while when p==0 or p == const
+ return(p);
+}
 …
 // // interface
 // proc whichshift(poly p, int numvars)
+// static proc whichshift(poly p, int numvars)
 // {
 // // numvars = number of vars of the orig free algebra
 …
 // LIB "qhmoduli.lib";
 // proc polyshift(poly p,  int numvars)
+// static proc polyshift(poly p,  int numvars)
 // {
 //   poly q = p; int i = 0;
 …
   lpMultX(a,b); // seems to work properly
+}
+/* THE FOLLOWING IS UNDER DEVELOPMENT
+// copied following from freegb_wrkcp.lib by Karim Abou Zeid on 07.04.2017:
+// makeLetterplaceRingElim(int d)
+// makeLetterplaceRingNDO(int d)
+// setLetterplaceAttributesElim(def R, int uptodeg, int lV)
+// lpElimIdeal(ideal I)
+// makeLetterplaceRingWt(int d, intvec W)
+static proc makeLetterplaceRingElim(int d)
+"USAGE:  makeLetterplaceRingElim(d); d integers
+RETURN:  ring
+PURPOSE: creates a ring with an elimination ordering
+NOTE: the matrix for the ordering looks as follows: first row is 1,..,0,1,0,..
+@* then 0,1,0,...,0,0,1,0... and so on, lastly its lp
+@* this ordering is only correct if only polys with same shift are compared
+EXAMPLE: example makeLetterplaceRingElim; shows examples
+"
+{
+  // ToDo future: inherit positive weights in the orig ring
+  // complain on nonpositive ones
+  // d = up to degree, will be shifted to d+1
+  if (d<1) {"bad d"; return(0);}
+  int uptodeg = d; int lV = nvars(basering);
+  int ppl = printlevel-voice+2;
+  string err = "";
+  int i,j,s; intvec iV,iVl;
+  def save = basering;
+  int D = d-1;
+  list LR  = ringlist(save);
+  list L, tmp, tmp2, tmp3;
+  L[1] = LR[1]; // ground field
+  L[4] = LR[4]; // quotient ideal
+  tmp  = LR[2]; // varnames
+  s = size(LR[2]);
+  for (i=1; i<=D; i++)
+  {
+    for (j=1; j<=s; j++)
+    {
+      tmp[i*s+j] = string(tmp[j])+"("+string(i+1)+")";
+    }
+  }
+  for (i=1; i<=s; i++)
+  {
+    tmp[i] = string(tmp[i])+"("+string(1)+")";
+  }
+  L[2] = tmp;
+  L[3] = list();
+  list OrigNames = LR[2];
+  s = size(LR[3]);
+  //creation of first block
+  if (s==2)
+  {
+    // not a blockord, 1 block + module ord
+    tmp = LR[3][s]; // module ord
+    for (i = 1; i <= lV;  i++)
+    {
+      iV = (0: lV);
+      iV[i] = 1;
+      iVl = iV;
+      for (j = 1; j <= D; j++)
+       { iVl = iVl,iV; }
+      L[3][i] = list("a",iVl);
+    }
+//    for (i=1; i<=d; i++)
+//    {
+//      LR[3][s-1+i] = LR[3][1];
+//    }
+    //    LR[3][s+D] = tmp;
+    //iV = (1:(d*lV));
+    L[3][lV+1] = list("lp",(1:(d*lV)));
+    L[3][lV+2] = tmp;
+  }
+  else {ERROR("Please set the ordering of basering to dp");}
+//  if (s>2)
+//  {
+//    // there are s-1 blocks
+//    int nb = s-1;
+//    tmp = LR[3][s]; // module ord to place at the very end
+//   tmp2 = LR[3]; tmp2 = tmp2[1..nb];
+//    LR[3][1] = list("a",LTO);
+//    //tmp3[1] = list("a",intvec(1: int(d*lV))); // deg-ord, insert as the 1st
+//    for (i=1; i<=d; i++)
+//    {
+//      tmp3 = tmp3 + tmp2;
+//    }
+//    tmp3 = tmp3 + list(tmp);
+//    LR[3] = tmp3;
+//     for (i=1; i<=d; i++)
+//     {
+//       for (j=1; j<=nb; j++)
+//       {
+//         //        LR[3][i*nb+j+1]= LR[3][j];
+//         LR[3][i*nb+j+1]= tmp2[j];
+//       }
+//     }
+//     //    size(LR[3]);
+//     LR[3][(s-1)*d+2] = tmp;
+//     LR[3] = list("a",intvec(1: int(d*lV))) + LR[3]; // deg-ord, insert as the 1st
+    // remove everything behind nb*(D+1)+1 ?
+    //    tmp = LR[3];
+    //    LR[3] = tmp[1..size(tmp)-1];
+ // }
+ // L[3] = LR[3];
+  def @R = ring(L);
+  //  setring @R;
+  //  int uptodeg = d; int lV = nvars(basering); // were defined before
+  def @@R = setLetterplaceAttributesElim(@R,uptodeg,lV);
+  return (@@R);
+}
+example
+{
+  "EXAMPLE:"; echo = 2;
+  ring r = 0,(x,y,z),lp;
+  def A = makeLetterplaceRingElim(2);
+  setring A;
+  A;
+  attrib(A,"isLetterplaceRing");
+  attrib(A,"uptodeg");  // degree bound
+  attrib(A,"lV"); // number of variables in the main block
+}
+static proc makeLetterplaceRingNDO(int d)
+"USAGE:  makeLetterplaceRingNDO(d); d an integer
+RETURN:  ring
+PURPOSE: creates a ring with a non-degree first ordering, suitable for
+@* the use of non-homogeneous letterplace
+NOTE: the matrix for the ordering looks as follows:
+@*    'd' blocks of shifted original variables
+EXAMPLE: example makeLetterplaceRingNDO; shows examples
+"
+{
+  // ToDo future: inherit positive weights in the orig ring
+  // complain on nonpositive ones
+  // d = up to degree, will be shifted to d+1
+  if (d<1) {"bad d"; return(0);}
+  int uptodeg = d; int lV = nvars(basering);
+  int ppl = printlevel-voice+2;
+  string err = "";
+  int i,j,s;
+  def save = basering;
+  int D = d-1;
+  list LR  = ringlist(save);
+  list L, tmp, tmp2, tmp3;
+  L[1] = LR[1]; // ground field
+  L[4] = LR[4]; // quotient ideal
+  tmp  = LR[2]; // varnames
+  s = size(LR[2]);
+  for (i=1; i<=D; i++)
+  {
+    for (j=1; j<=s; j++)
+    {
+      tmp[i*s+j] = string(tmp[j])+"("+string(i+1)+")";
+    }
+  }
+  for (i=1; i<=s; i++)
+  {
+    tmp[i] = string(tmp[i])+"("+string(1)+")";
+  }
+  L[2] = tmp;
+  list OrigNames = LR[2];
+  // ordering: one 1..1 a above
+  // ordering: d blocks of the ord on r
+  // try to get whether the ord on r is blockord itself
+  // TODO: make L(2) ordering! exponent is maximally 2
+  s = size(LR[3]);
+  if (s==2)
+  {
+    // not a blockord, 1 block + module ord
+    tmp = LR[3][s]; // module ord
+    for (i=1; i<=d; i++)
+    {
+      LR[3][i] = LR[3][1];
+    }
+    //    LR[3][s+D] = tmp;
+    LR[3][d+1] = tmp;
+    //LR[3][1] = list("a",intvec(1: int(d*lV))); // deg-ord not wanted here
+  }
+  if (s>2)
+  {
+    // there are s-1 blocks
+    int nb = s-1;
+    tmp = LR[3][s]; // module ord to place at the very end
+    tmp2 = LR[3]; tmp2 = tmp2[1..nb];
+    //tmp3[1] = list("a",intvec(1: int(d*lV))); // deg-ord not wanted here
+    for (i=1; i<=d; i++)
+    {
+      tmp3 = tmp3 + tmp2;
+    }
+    tmp3 = tmp3 + list(tmp);
+    LR[3] = tmp3;
+//     for (i=1; i<=d; i++)
+//     {
+//       for (j=1; j<=nb; j++)
+//       {
+//         //        LR[3][i*nb+j+1]= LR[3][j];
+//         LR[3][i*nb+j+1]= tmp2[j];
+//       }
+//     }
+//     //    size(LR[3]);
+//     LR[3][(s-1)*d+2] = tmp;
+//     LR[3] = list("a",intvec(1: int(d*lV))) + LR[3]; // deg-ord, insert as the 1st
+    // remove everything behind nb*(D+1)+1 ?
+    //    tmp = LR[3];
+    //    LR[3] = tmp[1..size(tmp)-1];
+  }
+  L[3] = LR[3];
+  def @R = ring(L);
+  //  setring @R;
+  //  int uptodeg = d; int lV = nvars(basering); // were defined before
+  def @@R = setLetterplaceAttributes(@R,uptodeg,lV);
+  return (@@R);
+}
+example
+{
+  "EXAMPLE:"; echo = 2;
+  ring r = 0,(x,y,z),lp;
+  def A = makeLetterplaceRingNDO(2);
+  setring A;
+  A;
+  attrib(A,"isLetterplaceRing");
+  attrib(A,"uptodeg");  // degree bound
+  attrib(A,"lV"); // number of variables in the main block
+}
+static proc setLetterplaceAttributesElim(def R, int uptodeg, int lV)
+"USAGE: setLetterplaceAttributesElim(R, d, b, eV); R a ring, b,d, eV integers
+RETURN: ring with special attributes set
+PURPOSE: sets attributes for a letterplace ring:
+@*      'isLetterplaceRing' = true, 'uptodeg' = d, 'lV' = b, 'eV' = eV, where
+@*      'uptodeg' stands for the degree bound,
+@*      'lV' for the number of variables in the block 0
+@*      'eV' for the number of elimination variables
+NOTE: Activate the resulting ring by using @code{setring}
+"
+{
+  if (uptodeg*lV != nvars(R))
+  {
+    ERROR("uptodeg and lV do not agree on the basering!");
+  }
+    // Set letterplace-specific attributes for the output ring!
+  attrib(R, "uptodeg", uptodeg);
+  attrib(R, "lV", lV);
+  attrib(R, "isLetterplaceRing", 1);
+  attrib(R, "HasElimOrd", 1);
+  return (R);
+}
+example
+{
+  "EXAMPLE:"; echo = 2;
+  ring r = 0,(x(1),y(1),x(2),y(2),x(3),y(3),x(4),y(4)),dp;
+  def R = setLetterplaceAttributesElim(r, 4, 2, 1); setring R;
+  attrib(R,"isLetterplaceRing");
+  lieBracket(x(1),y(1),2);
+}
+static proc lpElimIdeal(ideal I)
+"
+does not work for degree reasons (deg function does not work for lp rings -> newone!)
+"
+{
+  def lpring = attrib(basering,"isLetterplaceRing");
+  def lpEO =  attrib(basering,"HasElimOrd");
+  if ( typeof(lpring)!="int" && typeof(lpEO)!="int")
+  {
+    ERROR("Ring is not a lp-ring with an elimination ordering");
+  }
+  //int nE = attrib(basering, "eV");
+  return(letplaceGBasis(I));
+}
+static proc makeLetterplaceRingWt(int d, intvec W)
+"USAGE:  makeLetterplaceRingWt(d,W); d an integer, W a vector of positive integers
+RETURN:  ring
+PURPOSE: creates a ring with a special ordering, suitable for
+@* the use of non-homogeneous letterplace
+NOTE: the matrix for the ordering looks as follows: first row is W,W,W,...
+@* then there come 'd' blocks of shifted original variables
+EXAMPLE: example makeLetterplaceRing2; shows examples
+"
+{
+  // ToDo future: inherit positive weights in the orig ring
+  // complain on nonpositive ones
+  // d = up to degree, will be shifted to d+1
+  if (d<1) {"bad d"; return(0);}
+  int uptodeg = d; int lV = nvars(basering);
+  //check weightvector
+  if (size(W) <> lV) {"bad weights"; return(0);}
+  int i;
+  for (i = 1; i <= size(W); i++) {if (W[i] < 0) {"bad weights"; return(0);}}
+  intvec Wt = W;
+  for (i = 2; i <= d; i++) {Wt = Wt, W;}
+  kill i;
+  int ppl = printlevel-voice+2;
+  string err = "";
+  int i,j,s;
+  def save = basering;
+  int D = d-1;
+  list LR  = ringlist(save);
+  list L, tmp, tmp2, tmp3;
+  L[1] = LR[1]; // ground field
+  L[4] = LR[4]; // quotient ideal
+  tmp  = LR[2]; // varnames
+  s = size(LR[2]);
+  for (i=1; i<=D; i++)
+  {
+    for (j=1; j<=s; j++)
+    {
+      tmp[i*s+j] = string(tmp[j])+"("+string(i+1)+")";
+    }
+  }
+  for (i=1; i<=s; i++)
+  {
+    tmp[i] = string(tmp[i])+"("+string(1)+")";
+  }
+  L[2] = tmp;
+  list OrigNames = LR[2];
+  // ordering: one 1..1 a above
+  // ordering: d blocks of the ord on r
+  // try to get whether the ord on r is blockord itself
+  // TODO: make L(2) ordering! exponent is maximally 2
+  s = size(LR[3]);
+  if (s==2)
+  {
+    // not a blockord, 1 block + module ord
+    tmp = LR[3][s]; // module ord
+    for (i=1; i<=d; i++)
+    {
+      LR[3][s-1+i] = LR[3][1];
+    }
+    //    LR[3][s+D] = tmp;
+    LR[3][s+1+D] = tmp;
+    LR[3][1] = list("a",Wt); // deg-ord
+  }
+  if (s>2)
+  {
+    // there are s-1 blocks
+    int nb = s-1;
+    tmp = LR[3][s]; // module ord to place at the very end
+    tmp2 = LR[3]; tmp2 = tmp2[1..nb];
+    tmp3[1] = list("a",Wt); // deg-ord, insert as the 1st
+    for (i=1; i<=d; i++)
+    {
+      tmp3 = tmp3 + tmp2;
+    }
+    tmp3 = tmp3 + list(tmp);
+    LR[3] = tmp3;
+  }
+  L[3] = LR[3];
+  def @R = ring(L);
+  //  setring @R;
+  //  int uptodeg = d; int lV = nvars(basering); // were defined before
+  def @@R = setLetterplaceAttributes(@R,uptodeg,lV);
+  return (@@R);
+}
+example
+{
+  "EXAMPLE:"; echo = 2;
+  ring r = 0,(x,y,z),(dp(1),dp(2));
+  def A = makeLetterplaceRingWt(2,intvec(1,2,3));
+  setring A;
+  A;
+  attrib(A,"isLetterplaceRing");
+  attrib(A,"uptodeg");  // degree bound
+  attrib(A,"lV"); // number of variables in the main block
+}
+*/

Singular/LIB/ncfactor.lib

-                      r9b58b3f
+                      r578051
  the nth Weyl algebra, the permutations of this element with the other
  entries will also be computed.
-SEE ALSO: homogfacFirstWeyl
 "{//proc HomogfacNthWeylAll
   int p=printlevel-voice+2;//for dbprint
 …
  - We have n parameters q_1,..., q_n given.
 SEE ALSO: homogfacNthWeyl, homogfacFirstQWeyl, homogfacFirstQWeyl_all
+SEE ALSO: homogfacFirstQWeyl, homogfacFirstQWeyl_all
+"
 {//proc homogfacNthQWeyl_all

Singular/LIB/standard.lib

-                      r9b58b3f
+                      r578051
 @ref{hres};
 @ref{sres};
+@ref{fres};
 @ref{resolution}.
 @c ref
 …
      return(nres(m,i));
+   }
-/* if( attrib(basering, "global") == 1 ) // preparations for s_res usage. in testing!
+   {
-     if (p_opt) { "using s_res";}
-     if( !defined(s_res) )
+     {
-       def @@v=option(get); option(noloadLib); option(noloadProc); LIB( "schreyer.lib" ); // for s_res
-       option(set, @@v); kill @@v;
+     }
-     resolution re = s_res(m,i);
-     if(size(#)>2)
+     {
-       re=minres(re);
+     }
-     return(re);
-   }*/
    if(homog(m)==1)

Singular/dyn_modules/syzextra/singularxx_defs.h

-                      r9b58b3f
+                      r578051
 #endif
-/// For optimizing if-branches
-#ifdef __GNUC__
-#define LIKELY(expression) (__builtin_expect(!!(expression), 1))
-#define UNLIKELY(expression) (__builtin_expect(!!(expression), 0))
-#else
-#define LIKELY(expression) (expression)
-#define UNLIKELY(expression) (expression)
-#endif
 // #include "CSingularTypes.h"

Singular/iparith.cc

-                      r9b58b3f
+                      r578051
   return FALSE;
+}
+static BOOLEAN jjFRES3(leftv res, leftv u, leftv v, leftv w)
+{
+    assumeStdFlag(u);
+    ideal id = (ideal)u->Data();
+    int max_length = (int)(long)v->Data();
+    if (max_length < 0) {
+        WerrorS("length for fres must not be negative");
+        return TRUE;
+    }
+    if (max_length == 0) {
+        max_length = currRing->N+1;
+        if (currRing->qideal != NULL) {
+            Warn("full resolution in a qring may be infinite, "
+                "setting max length to %d", max_length);
+        }
+    }
+    char *method = (char *)w->Data();
+    /* For the moment, only "complete" (default), "frame", or "extended frame"
+     * are allowed. Another useful option would be "linear strand".
+     */
+    if (strcmp(method, "complete") != 0
+            && strcmp(method, "frame") != 0
+            && strcmp(method, "extended frame") != 0) {
+        WerrorS("wrong optional argument for fres");
+    }
+    syStrategy r = syFrank(id, max_length, method);
+    assume(r->fullres != NULL);
+    res->data = (void *)r;
+    return FALSE;
+}
+static BOOLEAN jjFRES(leftv res, leftv u, leftv v)
+{
+    leftv w = (leftv)omAlloc0(sizeof(sleftv));
+    w->rtyp = STRING_CMD;
+    w->data = (char *)"complete";   // default
+    BOOLEAN RES = jjFRES3(res, u, v, w);
+    omFree(w);
+    return RES;
+}
 static BOOLEAN jjFWALK(leftv res, leftv u, leftv v)
+{

Singular/table.h

-                      r9b58b3f
+                      r578051
 ,{D(fglmQuotProc),FGLMQUOT_CMD,   IDEAL_CMD,      IDEAL_CMD,  POLY_CMD, NO_PLURAL |NO_RING}
 ,{D(jjFIND2),     FIND_CMD,       INT_CMD,        STRING_CMD, STRING_CMD, ALLOW_PLURAL |ALLOW_RING}
+,{D(jjFRES),      FRES_CMD,       RESOLUTION_CMD, IDEAL_CMD,  INT_CMD, NO_PLURAL |NO_RING}
+,{D(jjFRES),      FRES_CMD,       RESOLUTION_CMD, MODUL_CMD,  INT_CMD, NO_PLURAL |NO_RING}
 ,{D(jjFWALK),     FWALK_CMD,      IDEAL_CMD,      RING_CMD,   DEF_CMD, NO_PLURAL |NO_RING}
 ,{D(jjGCD_I),     GCD_CMD,        INT_CMD,        INT_CMD,    INT_CMD, ALLOW_PLURAL |ALLOW_RING}
 …
 ,{D(jjELIMIN_HILB),    ELIMINATION_CMD,MODUL_CMD, MODUL_CMD, POLY_CMD, INTVEC_CMD, NO_PLURAL |ALLOW_RING}
 ,{D(jjFIND3),          FIND_CMD,   INT_CMD,    STRING_CMD, STRING_CMD, INT_CMD, ALLOW_PLURAL |ALLOW_RING}
+,{D(jjFRES3),          FRES_CMD,   RESOLUTION_CMD, IDEAL_CMD, INT_CMD, STRING_CMD, NO_PLURAL |NO_RING}
+,{D(jjFRES3),          FRES_CMD,   RESOLUTION_CMD, MODUL_CMD, INT_CMD, STRING_CMD, NO_PLURAL |NO_RING}
 ,{D(jjFWALK3),         FWALK_CMD,  IDEAL_CMD,  RING_CMD,   DEF_CMD,    INT_CMD, NO_PLURAL |ALLOW_RING}
 ,{D(jjHILBERT3),       HILBERT_CMD,INTVEC_CMD, IDEAL_CMD,  INT_CMD,    INTVEC_CMD, ALLOW_PLURAL | ALLOW_RING | NO_ZERODIVISOR}
 …
   { "forif",       0, IF_CMD ,            IF_CMD},
   { "freemodule",  0, FREEMODULE_CMD ,    CMD_1},
+  { "fres",        0, FRES_CMD ,          CMD_23},
   { "frwalk",      0, FWALK_CMD ,         CMD_23},
   { "gen",         0, E_CMD ,             CMD_1},

Singular/tok.h

r9b58b3f	r578051
79	79	FACSTD_CMD,
80	80	FMD_CMD,
	81	FRES_CMD,
81	82	FWALK_CMD,
82	83	FGLM_CMD,

Tst/Long/ok_l.lst

r9b58b3f	r578051
24	24	finvar_l
25	25	finvar2_l
	26	fres_l
26	27	gcd0_l
27	28	gcdp_l

Tst/Short/ok_s.lst

r9b58b3f	r578051
91	91	fermat_gcd_mod_4var
92	92	ffmodstd_s
	93	fres_s
93	94	gcd2test
94	95	gcd3primtest

configure.ac

-                      r9b58b3f
+                      r578051
 AC_PROG_CXXCPP
 AM_PROG_CC_C_O
+AM_PROG_AR
 ### AM_PROG_LEX
 AC_PROG_LN_S
 AC_PROG_INSTALL
-m4_ifdef([AM_PROG_AR], [AM_PROG_AR])
 AC_HEADER_STDC

doc/NEWS.texi

-                      r9b58b3f
+                      r578051
 Can only be used in procedure headings. (@nref{General command syntax}).
 @end itemize
+New command:
+@itemize
+@item @code{fres}: improved version of @code{sres}: computes a (not necessarily minimal) free resolution of the input ideal/module, using Schreyer's algorithm.
+(@nref{fres},@nref{sres}).
+@end itemize
 Extended commands:
 …
 @item Ring::addNvarsTo (@nref{addNvarsTo})
 @item Ring::hasAlgExtensionCoefficient (@nref{hasAlgExtensionCoefficient})
 @item Schreyer::s_res (@nref{s_res})
+@item Schreyer::s_res (@code{s_res})
 @item grobcov.lib (grobcovK) (@nref{grobcov_lib}) with new routines
    AddCons  AddConsP.

kernel/GBEngine/Makefile.am

r9b58b3f	r578051
5	5
6	6	noinst_LTLIBRARIES=libGBEngine.la
7		libGBEngine_la_SOURCES=khstd.cc kstdfac.cc kstd1.cc kstd2.cc kutil.cc nc.cc sca.cc gr_kstd2.cc kspoly.cc kpolys.cc syz.cc syz0.cc syz1.cc syz2.cc syz3.cc units.cc tgb.cc tgbgauss.cc f5data.cc f5lists.cc f5gb.cc f5c.cc ratgring.cc shiftgb.cc ringgb.cc janet.cc
	7	libGBEngine_la_SOURCES=khstd.cc kstdfac.cc kstd1.cc kstd2.cc kutil.cc nc.cc sca.cc gr_kstd2.cc kspoly.cc kpolys.cc syz.cc syz0.cc syz1.cc syz2.cc syz3.cc syz4.cc units.cc tgb.cc tgbgauss.cc f5data.cc f5lists.cc f5gb.cc f5c.cc ratgring.cc shiftgb.cc ringgb.cc janet.cc
8	8
9	9	libGBEngine_la_includedir=$(includedir)/singular/kernel/GBEngine

kernel/GBEngine/kstd2.cc

-                      r9b58b3f
+                      r578051
     /* here in the nonhomog case we shrink the reduced poly AGAIN */
     if ( ! strat->homog)
+    {
       strat->P.GetP(strat->lmBin); // because shifts are counted with .p structure
       /* assume strat->P.t_p != NULL */
       /* in the nonhomog case we have to shrink the polynomial */
       assume(strat->P.t_p!=NULL); // poly qq defined above
       qq = p_Shrink(strat->P.t_p, lV, strat->tailRing); // direct shrink
       if (qq != NULL)
+      {
          /* we're here if Shrink is nonzero */
         //         strat->P.p =  NULL;
         //        strat->P.Delete(); /* deletes P.p and P.t_p */ //error
         strat->P.p   =  NULL; // is not set by Delete
         strat->P.t_p =  qq;
         strat->P.GetP(strat->lmBin);
         // update sev and length
         strat->initEcart(&(strat->P));
         strat->P.sev = pGetShortExpVector(strat->P.p);
+      }
       else
+      {
          /* Shrink is zero, like y(1)*y(2) - y(1)*y(3)*/
+      if ( ! strat->homog)
+      {
+        strat->P.GetP(strat->lmBin); // because shifts are counted with .p structure
+        /* in the nonhomog case we have to shrink the polynomial */
+        if (strat->P.t_p!=NULL)
+        {
+          qq = p_Shrink(strat->P.t_p, lV, strat->tailRing); // direct shrink
+          if (qq != NULL)
+          {
+            /* we're here if Shrink is nonzero */
+            //         strat->P.p =  NULL;
+            //        strat->P.Delete(); /* deletes P.p and P.t_p */ //error
+            strat->P.p   =  NULL; // is not set by Delete
+            strat->P.t_p =  qq;
+            strat->P.GetP(strat->lmBin);
+            // update sev and length
+            strat->initEcart(&(strat->P));
+            strat->P.sev = pGetShortExpVector(strat->P.p);
+          }
+          else
+          {
+            /* Shrink is zero, like y(1)*y(2) - y(1)*y(3)*/
 #ifdef PDEBUG
+         if (TEST_OPT_DEBUG){PrintS("nonzero s shrinks to 0");PrintLn();}
+#endif
+         //         strat->P.Delete();  // cause error
+         strat->P.p = NULL;
+         strat->P.t_p = NULL;
+           //         strat->P.p = NULL; // or delete strat->P.p ?
+         goto     red_shrink2zero;
+       }
+    }
+            if (TEST_OPT_DEBUG){PrintS("nonzero s shrinks to 0");PrintLn();}
+#endif
+            //         strat->P.Delete();  // cause error
+            strat->P.p = NULL;
+            strat->P.t_p = NULL;
+            //         strat->P.p = NULL; // or delete strat->P.p ?
+            goto     red_shrink2zero;
+          }
+        }
+        else
+        {
+          qq = p_Shrink(strat->P.p, lV, currRing); // direct shrink
+          if (qq != NULL)
+          {
+            /* we're here if Shrink is nonzero */
+            strat->P.p   =  qq;
+            strat->P.t_p =  NULL;
+            // update sev and length
+            strat->initEcart(&(strat->P));
+            strat->P.sev = pGetShortExpVector(strat->P.p);
+          }
+          else
+          {
+            /* Shrink is zero, like y(1)*y(2) - y(1)*y(3)*/
+#ifdef PDEBUG
+            if (TEST_OPT_DEBUG){PrintS("nonzero s shrinks to 0");PrintLn();}
+#endif
+            //         strat->P.Delete();  // cause error
+            strat->P.p = NULL;
+            strat->P.t_p = NULL;
+            //         strat->P.p = NULL; // or delete strat->P.p ?
+            goto     red_shrink2zero;
+          }
+        }
+      }
       /* end shrinking poly AGAIN in the nonhomog case */
 …
       //      enterpairsShift(vw,strat->sl,strat->P.ecart,pos,strat, strat->tl,uptodeg,lV);
       // posInS only depends on the leading term
+      if ((strat->P.t_p!=NULL)&&(currRing!=strat->tailRing))
+      {
+        // move to currRing:
+        // need tp save t_p, as it is in also in T
+        pNext(strat->P.p)=strat->p_shallow_copy_delete(
+                            p_Copy(pNext(strat->P.p),strat->tailRing),
+                            strat->tailRing, currRing,
+                            currRing->PolyBin);
+        strat->P.t_p=NULL;
+      }
       strat->enterS(strat->P, pos, strat, atR);

kernel/GBEngine/kutil.cc

-                      r9b58b3f
+                      r578051
   /*- save result -*/
+  p_Test(p.p,currRing);
   strat->S[atS] = p.p;
   if (strat->honey) strat->ecartS[atS] = p.ecart;
 …
     qq.p    = NULL;
     qq.max_exp  = NULL;
+    qq.t_p = p_LPshift(p_Copy(p.t_p,strat->tailRing), i, uptodeg, lV, strat->tailRing); // direct shift
+    if (p.t_p!=NULL)
+      qq.t_p = p_LPshift(p_Copy(p.t_p,strat->tailRing), i, uptodeg, lV, strat->tailRing); // direct shift
+    else
+      qq.p = p_LPshift(p_Copy(p.p,currRing), i, uptodeg, lV, currRing); // direct shift
     qq.GetP();
     // update q.sev
     qq.sev = pGetShortExpVector(qq.p);
+    #ifdef KTEST
+    kTest_T(&qq, strat->tailRing, -1, 'L');
+    #endif
     /* enter it into T, first el't is with the shift 0 */
     // compute the position for qq

kernel/GBEngine/syz.h

r9b58b3f	r578051
99	99	syStrategy syKosz(ideal arg,int * length);
100	100
	101	syStrategy syFrank(const ideal arg, const int length, const char *method);
	102
101	103	void syKillComputation(syStrategy syzstr, ring r=currRing);
102	104	intvec * syBettiOfComputation(syStrategy syzstr, BOOLEAN minim=TRUE,int * row_shift=NULL, intvec *weights=NULL);

kernel/GBEngine/tgb_internal.h

-                      r9b58b3f
+                      r578051
+}
 */
-#ifdef __GNUC__
-#define LIKELY(expression) (__builtin_expect(!!(expression), 1))
-#define UNLIKELY(expression) (__builtin_expect(!!(expression), 0))
-#else
-#define LIKELY(expression) (expression)
-#define UNLIKELY(expression) (expression)
-#endif
 template<class number_type> SparseRow<number_type>* convert_to_sparse_row(number_type* temp_array,int temp_size,int non_zeros){

libpolys/misc/auxiliary.h

-                      r9b58b3f
+                      r578051
+#ifdef __GNUC__
+#define likely(X)   (__builtin_expect(!!(X), 1))
+#define unlikely(X) (__builtin_expect(!!(X), 0))
+#else
+#define likely(X)   (X)
+#define unlikely(X) (X)
+#endif
+#define LIKELY   likely
+#define UNLIKELY unlikely
 #endif

libpolys/polys/monomials/p_polys.h

-                      r9b58b3f
+                      r578051
   ev[0] = p_GetComp(p, r);
+}
 static inline void p_GetExpVL(poly p, long *ev, const ring r)
+static inline void p_GetExpVL(poly p, int64 *ev, const ring r)
+{
   p_LmCheckPolyRing1(p, r);
 …
+}
 static inline void p_SetExpV(poly p, int *ev, const ring r)
+{
+  p_LmCheckPolyRing1(p, r);
+  for (unsigned j = r->N; j!=0; j--)
+      p_SetExp(p, j, ev[j], r);
+  if(ev[0]!=0) p_SetComp(p, ev[0],r);
+  p_Setm(p, r);
+}
+static inline void p_SetExpVL(poly p, int64 *ev, const ring r)
+{
   p_LmCheckPolyRing1(p, r);

omalloc/configure.ac

-                      r9b58b3f
+                      r578051
 AC_PROG_CC
 AC_PROG_CXX
+AM_PROG_AR
 SING_RESET_FLAGS()
 …
 AM_INIT_AUTOMAKE([-Wall foreign subdir-objects]) # -Wno-extra-portability -Werror silent-rules
 m4_ifdef([AM_SILENT_RULES], [AM_SILENT_RULES([yes])])
-m4_ifdef([AM_PROG_AR], [AM_PROG_AR])
 AM_SANITY_CHECK
 …
 AC_PROG_INSTALL
 AM_PROG_CC_C_O
-# AM_PROG_AR
 AC_C_CONST
 AC_C_INLINE

resources/configure.ac

-                      r9b58b3f
+                      r578051
 AX_PREFIX_CONFIG_H([singular_resourcesconfig.h],[],[_config.h])
+AM_PROG_AR
 SING_RESET_FLAGS()
 SING_CHECK_SET_ARGS()
 AM_PROG_CC_C_O
-# AM_PROG_AR
 AC_PROG_LN_S

Context Navigation

Changeset 578051 in git

Legend:

Singular/LIB/fpadim.lib

Singular/LIB/freegb.lib

Singular/LIB/ncfactor.lib

Singular/LIB/standard.lib

Singular/dyn_modules/syzextra/singularxx_defs.h

Singular/iparith.cc

Singular/table.h

Singular/tok.h

Tst/Long/ok_l.lst

Tst/Short/ok_s.lst

configure.ac

doc/NEWS.texi

kernel/GBEngine/Makefile.am

kernel/GBEngine/kstd2.cc

kernel/GBEngine/kutil.cc

kernel/GBEngine/syz.h

kernel/GBEngine/tgb_internal.h

libpolys/misc/auxiliary.h

libpolys/polys/monomials/p_polys.h

omalloc/configure.ac

resources/configure.ac

Download in other formats: