Changeset 5a8e35 in git


Ignore:
Timestamp:
Nov 15, 2018, 11:34:44 AM (5 years ago)
Author:
Hans Schoenemann <hannes@…>
Branches:
(u'fieker-DuVal', '117eb8c30fc9e991c4decca4832b1d19036c4c65')(u'spielwiese', 'd08f5f0bb3329b8ca19f23b74cb1473686415c3a')
Children:
9fd2bddf4dd0f11563a18ff45c897ab26f54f71a
Parents:
4aa50a694d58bf7ccd9553bb5644b3297c61b6088a7dbe20b15936e15424c94142c26c51a9c98f44
git-author:
Hans Schoenemann <hannes@mathematik.uni-kl.de>2018-11-15 11:34:44+01:00
git-committer:
GitHub <noreply@github.com>2018-11-15 11:34:44+01:00
Message:
Merge pull request #892 from kabouzeid/lp-kernel

Much faster GK dim and Ufnarovski graph, also various other fixes
Files:
6 edited

Legend:

Unmodified
Added
Removed

  • Singular/LIB/fpadim.lib

    r4aa50a r5a8e35  
    7777";
    7878
    79 // Remark Oct 2018: iv2lp, lp2iv etc are NOT IN HEADER because
    80 // they should not be used anymore
    81 
    8279LIB "freegb.lib"; //for letterplace rings
    8380LIB "general.lib";//for sorting mistletoes
    … …  
    113110  example lpSickleDim;
    114111  example sickle;
    115   example ivL2lpI;
    116   example iv2lp;
    117   example iv2lpList;
    118   example iv2lpMat;
    119   example lp2iv;
    120   example lp2ivId;
    121   example lpId2ivLi;
    122112  example lpMonomialBasis;
    123113}
    … …  
    902892  if (IP == P) {return(1);}
    903893  else {return(0);}
    904 }
    905 
    906 proc ivL2lpI(list L)
    907 "USAGE: ivL2lpI(L); L a list of intvecs (deprecated, will be removed soon)
    908 RETURN: ideal
    909 PURPOSE:Transforming a list of intvecs into an ideal of Letterplace monomials
    910 ASSUME: - Intvec corresponds to a Letterplace monomial
    911 @*      - basering has to be a Letterplace ring
    912 NOTE:   - Assumptions will not be checked!
    913 EXAMPLE: example ivL2lpI; shows examples
    914 "
    915 {
    916   int i; ideal G;
    917   poly p;
    918   for (i = 1; i <= size(L); i++)
    919   {p = iv2lp(L[i]);
    920     G[(size(G) + 1)] = p;
    921   }
    922   return(G);
    923 }
    924 example
    925 {
    926   "EXAMPLE:"; echo = 2;
    927   ring r = 0,(x,y,z),dp;
    928   def R = makeLetterplaceRing(5);// constructs a Letterplace ring
    929   setring R; //sets basering to Letterplace ring
    930   intvec u = 1,1,2; intvec v = 2,1,3; intvec w = 3,1,1;
    931   // u = x^2y, v = yxz, w = zx^2 in intvec representation
    932   list L = u,v,w;
    933   ivL2lpI(L);// invokes the procedure, returns the ideal containing u,v,w
    934 }
    935 
    936 proc iv2lp(intvec I)
    937 "USAGE: iv2lp(I); I an intvec (deprecated, will be removed soon)
    938 RETURN: poly
    939 PURPOSE:Transforming an intvec into the corresponding Letterplace polynomial
    940 ASSUME: - Intvec corresponds to a Letterplace monomial
    941 @*      - basering has to be a Letterplace ring
    942 NOTE:   - Assumptions will not be checked!
    943 EXAMPLE: example iv2lp; shows examples
    944 "
    945 {if (I[1] == 0) {return(1);}
    946   int i = size(I);
    947   if (i > attrib(basering,"uptodeg")) {ERROR("polynomial exceeds degreebound");}
    948   int j; poly p = 1;
    949   for (j = 1; j <= i; j++) {if (I[j] > 0) { p = p*var(I[j]);}} //ignore zeroes, because they correspond to 1
    950   return(p);
    951 }
    952 example
    953 {
    954   "EXAMPLE:"; echo = 2;
    955   ring r = 0,(x,y,z),dp;
    956   def R = makeLetterplaceRing(5); // constructs a Letterplace ring
    957   setring R; //sets basering to Letterplace ring
    958   // u = x^2y, v = yxz, w = zx^2 in intvec representation
    959   intvec u = 1,1,2;
    960   iv2lp(u); // invokes the procedure and returns the corresponding poly
    961   intvec v = 2,1,3;
    962   iv2lp(v);
    963   intvec w = 3,1,1;
    964   iv2lp(w);
    965 }
    966 
    967 proc iv2lpList(list L)
    968 "USAGE: iv2lpList(L); L a list of intmats (deprecated, will be removed soon)
    969 RETURN: ideal
    970 PURPOSE:Converting a list of intmats into an ideal of corresponding monomials
    971 ASSUME: - The rows of each intmat in L must correspond to a Letterplace monomial
    972 @*      - basering has to be a Letterplace ring
    973 EXAMPLE: example iv2lpList; shows examples
    974 "
    975 {checkAssumptions(0,L);
    976   ideal G;
    977   int i;
    978   for (i = 1; i <= size(L); i++){G = G + iv2lpMat(L[i]);}
    979   return(G);
    980 }
    981 example
    982 {
    983   "EXAMPLE:"; echo = 2;
    984   ring r = 0,(x,y,z),dp;
    985   def R = makeLetterplaceRing(5); // constructs a Letterplace ring
    986   setring R; // sets basering to Letterplace ring
    987   intmat u[3][1] = 1,1,2; intmat v[1][3] = 2,1,3; intmat w[2][3] = 3,1,1,2,3,1;
    988   // defines intmats of different size containing intvec representations of
    989   // monomials as rows
    990   list L = u,v,w;
    991   print(u); print(v); print(w); // shows the intmats contained in L
    992   iv2lpList(L); // returns the corresponding monomials as an ideal
    993 }
    994 
    995 
    996 proc iv2lpMat(intmat M)
    997 "USAGE: iv2lpMat(M); M an intmat (deprecated, will be removed soon)
    998 RETURN: ideal
    999 PURPOSE:Converting an intmat into an ideal of the corresponding monomials
    1000 ASSUME: - The rows of M must correspond to Letterplace monomials
    1001 @*      - basering has to be a Letterplace ring
    1002 EXAMPLE: example iv2lpMat; shows examples
    1003 "
    1004 {list L = M;
    1005   checkAssumptions(0,L);
    1006   kill L;
    1007   ideal G; poly p;
    1008   int i; intvec I;
    1009   for (i = 1; i <= nrows(M); i++)
    1010   { I = M[i,1..ncols(M)];
    1011     p = iv2lp(I);
    1012     G[size(G)+1] = p;
    1013   }
    1014   return(G);
    1015 }
    1016 example
    1017 {
    1018   "EXAMPLE:"; echo = 2;
    1019   ring r = 0,(x,y,z),dp;
    1020   def R = makeLetterplaceRing(5); // constructs a Letterplace ring
    1021   setring R; // sets basering to Letterplace ring
    1022   intmat u[3][1] = 1,1,2; intmat v[1][3] = 2,1,3; intmat w[2][3] = 3,1,1,2,3,1;
    1023   // defines intmats of different size containing intvec representations of
    1024   // monomials as rows
    1025   iv2lpMat(u); // returns the monomials contained in u
    1026   iv2lpMat(v); // returns the monomials contained in v
    1027   iv2lpMat(w); // returns the monomials contained in w
    1028 }
    1029 
    1030 proc lpId2ivLi(ideal G)
    1031 "USAGE: lpId2ivLi(G); G an ideal (deprecated, will be removed soon)
    1032 RETURN: list
    1033 PURPOSE:Transforming an ideal into the corresponding list of intvecs
    1034 ASSUME: - basering has to be a Letterplace ring
    1035 EXAMPLE: example lpId2ivLi; shows examples
    1036 "
    1037 {
    1038   int i,j,k;
    1039   list M;
    1040   checkAssumptions(0,M);
    1041   for (i = 1; i <= size(G); i++) {M[i] = lp2iv(G[i]);}
    1042   return(M);
    1043 }
    1044 example
    1045 {
    1046   "EXAMPLE:"; echo = 2;
    1047   ring r = 0,(x,y),dp;
    1048   def R = makeLetterplaceRing(5); // constructs a Letterplace ring
    1049   setring R; // sets basering to Letterplace ring
    1050   ideal L = x*x,y*y,x*y*x;
    1051   lpId2ivLi(L); // returns the corresponding intvecs as a list
    1052 }
    1053 
    1054 proc lp2iv(poly p)
    1055 "USAGE: lp2iv(p); p a poly (deprecated, will be removed soon)
    1056 RETURN: intvec
    1057 PURPOSE: Transforming a monomial into the corresponding intvec
    1058 ASSUME: - basering has to be a Letterplace ring
    1059 NOTE:   - Assumptions will not be checked!
    1060 EXAMPLE: example lp2iv; shows examples
    1061 "
    1062 {p = normalize(lead(p));
    1063   intvec I;
    1064   int i,j;
    1065   if (deg(p) > attrib(basering,"uptodeg")) {ERROR("Monomial exceeds degreebound");}
    1066   if (p == 1) {return(I);}
    1067   if (p == 0) {ERROR("Monomial is not allowed to equal zero");}
    1068   intvec lep = leadexp(p);
    1069   for ( i = 1; i <= attrib(basering,"isLetterplaceRing"); i++) {if (lep[i] == 1) {I = i; break;}}
    1070   for (i = (attrib(basering,"isLetterplaceRing")+1); i <= size(lep); i++)
    1071   {if (lep[i] == 1)
    1072     { j = (i mod attrib(basering,"isLetterplaceRing"));
    1073       if (j == 0) {I = I,attrib(basering,"isLetterplaceRing");}
    1074       else {I = I,j;}
    1075     }
    1076     else { if (lep[i] > 1) {ERROR("monomial has a not allowed multidegree");}}
    1077   }
    1078   if (I[1] == 0) {ERROR("monomial has a not allowed multidegree");}
    1079   return(I);
    1080 }
    1081 example
    1082 {
    1083   "EXAMPLE:"; echo = 2;
    1084   ring r = 0,(x,y,z),dp;
    1085   def R = makeLetterplaceRing(5); // constructs a Letterplace ring
    1086   setring R; // sets basering to Letterplace ring
    1087   poly p = x*x*z;
    1088   lp2iv(p); // transforms p into the intvec representation
    1089   lp2iv(y*y*x*x);
    1090   lp2iv(z*y*x*z*z);
    1091 }
    1092 
    1093 proc lp2ivId(ideal G)
    1094 "USAGE: lp2ivId(G); G an ideal (deprecated, will be removed soon)
    1095 RETURN: list
    1096 PURPOSE:Converting an ideal into an list of intmats,
    1097 @*      the corresponding intvecs forming the rows
    1098 ASSUME: - basering has to be a Letterplace ring
    1099 EXAMPLE: example lp2ivId; shows examples
    1100 "
    1101 {G = normalize(lead(G));
    1102   intvec I; list L;
    1103   checkAssumptions(0,L);
    1104   int i,md;
    1105   for (i = 1; i <= size(G); i++) { if (md <= deg(G[i])) {md = deg(G[i]);}}
    1106   while (size(G) > 0)
    1107   {ideal Gt;
    1108     for (i = 1; i <= ncols(G); i++) {if (md == deg(G[i])) {Gt = Gt + G[i]; G[i] = 0;}}
    1109     if (size(Gt) > 0)
    1110     {G = simplify(G,2);
    1111       intmat M [size(Gt)][md];
    1112       for (i = 1; i <= size(Gt); i++) {M[i,1..md] = lp2iv(Gt[i]);}
    1113       L = insert(L,M);
    1114       kill M; kill Gt;
    1115       md = md - 1;
    1116     }
    1117     else {kill Gt; md = md - 1;}
    1118   }
    1119   return(L);
    1120 }
    1121 example
    1122 {
    1123   "EXAMPLE:"; echo = 2;
    1124   ring r = 0,(x,y,z),dp;
    1125   def R = makeLetterplaceRing(5); // constructs a Letterplace ring
    1126   setring R; // sets basering to Letterplace ring
    1127   poly p = x*x*z;
    1128   poly q = y*y*x*x;
    1129   poly w = z*y*x*z;
    1130   // p,q,w are some polynomials we want to transform into their
    1131   // intvec representation
    1132   ideal G = p,q,w;
    1133   lp2ivId(G); // returns the list of intmats for this ideal
    1134894}
    1135895
    … …  
    23642124@*      - d <= attrib(basering,uptodeg) holds.
    23652125@*      - J is a Groebner basis
    2366 "
    2367 {
    2368   int nv = attrib(basering,"uptodeg");
    2369   if ((d>nv) || (d<0) )
    2370   {
    2371     ERROR("incorrect degree");
    2372   }
    2373   nv = attrib(basering,"isLetterplaceRing"); // nvars
    2374   if (d==0)
    2375   {
    2376     return(ideal(1));
    2377   }
    2378   /* from now on d>=1 */
    2379   ideal I;
    2380   if (size(J)==0)
    2381   {
    2382     I = maxideal(d);
    2383     if (!donly)
    2384     {
    2385       for (int i = d-1; i >= 0; i--)
    2386       {
    2387         I = maxideal(i), I;
    2388       } kill i;
    2389     }
    2390     return(I);
    2391   }
    2392   // ok, Sickle misbehaves: have to remove all
    2393   // elts from J of degree >d
    2394   ideal JJ;
    2395   int j; int sj = ncols(J);
    2396   int cnt=0;
    2397   for(j=1;j<=sj;j++)
    2398   {
    2399     if (deg(J[j]) <= d)
    2400     {
    2401       cnt++;
    2402       JJ[cnt]=lead(J[j]); // only LMs are needed
    2403     }
    2404   }
    2405   if (cnt==0)
    2406   {
    2407     // there are no elements in J of degree <= d
    2408     // return free stuff and the 1
    2409     I = lpMonomialBasis(d, donly, ideal(0));
    2410     if (!donly)
    2411     {
    2412       I = 1, I;
    2413     }
    2414     return(I);
    2415   }
    2416   // from here on, Ibase is not zero
    2417   ideal Ibase = lpMis2Base(lpSickle(JJ,d)); // the complete K-basis modulo J up to d
    2418   if (!donly)
    2419   {
    2420     // for not donly, give everything back
    2421     Ibase = sort(Ibase)[1];
    2422     return(Ibase);
    2423   }
    2424   /* !donly: pick out only monomials of degree d */
    2425   int i; int si = ncols(Ibase);
    2426   cnt=0;
    2427   I=0;
    2428   for(i=1;i<=si;i++)
    2429   {
    2430     if (deg(Ibase[i]) == d)
    2431     {
    2432       cnt++;
    2433       I[cnt]=Ibase[i];
    2434     }
    2435   }
    2436   kill Ibase;
    2437   return(I);
     2126NOTE: will be replaced with reduce(maxideal(d), J); soon
     2127"
     2128{
     2129  if (d < 0) {
     2130    return (delete(ideal(0), 1)); // no monomials
     2131  }
     2132  ideal I = maxideal(d);
     2133  if (!donly) {
     2134    for (int i = d-1; i >= 0; i--) {
     2135      I = maxideal(i), I;
     2136    } kill i;
     2137  }
     2138  for (int i = ncols(I); i >= 1; i--) {
     2139    if (lpLmDivides(J, I[i])) {
     2140      I = delete(I, i);
     2141    }
     2142  } kill i;
     2143  return (I);
    24382144}
    24392145example

  • Singular/LIB/fpaprops.lib

    r4aa50a r5a8e35  
    622622  // iterate through all vertices
    623623
    624   intvec visited;
    625   visited[n] = 0;
    626 
    627   intvec cyclic;
    628   cyclic[n] = 0;
     624  intvec visited = 0:n;
     625  intvec cyclic = 0:n;
     626  intvec countedCycles = -2:n;
    629627
    630628  int maxCycleCount = 0;
    631629  for (int v = 1; v <= n; v++) {
    632     int cycleCount = countCycles(UG, v, visited, cyclic, 0);
    633     if (cycleCount == -1) {
     630    countedCycles = countCycles(UG, v, visited, cyclic, 0, countedCycles);
     631    dbprint("counted " + string(countedCycles[v]) + " cycles from vertex " + string(v) + "/" + string(n) + " (cache: " + string(countedCycles) + ")");
     632    if (countedCycles[v] == -1) {
    634633      return(-1);
    635634    }
    636     if (cycleCount > maxCycleCount) {
    637       maxCycleCount = cycleCount;
    638     }
    639     kill cycleCount;
     635    if (countedCycles[v] > maxCycleCount) {
     636      maxCycleCount = countedCycles[v];
     637    }
    640638  } kill v;
    641   return(maxCycleCount);
    642 }
    643 
    644 static proc countCycles(intmat G, int v, intvec visited, intvec cyclic, intvec path)
     639  return (maxCycleCount);
     640}
     641
     642static proc countCycles(intmat G, int v, intvec visited, intvec cyclic, intvec path, intvec countedCycles)
    645643"USAGE: countCycles(G, v, visited, cyclic, path); G a Graph, v the vertex to
    646644start. The parameter visited, cyclic and path should be 0.
    … …  
    651649"
    652650{
     651  if (countedCycles[v] > -2) {
     652    return (countedCycles);
     653  }
    653654  // Mark the current vertex as visited
    654655  visited[v] = 1;
    … …  
    669670          if(cyclic[path[j]] == 1) {
    670671            // 1.1 if yes, return -1
    671             return (-1);
     672            countedCycles[v] = -1;
     673            return (countedCycles);
    672674          }
    673675          if (path[j] == w) {
    … …  
    694696        int maxCycleCount = 0;
    695697        for (int j = size(path); j >= 1; j--) {
    696           int cycleCount = countCycles(G, path[j], visited, cyclic, path);
    697           if(cycleCount == -1) {
    698             return (-1);
     698          countedCycles = countCycles(G, path[j], visited, cyclic, path, countedCycles);
     699          if(countedCycles[path[j]] == -1) {
     700            countedCycles[v] = -1;
     701            return (countedCycles);
    699702          }
    700           if (cycleCount > maxCycleCount) {
    701             maxCycleCount = cycleCount;
     703          if (countedCycles[path[j]] > maxCycleCount) {
     704            maxCycleCount = countedCycles[path[j]];
    702705          }
    703           kill cycleCount;
    704706          if (path[j] == w) {
    705707            break;
    … …  
    711713        kill maxCycleCount;
    712714      } else {
    713         int cycleCount = countCycles(G, w, visited, cyclic, path);
    714         if (cycleCount == -1) {
    715           return(-1);
    716         }
    717         if (cycleCount > cycles) {
    718           cycles = cycleCount;
    719         }
    720         kill cycleCount;
     715        countedCycles = countCycles(G, w, visited, cyclic, path, countedCycles);
     716        if (countedCycles[w] == -1) {
     717          countedCycles[v] = -1;
     718          return (countedCycles);
     719        }
     720        if (countedCycles[w] > cycles) {
     721          cycles = countedCycles[w];
     722        }
    721723      }
    722724    }
    723725  } kill w;
    724   // printf("Path: %s countCycles: %s", path, cycles); // DEBUG
    725   return(cycles);
     726  countedCycles[v] = cycles;
     727  return (countedCycles);
    726728}
    727729
    … …  
    738740"
    739741{
     742  dbprint("computing maxDeg");
    740743  int l = maxDeg(G);
    741   list LG = lpId2ivLi(G);
    742   list SW = ivStandardWords(LG, l - 1); // vertices
    743   int n = size(SW);
     744  if (l - 1 == 0) {
     745    // TODO: how should the graph look like when l - 1 = 0 ?
     746    ERROR("Ufnarovskij graph not implemented for l = 1");
     747  }
     748  int lV = attrib(basering, "isLetterplaceRing");
     749  // TODO: what if l <= 0?
     750  dbprint("computing standard words");
     751  ideal SW = lpStandardWords(G, l - 1); // vertices
     752  int n = ncols(SW);
     753  dbprint("n = " + string(n));
    744754  intmat UG[n][n]; // Ufnarovskij graph
    745755  for (int i = 1; i <= n; i++) {
    746756    for (int j = 1; j <= n; j++) {
     757      dbprint("Ufnarovskii graph: " + string((i-1)*n + j) + "/" + string(n*n) + " entries");
    747758      // [Studzinski page 76]
    748       intvec v = SW[i];
    749       intvec w = SW[j];
     759      poly v = SW[i];
     760      poly w = SW[j];
    750761      intvec v_overlap;
    751762      intvec w_overlap;
    752       //TODO how should the graph look like when l - 1 = 0 ?
    753       if (l - 1 == 0) {
    754         ERROR("Ufnarovskij graph not implemented for l = 1");
    755       }
    756763      if (l - 1 > 1) {
    757         v_overlap = v[2 .. l-1];
    758         w_overlap = w[1 .. l-2];
    759       }
    760       intvec vw = v;
    761       vw[l] = w[l-1];
    762       if (v_overlap == w_overlap && !ivdivides(LG, vw)) {
     764        v_overlap = leadexp(v);
     765        w_overlap = leadexp(w);
     766        v_overlap = v_overlap[(lV+1) .. (l-1)*lV];
     767        w_overlap = w_overlap[1 .. (l-2)*lV];
     768      }
     769      if (v_overlap == w_overlap && !lpLmDivides(G, v * lpVarAt(w, l - 1))) {
    763770        UG[i,j] = 1;
    764771      }
    765       kill v; kill w; kill v_overlap; kill w_overlap; kill vw;
     772      kill v; kill w; kill v_overlap; kill w_overlap;
    766773    } kill j;
    767774  } kill i;
    … …  
    799806  } kill i;
    800807  return (l);
     808}
     809
     810static proc lpStandardWords(ideal G, int length)
     811"ASSUME: G is simplified
     812"
     813{
     814  if (length < 0) {
     815    return (delete(ideal(0), 1)); // no standard words
     816  }
     817
     818  ideal words = maxideal(length);
     819  for (int i = ncols(words); i >= 1; i--) {
     820    if (lpLmDivides(G, words[i])) {
     821      words = delete(words, i);
     822    }
     823  } kill i;
     824  return (words);
    801825}
    802826
    … …  
    858882RETURN: int
    859883PURPOSE: Determines the Gelfand Kirillov dimension of A/<G>
    860 @*       -1 means it is positive infinite
     884@*       -1 means positive infinite
    861885ASSUME: - basering is a Letterplace ring
    862886@*      - G is a Groebner basis
    … …  
    877901    // also if G is the whole ring return minus infinity
    878902    if (leadmonom(G[i]) == 1) {
    879       ERROR("Gk-Dim not defined for 0-ring")
     903      ERROR("GK-Dim not defined for 0-ring")
    880904    }
    881905    kill d;
    882906  } kill i;
    883   // if longest word has length 1 we handle it as a special case
    884   if (l == 1) {
     907  // if longest word has length 1, or G is the zero ideal, we handle it as a special case
     908  if (l == 1 || size(G) == 0) {
    885909    int n = attrib(basering, "isLetterplaceRing"); // variable count
    886910    int k = size(G);
    … …  
    896920  }
    897921
     922  dbprint("computing Ufnarovskii graph");
    898923  intmat UG = lpUfGraph(G);
     924  if (printlevel >= voice + 1) {
     925    UG;
     926  }
    899927
    900928  // check special case 2
    … …  
    905933
    906934  // check special case 3
     935  dbprint("topological sorting of Ufnarovskii graph");
    907936  UG = topologicalSort(UG);
    908 
     937  if (printlevel >= voice + 1) {
     938    UG;
     939  }
     940
     941  dbprint("check if Ufnarovskii graph is DAG");
    909942  if (imIsUpRightTriangle(UG)) {
    910943    UG = eliminateZerosUpTriangle(UG);
    … …  
    912945      return (0)
    913946    }
     947    dbprint("DAG detected, using URTNZD growth alg");
    914948    return(UfGraphURTNZDGrowth(UG));
    915949  }
    916950
    917951  // otherwise count cycles in the Ufnarovskij Graph
     952  dbprint("not a DAG, using regular growth alg");
    918953  return(UfGraphGrowth(UG));
    919954}

  • Singular/LIB/freegb.lib

    r4aa50a r5a8e35  
    3333isVar(p);                        check whether p is a power of a single variable
    3434
     35lpLmDivides(ideal I, poly p)     tests if there is a polynomial q in I with LM(q)|LM(p)
     36lpVarAt(poly p, int pos)         returns the variable (as a poly) at position pos of the poly p
     37
    3538SEE ALSO: fpadim_lib, fpaprops_lib, fpalgebras_lib, LETTERPLACE
    3639";
     40
     41// Remark Oct 2018: iv2lp, lp2iv etc are NOT IN HEADER because
     42// they should not be used anymore
    3743
    3844/* more legacy:
    … …  
    7076  example lpPrint;
    7177  example isVar;
     78
     79  example lpLmDivides;
     80  example lpVarAt;
     81
     82  example ivL2lpI;
     83  example iv2lp;
     84  example iv2lpList;
     85  example iv2lpMat;
     86  example lp2iv;
     87  example lp2ivId;
     88  example lpId2ivLi;
    7289}
    7390
    … …  
    354371  poly i = 1;
    355372  isVar(i);
     373}
     374
     375proc lpLmDivides(ideal I, poly p)
     376"USAGE: lpLmDivides(I); I an ideal
     377RETURN: boolean
     378ASSUME: basering is a Letterplace ring
     379PURPOSE: tests if there is a polynomial q in I with LM(q)|LM(p)
     380EXAMPLE: example lpLmDivides; shows examples
     381"
     382{
     383  for (int i = 1; i <= ncols(I); i++) {
     384    if (system("lpLmDivides", I[i], p)) {
     385      return (1);
     386    }
     387  } kill i;
     388  return (0);
     389}
     390example
     391{
     392  "EXAMPLE:"; echo = 2;
     393  ring r = 0,(x,y),dp;
     394  def R = makeLetterplaceRing(5);
     395  setring R;
     396  poly p = x*y*y;
     397  lpLmDivides(y*y, p);
     398  lpLmDivides(y*x, p);
     399  lpLmDivides(ideal(y*y, y*x), p);
     400}
     401
     402proc lpVarAt(poly p, int pos)
     403"USAGE: lpVarAt(p, pos); p a poly, pos an int
     404RETURN: poly
     405ASSUME: basering is a Letterplace ring
     406PURPOSE: returns the variable (as a poly) at position pos of the poly p
     407EXAMPLE: example lpVarAt; shows examples
     408"
     409{
     410  return (system("lpVarAt", p, pos));
     411}
     412example
     413{
     414  "EXAMPLE:"; echo = 2;
     415  ring r = 0,(x,y),dp;
     416  def R = makeLetterplaceRing(5);
     417  setring R;
     418  poly p = y*y*x;
     419  lpVarAt(p, 3);
    356420}
    357421
    … …  
    34663530// }
    34673531
     3532// ----------------- iv2lp and lp2iv ----------------------
     3533proc ivL2lpI(list L)
     3534"USAGE: ivL2lpI(L); L a list of intvecs (deprecated, will be removed soon)
     3535RETURN: ideal
     3536PURPOSE:Transforming a list of intvecs into an ideal of Letterplace monomials
     3537ASSUME: - Intvec corresponds to a Letterplace monomial
     3538@*      - basering has to be a Letterplace ring
     3539NOTE:   - Assumptions will not be checked!
     3540EXAMPLE: example ivL2lpI; shows examples
     3541"
     3542{
     3543  int i; ideal G;
     3544  poly p;
     3545  for (i = 1; i <= size(L); i++)
     3546  {p = iv2lp(L[i]);
     3547    G[(size(G) + 1)] = p;
     3548  }
     3549  return(G);
     3550}
     3551example
     3552{
     3553  "EXAMPLE:"; echo = 2;
     3554  ring r = 0,(x,y,z),dp;
     3555  def R = makeLetterplaceRing(5);// constructs a Letterplace ring
     3556  setring R; //sets basering to Letterplace ring
     3557  intvec u = 1,1,2; intvec v = 2,1,3; intvec w = 3,1,1;
     3558  // u = x^2y, v = yxz, w = zx^2 in intvec representation
     3559  list L = u,v,w;
     3560  ivL2lpI(L);// invokes the procedure, returns the ideal containing u,v,w
     3561}
     3562
     3563proc iv2lp(intvec I)
     3564"USAGE: iv2lp(I); I an intvec (deprecated, will be removed soon)
     3565RETURN: poly
     3566PURPOSE:Transforming an intvec into the corresponding Letterplace polynomial
     3567ASSUME: - Intvec corresponds to a Letterplace monomial
     3568@*      - basering has to be a Letterplace ring
     3569NOTE:   - Assumptions will not be checked!
     3570EXAMPLE: example iv2lp; shows examples
     3571"
     3572{if (I[1] == 0) {return(1);}
     3573  int i = size(I);
     3574  if (i > attrib(basering,"uptodeg")) {ERROR("polynomial exceeds degreebound");}
     3575  int j; poly p = 1;
     3576  for (j = 1; j <= i; j++) {if (I[j] > 0) { p = p*var(I[j]);}} //ignore zeroes, because they correspond to 1
     3577  return(p);
     3578}
     3579example
     3580{
     3581  "EXAMPLE:"; echo = 2;
     3582  ring r = 0,(x,y,z),dp;
     3583  def R = makeLetterplaceRing(5); // constructs a Letterplace ring
     3584  setring R; //sets basering to Letterplace ring
     3585  // u = x^2y, v = yxz, w = zx^2 in intvec representation
     3586  intvec u = 1,1,2;
     3587  iv2lp(u); // invokes the procedure and returns the corresponding poly
     3588  intvec v = 2,1,3;
     3589  iv2lp(v);
     3590  intvec w = 3,1,1;
     3591  iv2lp(w);
     3592}
     3593
     3594proc iv2lpList(list L)
     3595"USAGE: iv2lpList(L); L a list of intmats (deprecated, will be removed soon)
     3596RETURN: ideal
     3597PURPOSE:Converting a list of intmats into an ideal of corresponding monomials
     3598ASSUME: - The rows of each intmat in L must correspond to a Letterplace monomial
     3599@*      - basering has to be a Letterplace ring
     3600EXAMPLE: example iv2lpList; shows examples
     3601"
     3602{checkAssumptions(0,L);
     3603  ideal G;
     3604  int i;
     3605  for (i = 1; i <= size(L); i++){G = G + iv2lpMat(L[i]);}
     3606  return(G);
     3607}
     3608example
     3609{
     3610  "EXAMPLE:"; echo = 2;
     3611  ring r = 0,(x,y,z),dp;
     3612  def R = makeLetterplaceRing(5); // constructs a Letterplace ring
     3613  setring R; // sets basering to Letterplace ring
     3614  intmat u[3][1] = 1,1,2; intmat v[1][3] = 2,1,3; intmat w[2][3] = 3,1,1,2,3,1;
     3615  // defines intmats of different size containing intvec representations of
     3616  // monomials as rows
     3617  list L = u,v,w;
     3618  print(u); print(v); print(w); // shows the intmats contained in L
     3619  iv2lpList(L); // returns the corresponding monomials as an ideal
     3620}
     3621
     3622
     3623proc iv2lpMat(intmat M)
     3624"USAGE: iv2lpMat(M); M an intmat (deprecated, will be removed soon)
     3625RETURN: ideal
     3626PURPOSE:Converting an intmat into an ideal of the corresponding monomials
     3627ASSUME: - The rows of M must correspond to Letterplace monomials
     3628@*      - basering has to be a Letterplace ring
     3629EXAMPLE: example iv2lpMat; shows examples
     3630"
     3631{list L = M;
     3632  checkAssumptions(0,L);
     3633  kill L;
     3634  ideal G; poly p;
     3635  int i; intvec I;
     3636  for (i = 1; i <= nrows(M); i++)
     3637  { I = M[i,1..ncols(M)];
     3638    p = iv2lp(I);
     3639    G[size(G)+1] = p;
     3640  }
     3641  return(G);
     3642}
     3643example
     3644{
     3645  "EXAMPLE:"; echo = 2;
     3646  ring r = 0,(x,y,z),dp;
     3647  def R = makeLetterplaceRing(5); // constructs a Letterplace ring
     3648  setring R; // sets basering to Letterplace ring
     3649  intmat u[3][1] = 1,1,2; intmat v[1][3] = 2,1,3; intmat w[2][3] = 3,1,1,2,3,1;
     3650  // defines intmats of different size containing intvec representations of
     3651  // monomials as rows
     3652  iv2lpMat(u); // returns the monomials contained in u
     3653  iv2lpMat(v); // returns the monomials contained in v
     3654  iv2lpMat(w); // returns the monomials contained in w
     3655}
     3656
     3657proc lpId2ivLi(ideal G)
     3658"USAGE: lpId2ivLi(G); G an ideal (deprecated, will be removed soon)
     3659RETURN: list
     3660PURPOSE:Transforming an ideal into the corresponding list of intvecs
     3661ASSUME: - basering has to be a Letterplace ring
     3662EXAMPLE: example lpId2ivLi; shows examples
     3663"
     3664{
     3665  int i,j,k;
     3666  list M;
     3667  checkAssumptions(0,M);
     3668  for (i = 1; i <= size(G); i++) {M[i] = lp2iv(G[i]);}
     3669  return(M);
     3670}
     3671example
     3672{
     3673  "EXAMPLE:"; echo = 2;
     3674  ring r = 0,(x,y),dp;
     3675  def R = makeLetterplaceRing(5); // constructs a Letterplace ring
     3676  setring R; // sets basering to Letterplace ring
     3677  ideal L = x*x,y*y,x*y*x;
     3678  lpId2ivLi(L); // returns the corresponding intvecs as a list
     3679}
     3680
     3681proc lp2iv(poly p)
     3682"USAGE: lp2iv(p); p a poly (deprecated, will be removed soon)
     3683RETURN: intvec
     3684PURPOSE: Transforming a monomial into the corresponding intvec
     3685ASSUME: - basering has to be a Letterplace ring
     3686NOTE:   - Assumptions will not be checked!
     3687EXAMPLE: example lp2iv; shows examples
     3688"
     3689{p = normalize(lead(p));
     3690  intvec I;
     3691  int i,j;
     3692  if (deg(p) > attrib(basering,"uptodeg")) {ERROR("Monomial exceeds degreebound");}
     3693  if (p == 1) {return(I);}
     3694  if (p == 0) {ERROR("Monomial is not allowed to equal zero");}
     3695  intvec lep = leadexp(p);
     3696  for ( i = 1; i <= attrib(basering,"isLetterplaceRing"); i++) {if (lep[i] == 1) {I = i; break;}}
     3697  for (i = (attrib(basering,"isLetterplaceRing")+1); i <= size(lep); i++)
     3698  {if (lep[i] == 1)
     3699    { j = (i mod attrib(basering,"isLetterplaceRing"));
     3700      if (j == 0) {I = I,attrib(basering,"isLetterplaceRing");}
     3701      else {I = I,j;}
     3702    }
     3703    else { if (lep[i] > 1) {ERROR("monomial has a not allowed multidegree");}}
     3704  }
     3705  if (I[1] == 0) {ERROR("monomial has a not allowed multidegree");}
     3706  return(I);
     3707}
     3708example
     3709{
     3710  "EXAMPLE:"; echo = 2;
     3711  ring r = 0,(x,y,z),dp;
     3712  def R = makeLetterplaceRing(5); // constructs a Letterplace ring
     3713  setring R; // sets basering to Letterplace ring
     3714  poly p = x*x*z;
     3715  lp2iv(p); // transforms p into the intvec representation
     3716  lp2iv(y*y*x*x);
     3717  lp2iv(z*y*x*z*z);
     3718}
     3719
     3720proc lp2ivId(ideal G)
     3721"USAGE: lp2ivId(G); G an ideal (deprecated, will be removed soon)
     3722RETURN: list
     3723PURPOSE:Converting an ideal into an list of intmats,
     3724@*      the corresponding intvecs forming the rows
     3725ASSUME: - basering has to be a Letterplace ring
     3726EXAMPLE: example lp2ivId; shows examples
     3727"
     3728{G = normalize(lead(G));
     3729  intvec I; list L;
     3730  checkAssumptions(0,L);
     3731  int i,md;
     3732  for (i = 1; i <= size(G); i++) { if (md <= deg(G[i])) {md = deg(G[i]);}}
     3733  while (size(G) > 0)
     3734  {ideal Gt;
     3735    for (i = 1; i <= ncols(G); i++) {if (md == deg(G[i])) {Gt = Gt + G[i]; G[i] = 0;}}
     3736    if (size(Gt) > 0)
     3737    {G = simplify(G,2);
     3738      intmat M [size(Gt)][md];
     3739      for (i = 1; i <= size(Gt); i++) {M[i,1..md] = lp2iv(Gt[i]);}
     3740      L = insert(L,M);
     3741      kill M; kill Gt;
     3742      md = md - 1;
     3743    }
     3744    else {kill Gt; md = md - 1;}
     3745  }
     3746  return(L);
     3747}
     3748example
     3749{
     3750  "EXAMPLE:"; echo = 2;
     3751  ring r = 0,(x,y,z),dp;
     3752  def R = makeLetterplaceRing(5); // constructs a Letterplace ring
     3753  setring R; // sets basering to Letterplace ring
     3754  poly p = x*x*z;
     3755  poly q = y*y*x*x;
     3756  poly w = z*y*x*z;
     3757  // p,q,w are some polynomials we want to transform into their
     3758  // intvec representation
     3759  ideal G = p,q,w;
     3760  lp2ivId(G); // returns the list of intmats for this ideal
     3761}

  • Singular/extra.cc

    r4aa50a r5a8e35  
    12091209    else
    12101210  #endif
     1211  /*==================== divide-test for freeGB  =================*/
     1212  #ifdef HAVE_SHIFTBBA
     1213    if (strcmp(sys_cmd, "lpLmDivides") == 0)
     1214    {
     1215      const short t[]={2,POLY_CMD,POLY_CMD};
     1216      if (iiCheckTypes(h,t,1))
     1217      {
     1218        poly p=(poly)h->CopyD();
     1219        poly q=(poly)h->next->CopyD();
     1220        res->rtyp = INT_CMD;
     1221        res->data = (void*)(long)p_LPDivisibleBy(p, q, currRing);
     1222        return FALSE;
     1223      }
     1224      else return TRUE;
     1225    }
     1226    else
     1227  #endif
     1228  /*==================== get var for freeGB  ====================*/
     1229  #ifdef HAVE_SHIFTBBA
     1230    if (strcmp(sys_cmd, "lpVarAt") == 0)
     1231    {
     1232      const short t[]={2,POLY_CMD,INT_CMD};
     1233      if (iiCheckTypes(h,t,1))
     1234      {
     1235        poly p=(poly)h->CopyD();
     1236        int pos=(int)((long)(h->next->Data()));
     1237        res->rtyp = POLY_CMD;
     1238        res->data = p_LPVarAt(p, pos, currRing);
     1239        return FALSE;
     1240      }
     1241      else return TRUE;
     1242    }
     1243    else
     1244  #endif
    12111245  /*==================== pcv ==================================*/
    12121246  #ifdef HAVE_PCV

  • libpolys/polys/shiftop.cc

    r4aa50a r5a8e35  
    567567      StringAppendS("| ");
    568568    }
    569     if (i % ri->isLPring == 0)
     569    if (i % ri->isLPring == 0 && i != ri->N)
    570570    {
    571571      StringAppendS(" ");
    … …  
    659659  omFreeSize((ADDRESS) B, (b+1)*sizeof(int));
    660660  return(1);
     661}
     662
     663BOOLEAN p_LPDivisibleBy(poly a, poly b, const ring r)
     664{
     665  pIfThen1(b!=NULL, p_LmCheckPolyRing1(b, r));
     666  pIfThen1(a!=NULL, p_LmCheckPolyRing1(a, r));
     667
     668  if (b == NULL) return TRUE;
     669  if (a != NULL && (p_GetComp(a, r) == 0 || p_GetComp(a,r) == p_GetComp(b,r)))
     670      return _p_LPLmDivisibleByNoComp(a,b,r);
     671  return FALSE;
     672}
     673
     674BOOLEAN p_LPLmDivisibleBy(poly a, poly b, const ring r)
     675{
     676  p_LmCheckPolyRing1(b, r);
     677  pIfThen1(a != NULL, p_LmCheckPolyRing1(b, r));
     678  if (p_GetComp(a, r) == 0 || p_GetComp(a,r) == p_GetComp(b,r))
     679    return _p_LPLmDivisibleByNoComp(a, b, r);
     680  return FALSE;
     681}
     682
     683BOOLEAN _p_LPLmDivisibleByNoComp(poly a, poly b, const ring r)
     684{
     685  if(p_LmIsConstantComp(a, r))
     686    return TRUE;
     687#ifdef SHIFT_MULT_COMPAT_MODE
     688  a = p_Head(a, r);
     689  p_mLPunshift(a, r);
     690  b = p_Head(b, r);
     691  p_mLPunshift(b, r);
     692#endif
     693  int i = (r->N / r->isLPring) - p_LastVblock(a, r);
     694  do {
     695    int j = r->N - (i * r->isLPring);
     696    bool divisible = true;
     697    do
     698    {
     699      if (p_GetExp(a, j, r) > p_GetExp(b, j + (i * r->isLPring), r))
     700      {
     701        divisible = false;
     702        break;
     703      }
     704      j--;
     705    }
     706    while (j);
     707    if (divisible) return TRUE;
     708    i--;
     709  }
     710  while (i > -1);
     711#ifdef SHIFT_MULT_COMPAT_MODE
     712  p_Delete(&a, r);
     713  p_Delete(&b, r);
     714#endif
     715  return FALSE;
     716}
     717
     718poly p_LPVarAt(poly p, int pos, const ring r)
     719{
     720  if (p == NULL || pos < 1 || pos > (r->N / r->isLPring)) return NULL;
     721  poly v = p_One(r);
     722  for (int i = (pos-1) * r->isLPring + 1; i <= pos * r->isLPring; i++) {
     723    if (p_GetExp(p, i, r)) {
     724      p_SetExp(v, i - (pos-1) * r->isLPring, 1, r);
     725      return v;
     726    }
     727  }
     728  return v;
    661729}
    662730

  • libpolys/polys/shiftop.h

    r4aa50a r5a8e35  
    4848#define pmIsInV(p) p_mIsInV(p, currRing)
    4949
     50BOOLEAN p_LPDivisibleBy(poly a, poly b, const ring r);
     51BOOLEAN p_LPLmDivisibleBy(poly a, poly b, const ring r);
     52BOOLEAN _p_LPLmDivisibleByNoComp(poly a, poly b, const ring r);
     53
     54poly p_LPVarAt(poly p, int pos, const ring r);
     55
    5056ring freeAlgebra(ring r, int d);
    5157#endif
Note: See TracChangeset for help on using the changeset viewer.