Changeset 658bc7 in git


Ignore:
Timestamp:
Dec 28, 2020, 4:05:23 PM (3 years ago)
Author:
Hans Schoenemann <hannes@…>
Branches:
(u'spielwiese', 'fe61d9c35bf7c61f2b6cbf1b56e25e2f08d536cc')
Children:
7831c520c32afb8d15cbf82e6d77a7d633f27c3b
Parents:
b13fdbde4aac844ef6c4a74da18120de7141a2bf07f5c6f6f6d1c977cdb54864f6ed0380559577ec
git-author:
Hans Schoenemann <hannes@mathematik.uni-kl.de>2020-12-28 16:05:23+01:00
git-committer:
GitHub <noreply@github.com>2020-12-28 16:05:23+01:00
Message:
Merge pull request #1036 from kabouzeid/letterplace-dim

Letterplace dim
Files:
3 added
12 edited

Legend:

Unmodified
Added
Removed

  • Singular/LIB/fpaprops.lib

    rb13fdb r658bc7  
    2626  lpIsSemiPrime(<GB>);    check whether A/<LM(GB)> is semi-prime
    2727  lpIsPrime(<GB>);        check whether A/<LM(GB)> is prime
     28  lpGkDim(<GB>);          compute the Gelfand Kirillov dimension of A/<GB>
    2829  lpGlDimBound(<GB>);     compute an upper bound for the global dimension of A/<GB>
    2930  lpSubstitute();         substitute a variable with polynomials (ring homomorphism)
    … …  
    4243    example lpIsPrime;
    4344    example lpGlDimBound;
     45    example lpGkDim;
    4446    example lpSubstitute;
    4547    example lpCalcSubstDegBound;
    … …  
    449451        break;
    450452      }
    451     }
     453    } kill j;
    452454  } kill i;
    453455
    … …  
    875877}
    876878
    877 // lpGkDim now implemented in dynamic module
     879proc lpGkDim(ideal G)
     880"USAGE: lpGkDim(G); G an ideal in a letterplace ring
     881RETURN: int
     882PURPOSE: Determines the Gelfand Kirillov dimension of A/<G>
     883       -1 means positive infinite
     884ASSUME: - basering is a Letterplace ring
     885      - G is a Groebner basis
     886NOTE: Alias for dim(G)
     887"
     888{
     889  return (dim(G));
     890}
     891example
     892{
     893  "EXAMPLE:"; echo = 2;
     894  ring r = 0,(x,y,z),dp;
     895  ring R = freeAlgebra(r, 5);
     896  ideal I = z; // infinite GK dimension (-1)
     897  lpGkDim(I);
     898  I = x,y,z; I = std(I); // GK dimension 0
     899  lpGkDim(I);
     900  I = x*y, x*z, z*y, z*z; I = std(I); // GK dimension 2
     901  lpGkDim(I);
     902  ideal G = y*x - x*y, z*x - x*z, z*y - y*z; G = std(G);
     903  G;
     904  lpGkDim(G); // GK dimension 3
     905}
    878906/* proc lpGkDim(ideal G) */
    879907/* "USAGE: lpGkDim(G); G an ideal in a letterplace ring */
    … …  
    10241052    } else {
    10251053      if (i == size(G)) { // if last iteration
     1054        G = twostd(G); // otherwise warning that G is no standard basis
    10261055        int gkDim = lpGkDim(G);
    10271056        if (gkDim >= 0) {

  • Singular/dyn_modules/freealgebra/freealgebra.cc

    rb13fdb r658bc7  
    11#include "Singular/libsingular.h"
     2#include "kernel/combinatorics/stairc.h"
    23#include <vector>
    34
    … …  
    9192}
    9293
    93 static BOOLEAN p_LPDivisibleBy(ideal I, poly p, ring r)
    94 {
    95   for(int i = 0; i < IDELEMS(I); i++)
    96   {
    97     if (p_LPDivisibleBy(I->m[i], p, r))
    98     {
    99       return TRUE;
    100     }
    101   }
    102   return FALSE;
    103 }
    104 
    10594static BOOLEAN lpLmDivides(leftv res, leftv h)
    10695{
    … …  
    140129}
    141130
    142 static void _computeStandardWords(ideal words, int n, ideal M, int& last)
    143 {
    144   // assume <M> != <1>
    145   if (n <= 0){
    146     words->m[0] = pOne();
    147     last = 0;
    148     return;
    149   }
    150 
    151   _computeStandardWords(words, n - 1, M, last);
    152 
    153   int nVars = currRing->isLPring - currRing->LPncGenCount;
    154 
    155   for (int j = nVars - 1; j >= 0; j--)
    156   {
    157     for (int i = last; i >= 0; i--)
    158     {
    159       int index = (j * (last + 1)) + i;
    160 
    161       if (words->m[i] != NULL)
    162       {
    163         if (j > 0) {
    164           words->m[index] = pCopy(words->m[i]);
    165         }
    166 
    167         int varOffset = ((n - 1) * currRing->isLPring) + 1;
    168         pSetExp(words->m[index], varOffset + j, 1);
    169         pSetm(words->m[index]);
    170         pTest(words->m[index]);
    171 
    172         if (p_LPDivisibleBy(M, words->m[index], currRing))
    173         {
    174           pDelete(&words->m[index]);
    175           words->m[index] = NULL;
    176         }
    177       }
    178     }
    179   }
    180 
    181   last = nVars * last + nVars - 1;
    182 }
    183 
    184 static ideal computeStandardWords(int n, ideal M)
    185 {
    186   int nVars = currRing->isLPring - currRing->LPncGenCount;
    187 
    188   int maxElems = 1;
    189   for (int i = 0; i < n; i++) // maxElems = nVars^n
    190     maxElems *= nVars;
    191   ideal words = idInit(maxElems);
    192   int last;
    193   _computeStandardWords(words, n, M, last);
    194   idSkipZeroes(words);
    195   return words;
    196 }
    197 
    198 // NULL if graph is undefined
    199 static intvec* ufnarovskiGraph(ideal G, ideal &standardWords)
    200 {
    201   long l = 0;
    202   for (int i = 0; i < IDELEMS(G); i++)
    203     l = si_max(pTotaldegree(G->m[i]), l);
    204   l--;
    205   if (l <= 0)
    206   {
    207     WerrorS("Ufnarovski graph not implemented for l <= 0");
    208     return NULL;
    209   }
    210   int lV = currRing->isLPring;
    211 
    212   standardWords = computeStandardWords(l, G);
    213 
    214   int n = IDELEMS(standardWords);
    215   intvec* UG = new intvec(n, n, 0);
    216   for (int i = 0; i < n; i++)
    217   {
    218     for (int j = 0; j < n; j++)
    219     {
    220       poly v = standardWords->m[i];
    221       poly w = standardWords->m[j];
    222 
    223       // check whether v*x1 = x2*w (overlap)
    224       bool overlap = true;
    225       for (int k = 1; k <= (l - 1) * lV; k++)
    226       {
    227         if (pGetExp(v, k + lV) != pGetExp(w, k)) {
    228           overlap = false;
    229           break;
    230         }
    231       }
    232 
    233       if (overlap)
    234       {
    235         // create the overlap
    236         poly p = pMult(pCopy(v), p_LPVarAt(w, l, currRing));
    237 
    238         // check whether the overlap is normal
    239         bool normal = true;
    240         for (int k = 0; k < IDELEMS(G); k++)
    241         {
    242           if (p_LPDivisibleBy(G->m[k], p, currRing))
    243           {
    244             normal = false;
    245             break;
    246           }
    247         }
    248 
    249         if (normal)
    250         {
    251           IMATELEM(*UG, i + 1, j + 1) = 1;
    252         }
    253       }
    254     }
    255   }
    256   return UG;
    257 }
    258 
    259131static BOOLEAN lpUfnarovskiGraph(leftv res, leftv h)
    260132{
    … …  
    266138
    267139    ideal standardWords;
    268     intvec* graph = ufnarovskiGraph(I, standardWords);
     140    intvec* graph = lp_ufnarovskiGraph(I, standardWords);
    269141
    270142    lists li=(lists)omAllocBin(slists_bin);
    … …  
    282154  else return TRUE;
    283155}
    284 
    285 static std::vector<int> countCycles(const intvec* _G, int v, std::vector<int> path, std::vector<BOOLEAN> visited, std::vector<BOOLEAN> cyclic, std::vector<int> cache)
    286 {
    287   intvec* G = ivCopy(_G); // modifications must be local
    288 
    289   if (cache[v] != -2) return cache; // value is already cached
    290 
    291   visited[v] = TRUE;
    292   path.push_back(v);
    293 
    294   int cycles = 0;
    295   for (int w = 0; w < G->cols(); w++)
    296   {
    297     if (IMATELEM(*G, v + 1, w + 1)) // edge v -> w exists in G
    298     {
    299       if (!visited[w])
    300       { // continue with w
    301         cache = countCycles(G, w, path, visited, cyclic, cache);
    302         if (cache[w] == -1)
    303         {
    304           cache[v] = -1;
    305           return cache;
    306         }
    307         cycles = si_max(cycles, cache[w]);
    308       }
    309       else
    310       { // found new cycle
    311         int pathIndexOfW = -1;
    312         for (int i = path.size() - 1; i >= 0; i--) {
    313           if (cyclic[path[i]] == 1) { // found an already cyclic vertex
    314             cache[v] = -1;
    315             return cache;
    316           }
    317           cyclic[path[i]] = TRUE;
    318 
    319           if (path[i] == w) { // end of the cycle
    320             assume(IMATELEM(*G, v + 1, w + 1) != 0);
    321             IMATELEM(*G, v + 1, w + 1) = 0; // remove edge v -> w
    322             pathIndexOfW = i;
    323             break;
    324           } else {
    325             assume(IMATELEM(*G, path[i - 1] + 1, path[i] + 1) != 0);
    326             IMATELEM(*G, path[i - 1] + 1, path[i] + 1) = 0; // remove edge vi-1 -> vi
    327           }
    328         }
    329         assume(pathIndexOfW != -1); // should never happen
    330         for (int i = path.size() - 1; i >= pathIndexOfW; i--) {
    331           cache = countCycles(G, path[i], path, visited, cyclic, cache);
    332           if (cache[path[i]] == -1)
    333           {
    334             cache[v] = -1;
    335             return cache;
    336           }
    337           cycles = si_max(cycles, cache[path[i]] + 1);
    338         }
    339       }
    340     }
    341   }
    342   cache[v] = cycles;
    343 
    344   delete G;
    345   return cache;
    346 }
    347 
    348 // -1 is infinity
    349 static int graphGrowth(const intvec* G)
    350 {
    351   // init
    352   int n = G->cols();
    353   std::vector<int> path;
    354   std::vector<BOOLEAN> visited;
    355   std::vector<BOOLEAN> cyclic;
    356   std::vector<int> cache;
    357   visited.resize(n, FALSE);
    358   cyclic.resize(n, FALSE);
    359   cache.resize(n, -2);
    360 
    361   // get max number of cycles
    362   int cycles = 0;
    363   for (int v = 0; v < n; v++)
    364   {
    365     cache = countCycles(G, v, path, visited, cyclic, cache);
    366     if (cache[v] == -1)
    367       return -1;
    368     cycles = si_max(cycles, cache[v]);
    369   }
    370   return cycles;
    371 }
    372 
    373 // -1 is infinity, -2 is error
    374 static int gkDim(const ideal _G)
    375 {
    376   if (rField_is_Ring(currRing)) {
    377       WerrorS("GK-Dim not implemented for rings");
    378       return -2;
    379   }
    380 
    381   for (int i=IDELEMS(_G)-1;i>=0; i--)
    382   {
    383     if (pGetComp(_G->m[i]) != 0)
    384     {
    385       WerrorS("GK-Dim not implemented for modules");
    386       return -2;
    387     }
    388     if (pGetNCGen(_G->m[i]) != 0)
    389     {
    390       WerrorS("GK-Dim not implemented for bi-modules");
    391       return -2;
    392     }
    393   }
    394 
    395   ideal G = id_Head(_G, currRing); // G = LM(G) (and copy)
    396   idSkipZeroes(G); // remove zeros
    397   id_DelLmEquals(G, currRing); // remove duplicates
    398 
    399   // get the max deg
    400   long maxDeg = 0;
    401   for (int i = 0; i < IDELEMS(G); i++)
    402   {
    403     maxDeg = si_max(maxDeg, pTotaldegree(G->m[i]));
    404 
    405     // also check whether G = <1>
    406     if (pIsConstantComp(G->m[i]))
    407     {
    408       WerrorS("GK-Dim not defined for 0-ring");
    409       return -2;
    410     }
    411   }
    412 
    413   // early termination if G \subset X
    414   if (maxDeg <= 1)
    415   {
    416     int lV = currRing->isLPring;
    417     int ncGenCount = currRing->LPncGenCount;
    418     if (IDELEMS(G) == lV - ncGenCount) // V = {1} no edges
    419       return 0;
    420     if (IDELEMS(G) == lV - ncGenCount - 1) // V = {1} with loop
    421       return 1;
    422     if (IDELEMS(G) <= lV - ncGenCount - 2) // V = {1} with more than one loop
    423       return -1;
    424   }
    425 
    426   ideal standardWords;
    427   intvec* UG = ufnarovskiGraph(G, standardWords);
    428   if (errorreported || UG == NULL) return -2;
    429   return graphGrowth(UG);
    430 }
    431 
    432 
    433 static BOOLEAN lpGkDim(leftv res, leftv h)
    434 {
    435   const short t[]={1,IDEAL_CMD};
    436   if (iiCheckTypes(h,t,1))
    437   {
    438     assumeStdFlag(h);
    439     ideal G = (ideal) h->Data();
    440     res->rtyp = INT_CMD;
    441     res->data = (void*)(long) gkDim(G);
    442     if (errorreported) return TRUE;
    443     return FALSE;
    444   }
    445   else return TRUE;
    446 }
    447156#endif
    448157
    … …  
    455164  p->iiAddCproc("freealgebra.so","lpLmDivides",FALSE,lpLmDivides);
    456165  p->iiAddCproc("freealgebra.so","lpVarAt",FALSE,lpVarAt);
    457   p->iiAddCproc("freealgebra.so","lpGkDim",FALSE,lpGkDim);
    458166  p->iiAddCproc("freealgebra.so","lpUfnarovskiGraph",FALSE,lpUfnarovskiGraph);
    459167

  • Singular/iparith.cc

    rb13fdb r658bc7  
    40354035{
    40364036  assumeStdFlag(v);
     4037#ifdef HAVE_SHIFTBBA
     4038  if (currRing->isLPring)
     4039  {
     4040#ifdef HAVE_RINGS
     4041    if (rField_is_Ring(currRing))
     4042    {
     4043      WerrorS("`dim` is not implemented for letterplace rings over rings");
     4044      return TRUE;
     4045    }
     4046#endif
     4047    if (currRing->qideal != NULL)
     4048    {
     4049      WerrorS("qring not supported by `dim` for letterplace rings at the moment");
     4050      return TRUE;
     4051    }
     4052    int gkDim = lp_gkDim((ideal)(v->Data()));
     4053    if (errorreported || gkDim == -2) return TRUE;
     4054    res->data = (char *)(long)gkDim;
     4055    return FALSE;
     4056  }
     4057#endif
    40374058  if (rHasMixedOrdering(currRing))
    40384059  {

  • Singular/table.h

    rb13fdb r658bc7  
    122122,{D(jjDET_S),      DET_CMD,         POLY_CMD,       SMATRIX_CMD   , NO_NC |NO_RING}
    123123,{D(jjDET),        DET_CMD,         POLY_CMD,       MATRIX_CMD    , NO_NC |ALLOW_RING}
    124 ,{D(jjDIM),        DIM_CMD,         INT_CMD,        IDEAL_CMD     , ALLOW_PLURAL |ALLOW_RING}
     124,{D(jjDIM),        DIM_CMD,         INT_CMD,        IDEAL_CMD     , ALLOW_NC |ALLOW_RING}
    125125,{D(jjDIM),        DIM_CMD,         INT_CMD,        MODUL_CMD     , ALLOW_PLURAL |ALLOW_RING}
    126126,{D(jjDIM_R),      DIM_CMD,         INT_CMD,        RESOLUTION_CMD, ALLOW_PLURAL |ALLOW_RING}

  • Tst/Manual/lpGlDimBound.res.gz.uu

    rb13fdb r658bc7  
    11begin 644 lpGlDimBound.res.gz
    2 M'XL(")=_(UX"`VQP1VQ$:6U";W5N9"YR97,`C9-=:\(P%(;O]RM>9!=I5VN3
    3 M^HFL,!%$&;O0W8]*JX3U:VG$=K]^J;JT3G%>-<USSB'O0[)ZG\[?`%`/K_,)
    4 M6C*7=L37K3'4ZH,G7!)C_%!]X7F(LEDTY?$DW26!G81[.Y>^?%B=9K#3C$WF
    5 M9R+-\N,@C5T/>MVUT>F`@L@TS"(NOPTP#7LV!$^V$'B&8Y'2*@QKFM6#^MZ1
    6 M+Q7?B#!\B;;A6OA$6.@:==G``P]"/\)<U95F@39H38>_=*&HW*>Y#,B\T3TZ
    7 M3TL6BNDC4J?.0JF-3QY%$+J9*A.'K66]U4A/C^D9R-?.#T2ZCV,#3SS95)I+
    8 M7?6/!GJ?!OI70[LP2TO3H8W"+.K_D:UJ2MW-G-N:&+VBJ4TU9G5JYEYX8MT+
    9 M3ZS7Z.@?/+D@<9K0*XK8X%Q1895GBMCP+D5LU%2D]#2$N$XEI&@H<>EM)2Z[
    10 MHD3%,$W,P',D*=2K20)?!%C[.<\;OMS&+7'5+:G>8/7$=CFAQOCQ!WM9,B:M
    11 #`P``
     2M'XL("'[:GE\"`VQP1VQ$:6U";W5N9"YR97,`C9-=:\(P%(;O_14'V47J:FP2
     3M/Y$5)L*HC%WH[D>E5<+2CZ41V_WZI>J2.L5YU33/.8>\#\GJ?1Z\`0#QX368
     4M05L5"@N^;D]!KSYXRA5RIJWZ"[X/(G\1<Y[,LET:X33>XT*%JK4ZS:"G&9L\
     5MS&66%\=!!C,?S+J/H=<#`DAE<2ZX^G:`&CC`('FZ!0E/X+FH<DO'G>=VT-`_
     6M\J7F&QG'SV(;KV6(I`M]QY:-?.!1'`H(=%W5*:$+Q-+Q+UUHJO99H2(4-+HG
     7MYVG10C-S1.+9+(1@^.1"@#3-1)LX;"WM5B,].::G@+YV822S?9(X\,C33:VY
     8M,E7_:"#W:2!_-73+3N4:.L90=DK[/\&ZIC+=U+NMB9(KFKK$8&I34W;AB?8O
     9M/-%!HV-X\,0`)5E*KBBBHW-%I5N=*:+CNQ3125.1UM,0PKQ:2-E0PLAM)8S>
     10;5,(:%X'IBU`_L_H5[0I$G.G##S?-NJ>0`P``
    1211`
    1312end

  • Tst/Manual/lpGlDimBound.stat

    rb13fdb r658bc7  
    1 1 >> tst_memory_0 :: 1579384727:4122, 64 bit:4.1.2:x86_64-Darwin:Karims-iMac.localdomain:261384
    2 1 >> tst_memory_1 :: 1579384727:4122, 64 bit:4.1.2:x86_64-Darwin:Karims-iMac.localdomain:2155536
    3 1 >> tst_memory_2 :: 1579384727:4122, 64 bit:4.1.2:x86_64-Darwin:Karims-iMac.localdomain:2269840
    4 1 >> tst_timer_1 :: 1579384727:4122, 64 bit:4.1.2:x86_64-Darwin:Karims-iMac.localdomain:6
     11 >> tst_memory_0 :: 1604246142:4132, 64 bit:4.1.3:x86_64-Darwin:Karims-iMac.localdomain:261368
     21 >> tst_memory_1 :: 1604246142:4132, 64 bit:4.1.3:x86_64-Darwin:Karims-iMac.localdomain:2155536
     31 >> tst_memory_2 :: 1604246142:4132, 64 bit:4.1.3:x86_64-Darwin:Karims-iMac.localdomain:2269840
     41 >> tst_timer_1 :: 1604246142:4132, 64 bit:4.1.3:x86_64-Darwin:Karims-iMac.localdomain:6

  • Tst/Manual/lpIsPrime.res.gz.uu

    rb13fdb r658bc7  
    11begin 644 lpIsPrime.res.gz
    2 M'XL(""^!(UX"`VQP27-0<FEM92YR97,`I91?:]LP%,7?^RDN90^R<5W?*^4_
    3 M-6QT#RYCE';O)25*T>;8GJP2>9]^2M+*2D*SP)XLZ^@*G=_1U>./V^([`&`.
    4 MWXHO<&E:DY;J^7(&;O2D*F58-+O8?"'/H6R*]EZKE4PKN4Y;,S<7CV\;T-L&
    5 MRV;>Z+II=[MXF>?@QR*%ZVM`8*:63:G,GPBJVJN#%+2J7D###60)ZQ(;);=-
    6 MO],PW^D/3E]J*3^7+_)9SYE.0$3]LE$.:B'G)11N71=;N`+LU?&[>N=4LZY;
    7 MLV!%4#T)O+([)V3O$F:]$\04?JFR!.TKT7'83CWT4X%WW'DG8+]?YPM=KU>K
    8 MT#S^PSR>9QX/S5_9N$N\.D[!QK;_GZ1N3>>K*3L-A_!#.$2]5>)'<$@<P:%!
    9 M4#'<PN'`5G6%$72R]=)H'XQ-NCTP-#X+#$U",`Y*@(%G&PPV`,'Q-`A.AR#<
    10 MZ>,8M%S(I6L9=YR?P%1EW.?&W;X(PN:83GWM5`CZKUKT1PKN&A='`?#!40!\
    11 M&%2,M@$(8*6ZQ]'P*SU1>#WY^"`%3"SMY<`G9^4@LKT<,+;D<Q"NJ2S%MN]6
    12 B0:=S$/S#"RE$[TZXYMH\:IMGZ[5E&,T^_07;=>BR_@0`````
     2M'XL("./:GE\"`VQP27-0<FEM92YR97,`C91-3^,P$(;O_(H1VH,3A9`9NU^J
     3M-M*NX!"T0@BXHZ`&9&V:9!VC.OSZ=5NPW5:4GN+X\8ST/IGXX?&JN`4`S.%/
     4M\1O.=:_36CZ?S\&NGF0C-8OF9^LGY#G47='?*;FLTJ9:I;TN]=G#1P/Z:/#2
     5ME9UJNW[;Q6&>@UN+%"XO`8'IMNIJJ=\C:%I'1RDHV;R"@I^0)6Q(3)1<=;[3
     6M.-_R>\M?5%7]JE^K9U4RE8"(_+%)#G)1E344]MP0&[@`]'3Z26\LU:NVUPM6
     7M!-6S("N[L2#[1)CY)(@I_)5U#<I5HO6PV;KW6T%VW&8G8/_>RH5J5\ME&!Z_
     8M"8^GA<?]\!<F'A)'IRF8V/CW66K/#*Z:LN-R"+^40^2C$C^00^)`#HV"BO%&
     9M#@>V;!N,8*AZAR:[8DPR[(BAZ4EB:!:*L5("#3Q;:S"!"(['17#:%X$.!=^<
     10MBP,1?'0@@H^#BLE&A`!6RSN<C*_IB<(QX=,]&Y@8VO'!9R?Y$-F.#XP-.1_"
     11H#K>AV/B_1M!Q'X)_.1A"^'3"#OGZ<EE?'V\]PVC^XS_['5S!A@0`````
    1312`
    1413end

  • Tst/Manual/lpIsPrime.stat

    rb13fdb r658bc7  
    1 1 >> tst_memory_0 :: 1579385135:4122, 64 bit:4.1.2:x86_64-Darwin:Karims-iMac.localdomain:256680
    2 1 >> tst_memory_1 :: 1579385135:4122, 64 bit:4.1.2:x86_64-Darwin:Karims-iMac.localdomain:2153488
    3 1 >> tst_memory_2 :: 1579385135:4122, 64 bit:4.1.2:x86_64-Darwin:Karims-iMac.localdomain:2267792
    4 1 >> tst_timer_1 :: 1579385135:4122, 64 bit:4.1.2:x86_64-Darwin:Karims-iMac.localdomain:6
     11 >> tst_memory_0 :: 1604246243:4132, 64 bit:4.1.3:x86_64-Darwin:Karims-iMac.localdomain:256288
     21 >> tst_memory_1 :: 1604246243:4132, 64 bit:4.1.3:x86_64-Darwin:Karims-iMac.localdomain:2153488
     31 >> tst_memory_2 :: 1604246243:4132, 64 bit:4.1.3:x86_64-Darwin:Karims-iMac.localdomain:2267792
     41 >> tst_timer_1 :: 1604246243:4132, 64 bit:4.1.3:x86_64-Darwin:Karims-iMac.localdomain:6

  • kernel/combinatorics/hdegree.cc

    rb13fdb r658bc7  
    1818#include "kernel/combinatorics/hilb.h"
    1919#include "kernel/combinatorics/stairc.h"
     20#include "reporter/reporter.h"
    2021
    2122VAR int  hCo, hMu, hMu2;
    … …  
    15691570 */
    15701571#endif
     1572
     1573#ifdef HAVE_SHIFTBBA
     1574
     1575/*
     1576 * Computation of the Gel'fand-Kirillov Dimension
     1577 */
     1578
     1579#include "polys/shiftop.h"
     1580#include <vector>
     1581
     1582static std::vector<int> countCycles(const intvec* _G, int v, std::vector<int> path, std::vector<BOOLEAN> visited, std::vector<BOOLEAN> cyclic, std::vector<int> cache)
     1583{
     1584  intvec* G = ivCopy(_G); // modifications must be local
     1585
     1586  if (cache[v] != -2) return cache; // value is already cached
     1587
     1588  visited[v] = TRUE;
     1589  path.push_back(v);
     1590
     1591  int cycles = 0;
     1592  for (int w = 0; w < G->cols(); w++)
     1593  {
     1594    if (IMATELEM(*G, v + 1, w + 1)) // edge v -> w exists in G
     1595    {
     1596      if (!visited[w])
     1597      { // continue with w
     1598        cache = countCycles(G, w, path, visited, cyclic, cache);
     1599        if (cache[w] == -1)
     1600        {
     1601          cache[v] = -1;
     1602          return cache;
     1603        }
     1604        cycles = si_max(cycles, cache[w]);
     1605      }
     1606      else
     1607      { // found new cycle
     1608        int pathIndexOfW = -1;
     1609        for (int i = path.size() - 1; i >= 0; i--) {
     1610          if (cyclic[path[i]] == 1) { // found an already cyclic vertex
     1611            cache[v] = -1;
     1612            return cache;
     1613          }
     1614          cyclic[path[i]] = TRUE;
     1615
     1616          if (path[i] == w) { // end of the cycle
     1617            assume(IMATELEM(*G, v + 1, w + 1) != 0);
     1618            IMATELEM(*G, v + 1, w + 1) = 0; // remove edge v -> w
     1619            pathIndexOfW = i;
     1620            break;
     1621          } else {
     1622            assume(IMATELEM(*G, path[i - 1] + 1, path[i] + 1) != 0);
     1623            IMATELEM(*G, path[i - 1] + 1, path[i] + 1) = 0; // remove edge vi-1 -> vi
     1624          }
     1625        }
     1626        assume(pathIndexOfW != -1); // should never happen
     1627        for (int i = path.size() - 1; i >= pathIndexOfW; i--) {
     1628          cache = countCycles(G, path[i], path, visited, cyclic, cache);
     1629          if (cache[path[i]] == -1)
     1630          {
     1631            cache[v] = -1;
     1632            return cache;
     1633          }
     1634          cycles = si_max(cycles, cache[path[i]] + 1);
     1635        }
     1636      }
     1637    }
     1638  }
     1639  cache[v] = cycles;
     1640
     1641  delete G;
     1642  return cache;
     1643}
     1644
     1645// -1 is infinity
     1646static int graphGrowth(const intvec* G)
     1647{
     1648  // init
     1649  int n = G->cols();
     1650  std::vector<int> path;
     1651  std::vector<BOOLEAN> visited;
     1652  std::vector<BOOLEAN> cyclic;
     1653  std::vector<int> cache;
     1654  visited.resize(n, FALSE);
     1655  cyclic.resize(n, FALSE);
     1656  cache.resize(n, -2);
     1657
     1658  // get max number of cycles
     1659  int cycles = 0;
     1660  for (int v = 0; v < n; v++)
     1661  {
     1662    cache = countCycles(G, v, path, visited, cyclic, cache);
     1663    if (cache[v] == -1)
     1664      return -1;
     1665    cycles = si_max(cycles, cache[v]);
     1666  }
     1667  return cycles;
     1668}
     1669
     1670static void _lp_computeStandardWords(ideal words, int n, ideal M, int& last)
     1671{
     1672  // assume <M> != <1>
     1673  if (n <= 0){
     1674    words->m[0] = pOne();
     1675    last = 0;
     1676    return;
     1677  }
     1678
     1679  _lp_computeStandardWords(words, n - 1, M, last);
     1680
     1681  int nVars = currRing->isLPring - currRing->LPncGenCount;
     1682
     1683  for (int j = nVars - 1; j >= 0; j--)
     1684  {
     1685    for (int i = last; i >= 0; i--)
     1686    {
     1687      int index = (j * (last + 1)) + i;
     1688
     1689      if (words->m[i] != NULL)
     1690      {
     1691        if (j > 0) {
     1692          words->m[index] = pCopy(words->m[i]);
     1693        }
     1694
     1695        int varOffset = ((n - 1) * currRing->isLPring) + 1;
     1696        pSetExp(words->m[index], varOffset + j, 1);
     1697        pSetm(words->m[index]);
     1698        pTest(words->m[index]);
     1699
     1700        if (p_LPDivisibleBy(M, words->m[index], currRing))
     1701        {
     1702          pDelete(&words->m[index]);
     1703          words->m[index] = NULL;
     1704        }
     1705      }
     1706    }
     1707  }
     1708
     1709  last = nVars * last + nVars - 1;
     1710}
     1711
     1712static ideal lp_computeStandardWords(int n, ideal M)
     1713{
     1714  int nVars = currRing->isLPring - currRing->LPncGenCount;
     1715
     1716  int maxElems = 1;
     1717  for (int i = 0; i < n; i++) // maxElems = nVars^n
     1718    maxElems *= nVars;
     1719  ideal words = idInit(maxElems);
     1720  int last;
     1721  _lp_computeStandardWords(words, n, M, last);
     1722  idSkipZeroes(words);
     1723  return words;
     1724}
     1725
     1726// NULL if graph is undefined
     1727intvec* lp_ufnarovskiGraph(ideal G, ideal &standardWords)
     1728{
     1729  long l = 0;
     1730  for (int i = 0; i < IDELEMS(G); i++)
     1731    l = si_max(pTotaldegree(G->m[i]), l);
     1732  l--;
     1733  if (l <= 0)
     1734  {
     1735    WerrorS("Ufnarovski graph not implemented for l <= 0");
     1736    return NULL;
     1737  }
     1738  int lV = currRing->isLPring;
     1739
     1740  standardWords = lp_computeStandardWords(l, G);
     1741
     1742  int n = IDELEMS(standardWords);
     1743  intvec* UG = new intvec(n, n, 0);
     1744  for (int i = 0; i < n; i++)
     1745  {
     1746    for (int j = 0; j < n; j++)
     1747    {
     1748      poly v = standardWords->m[i];
     1749      poly w = standardWords->m[j];
     1750
     1751      // check whether v*x1 = x2*w (overlap)
     1752      bool overlap = true;
     1753      for (int k = 1; k <= (l - 1) * lV; k++)
     1754      {
     1755        if (pGetExp(v, k + lV) != pGetExp(w, k)) {
     1756          overlap = false;
     1757          break;
     1758        }
     1759      }
     1760
     1761      if (overlap)
     1762      {
     1763        // create the overlap
     1764        poly p = pMult(pCopy(v), p_LPVarAt(w, l, currRing));
     1765
     1766        // check whether the overlap is normal
     1767        bool normal = true;
     1768        for (int k = 0; k < IDELEMS(G); k++)
     1769        {
     1770          if (p_LPDivisibleBy(G->m[k], p, currRing))
     1771          {
     1772            normal = false;
     1773            break;
     1774          }
     1775        }
     1776
     1777        if (normal)
     1778        {
     1779          IMATELEM(*UG, i + 1, j + 1) = 1;
     1780        }
     1781      }
     1782    }
     1783  }
     1784  return UG;
     1785}
     1786
     1787// -1 is infinity, -2 is error
     1788int lp_gkDim(const ideal _G)
     1789{
     1790  id_Test(_G, currRing);
     1791
     1792  if (rField_is_Ring(currRing)) {
     1793      WerrorS("GK-Dim not implemented for rings");
     1794      return -2;
     1795  }
     1796
     1797  for (int i=IDELEMS(_G)-1;i>=0; i--)
     1798  {
     1799    if (_G->m[i] != NULL)
     1800    {
     1801      if (pGetComp(_G->m[i]) != 0)
     1802      {
     1803        WerrorS("GK-Dim not implemented for modules");
     1804        return -2;
     1805      }
     1806      if (pGetNCGen(_G->m[i]) != 0)
     1807      {
     1808        WerrorS("GK-Dim not implemented for bi-modules");
     1809        return -2;
     1810      }
     1811    }
     1812  }
     1813
     1814  ideal G = id_Head(_G, currRing); // G = LM(G) (and copy)
     1815  idSkipZeroes(G); // remove zeros
     1816  id_DelLmEquals(G, currRing); // remove duplicates
     1817
     1818  // check if G is the zero ideal
     1819  if (IDELEMS(G) == 1 && G->m[0] == NULL)
     1820  {
     1821    // NOTE: this is needed because if the ideal is <0>, then idSkipZeroes keeps this element, and IDELEMS is still 1!
     1822    int lV = currRing->isLPring;
     1823    int ncGenCount = currRing->LPncGenCount;
     1824    if (lV - ncGenCount == 0)
     1825      return 0;
     1826    if (lV - ncGenCount == 1)
     1827      return 1;
     1828    if (lV - ncGenCount >= 2)
     1829      return -1;
     1830  }
     1831
     1832  // get the max deg
     1833  long maxDeg = 0;
     1834  for (int i = 0; i < IDELEMS(G); i++)
     1835  {
     1836    maxDeg = si_max(maxDeg, pTotaldegree(G->m[i]));
     1837
     1838    // also check whether G = <1>
     1839    if (pIsConstantComp(G->m[i]))
     1840    {
     1841      WerrorS("GK-Dim not defined for 0-ring");
     1842      return -2;
     1843    }
     1844  }
     1845
     1846  // early termination if G \subset X
     1847  if (maxDeg <= 1)
     1848  {
     1849    int lV = currRing->isLPring;
     1850    int ncGenCount = currRing->LPncGenCount;
     1851    if (IDELEMS(G) == lV - ncGenCount) // V = {1} no edges
     1852      return 0;
     1853    if (IDELEMS(G) == lV - ncGenCount - 1) // V = {1} with loop
     1854      return 1;
     1855    if (IDELEMS(G) <= lV - ncGenCount - 2) // V = {1} with more than one loop
     1856      return -1;
     1857  }
     1858
     1859  ideal standardWords;
     1860  intvec* UG = lp_ufnarovskiGraph(G, standardWords);
     1861  if (errorreported || UG == NULL) return -2;
     1862  return graphGrowth(UG);
     1863}
     1864#endif

  • kernel/combinatorics/stairc.h

    rb13fdb r658bc7  
    3232ideal scKBase(int deg, ideal  s, ideal Q=NULL, intvec * mv=NULL);
    3333
     34#if HAVE_SHIFTBBA
     35int lp_gkDim(const ideal G);
     36intvec * lp_ufnarovskiGraph(ideal G, ideal &standardWords);
     37#endif
     38
    3439#endif
    3540

  • libpolys/polys/shiftop.cc

    rb13fdb r658bc7  
    818818  p_Delete(&b, r);
    819819#endif
     820  return FALSE;
     821}
     822
     823BOOLEAN p_LPDivisibleBy(ideal I, poly p, ring r)
     824{
     825  for(int i = 0; i < IDELEMS(I); i++)
     826  {
     827    if (p_LPDivisibleBy(I->m[i], p, r))
     828    {
     829      return TRUE;
     830    }
     831  }
    820832  return FALSE;
    821833}

  • libpolys/polys/shiftop.h

    rb13fdb r658bc7  
    5454BOOLEAN p_LPLmDivisibleBy(poly a, poly b, const ring r);
    5555BOOLEAN _p_LPLmDivisibleByNoComp(poly a, poly b, const ring r);
     56BOOLEAN p_LPDivisibleBy(ideal I, poly p, ring r);
    5657#define pLPDivisibleBy(a, b) p_LPLmDivisibleBy(a, b, currRing)
    5758#define pLPLmDivisibleBy(a, b) p_LPLmDivisibleBy(a, b, currRing)
Note: See TracChangeset for help on using the changeset viewer.