Changeset 3f58e0f in git
 Timestamp:
 Dec 21, 2017, 8:26:44 PM (5 years ago)
 Branches:
 (u'spielwiese', '91fdef05f09f54b8d58d92a472e9c4a43aa4656f')
 Children:
 cb8124385abff6727059b05b1827fc734f8c42c8
 Parents:
 86d5ade6a65b37e57178a78ac1ba4a5b1a5d5e1044168ad1298cc934d410b44610566740ef33fc03
 Location:
 Singular/LIB
 Files:

 4 added
 2 edited
Legend:
 Unmodified
 Added
 Removed

Singular/LIB/fpadim.lib
r44168a r3f58e0f 4 4 info=" 5 5 LIBRARY: fpadim.lib Algorithms for quotient algebras in the letterplace case 6 AUTHORS: Grischa Studzinski, grischa.studzinski@rwthaachen.de 6 AUTHORS: Grischa Studzinski, grischa.studzinski at rwthaachen.de 7 @* Viktor Levandovskyy, viktor.levandovskyy at math.rwthaachen.de 8 @* Karim Abou Zeid, karim.abou.zeid at rwthaachen.de 7 9 8 10 Support: Joint projects LE 2697/21 and KR 1907/31 of the Priority Programme SPP 1489: 9 @* 'Algorithmische und Experimentelle Methoden in Algebra, Geometrie und Zahlentheorie' 10 @* of the German DFG 11 12 OVERVIEW: Given the free algebra A = K<x_1,...,x_n> and a (finite) Groebner basis 11 'Algorithmische und Experimentelle Methoden in Algebra, Geometrie und Zahlentheorie' 12 of the German DFG 13 and Project II.6 of the transregional collaborative research centre 14 SFBTRR 195 'Symbolic Tools in Mathematics and their Application' of the German DFG 15 16 OVERVIEW: Given the free associative algebra A = K<x_1,...,x_n> and a (finite) Groebner basis 13 17 GB = {g_1,..,g_w}, one is interested in the Kdimension and in the 14 18 explicit Kbasis of A/<GB>. 15 19 Therefore one is interested in the following data: 16 @*  the Ufnarovskij graph induced by GB 17 @*  the mistletoes of A/<GB> 18 @*  the Kdimension of A/<GB> 19 @*  the Hilbert series of A/<GB> 20 21 The Ufnarovskij graph is used to determine whether A/<GB> has finite 22 Kdimension. One has to check if the graph contains cycles. 23 For the whole theory we refer to [ufna]. Given a 24 reduced set of monomials GB one can define the basis tree, whose vertex 25 set V consists of all normal monomials w.r.t. GB. For every two 26 monomials m_1, m_2 in V there is a direct edge from m_1 to m_2, if and 27 only if there exists x_k in {x_1,..,x_n}, such that m_1*x_k = m_2. The 28 set M = {m in V  there is no edge from m to another monomial in V} is 29 called the set of mistletoes. As one can easily see it consists of 30 the endpoints of the graph. Since there is a unique path to every 31 monomial in V the whole graph can be described only from the knowledge 32 of the mistletoes. Note that V corresponds to a basis of A/<GB>, so 33 knowing the mistletoes we know a Kbasis. The name mistletoes was given 34 to those points because of these miraculous value and the algorithm is 35 named sickle, because a sickle is the tool to harvest mistletoes. 36 For more details see [studzins]. This package uses the Letterplace 37 format introduced by [lls]. The algebra can either be represented as a 38 Letterplace ring or via integer vectors: Every variable will only be 39 represented by its number, so variable one is represented as 1, 40 variable two as 2 and so on. The monomial x_1*x_3*x_2 for example will 41 be stored as (1,3,2). Multiplication is concatenation. Note that there 42 is no algorithm for computing the normal form needed for our case. 43 Note that the name fpadim.lib is short for dimensions of finite 44 presented algebras. 20  the Ufnarovskij graph induced by GB 21  the mistletoes of A/<GB> (special monomials in a basis) 22  the Kdimension of A/<GB> 23  the Hilbert series of A/<GB> 24 25 @* The Ufnarovskij graph is used to determine whether A/<GB> has finite 26 @* Kdimension. One has to check if the graph contains cycles. 27 @* For the whole theory we refer to [ufna]. Given a 28 @* reduced set of monomials GB one can define the basis tree, whose vertex 29 @* set V consists of all normal monomials w.r.t. GB. For every two 30 @* monomials m_1, m_2 in V there is a direct edge from m_1 to m_2, if and 31 @* only if there exists x_k in {x_1,..,x_n}, such that m_1*x_k = m_2. The 32 @* set M = {m in V  there is no edge from m to another monomial in V} is 33 @* called the set of mistletoes. As one can easily see it consists of 34 @* the endpoints of the graph. Since there is a unique path to every 35 @* monomial in V the whole graph can be described only from the knowledge 36 @* of the mistletoes. Note that V corresponds to a basis of A/<GB>, so 37 @* knowing the mistletoes we know a Kbasis. The name mistletoes was given 38 @* to those points because of these miraculous value and the algorithm is 39 @* named sickle, because a sickle is the tool to harvest mistletoes. 40 @* For more details see [studzins]. This package uses the Letterplace 41 @* format introduced by [lls]. The algebra can either be represented as a 42 @* Letterplace ring or via integer vectors: Every variable will only be 43 @* represented by its number, so variable one is represented as 1, 44 @* variable two as 2 and so on. The monomial x_1*x_3*x_2 for example will 45 @* be stored as (1,3,2). Multiplication is concatenation. Note that the 46 @* approach in this library does not need an algorithm for computing the normal 47 @* form yet. Note that the name fpadim.lib is short for dimensions of 48 @* finite presented algebras. 49 @* 45 50 46 51 REFERENCES: … … 48 53 @* [ufna] Ufnarovskij: Combinatorical and asymptotic methods in algebra, 1990 49 54 @* [lls] Levandovskyy, La Scala: Letterplace ideals and noncommutative 50 55 Groebner bases, 2009 51 56 @* [studzins] Studzinski: Dimension computations in noncommutative, 52 53 54 Assumptions:55 @* basering is always a Letterplace ring56 @* all intvecs correspond to Letterplace monomials57 @*  if you specify a different degree bound d, 58 d <= attrib(basering,uptodeg) should hold. 59 @*In the procedures below, 'iv' stands for intvec representation60 57 associative algebras, Diploma thesis, RWTH Aachen, 2010 58 59 NOTE: 60  basering is always a Letterplace ring 61  all intvecs correspond to Letterplace monomials 62  if you specify a different degree bound d, d <= attrib(basering,uptodeg) holds 63 64 In the procedures below, 'iv' stands for intvec representation 65 and 'lp' for the letterplace representation of monomials 61 66 62 67 PROCEDURES: 68 69 lpMis2Dim(M); computes the Kdimension of the monomial factor algebra 70 lpKDim(G[,d,n]); computes the Kdimension of A/<G> 71 lpDimCheck(G); checks if the Kdimension of A/<G> is infinite 72 lpMis2Base(M); computes a Kbasis of the factor algebra 73 lpHilbert(G[,d,n]); computes the Hilbert series of A/<G> in lp format 74 lpDHilbert(G[,d,n]); computes the Kdimension and Hilbert series of A/<G> 75 lpDHilbertSickle(G[,d,n]); computes mistletoes, Kdimension and Hilbert series 63 76 64 77 ivDHilbert(L,n[,d]); computes the Kdimension and the Hilbert series … … 73 86 ivSickleHil(L,n[,d]); computes the mistletoes and Hilbert series of A/<L> 74 87 ivSickleDim(L,n[,d]); computes the mistletoes and the Kdimension of A/<L> 75 lpDHilbert(G[,d,n]); computes the Kdimension and Hilbert series of A/<G>76 lpDHilbertSickle(G[,d,n]); computes mistletoes, Kdimension and Hilbert series77 lpHilbert(G[,d,n]); computes the Hilbert series of A/<G> in lp format78 lpDimCheck(G); checks if the Kdimension of A/<G> is infinite79 lpKDim(G[,d,n]); computes the Kdimension of A/<G> in lp format80 lpMis2Base(M); computes a Kbasis of the factor algebra81 lpMis2Dim(M); computes the Kdimension of the factor algebra82 88 lpOrdMisLex(M); orders an ideal of lpmonomials lexicographically 83 89 lpSickle(G[,d,n]); computes the mistletoes of A/<G> in lp format … … 85 91 lpSickleDim(G[,d,n]); computes the mistletoes and the Kdimension of A/<G> 86 92 sickle(G[,m,d,h]); can be used to access all lp main procedures 87 88 93 89 94 ivL2lpI(L); transforms a list of intvecs into an ideal of lp monomials … … 145 150 {for (i3 = 1; i3 <= n; i3++) 146 151 {for (i4 = 1; i4 <= (n^(i11)); i4++) 147 { 148 M[i2,i1] = i3; 152 {M[i2,i1] = i3; 149 153 i2 = i2 + 1; 150 }154 } 151 155 } 152 156 } … … 170 174 "PURPOSE:checks, if all entries in M are variablerelated 171 175 " 172 {if ((nrows(M) == 1) && (ncols(M) == 1)) {if (M[1,1] == 0){return(0);}} 173 int i,j; 176 {int i,j; 174 177 for (i = 1; i <= nrows(M); i++) 175 178 {for (j = 1; j <= ncols(M); j++) … … 328 331 } 329 332 333 334 static proc findCycleDFS(int i, intmat T, intvec V) 335 " 336 PURPOSE: 337 this is a classical deepfirst search for cycles contained in a graph given by an intmat 338 " 339 { 340 intvec rV; 341 int k,k1,t; 342 int j = V[size(V)]; 343 if (T[j,i] > 0) {return(V);} 344 else 345 { 346 for (k = 1; k <= ncols(T); k++) 347 { 348 t = 0; 349 if (T[j,k] > 0) 350 { 351 for (k1 = 1; k1 <= size(V); k1++) {if (V[k1] == k) {t = 1; break;}} 352 if (t == 0) 353 { 354 rV = V; 355 rV[size(rV)+1] = k; 356 rV = findCycleDFS(i,T,rV); 357 if (rV[1] > 1) {return(rV);} 358 } 359 } 360 } 361 } 362 return(intvec(1)); 363 } 364 365 366 330 367 static proc findHCoeff(intvec V,int n,list L,intvec P,intvec H,list #) 331 368 "USAGE: findHCoeff(V,n,L,P,H,degbound); L a list of intmats, degbound an integer … … 565 602 } 566 603 return(R); 567 568 604 } 569 605 } … … 647 683 } 648 684 685 static proc growthAlg(intmat T, list #) 686 " 687 real algorithm for checking the growth of an algebra 688 " 689 { 690 int s = 1; 691 if (size(#) > 0) { s = #[1];} 692 int j; 693 int n = ncols(T); 694 intvec NV,C; NV[n] = 0; int m,i; 695 intmat T2[n][n] = T[1..n,1..n]; intmat N[n][n]; 696 if (T2 == N) 697 { 698 for (i = 1; i <= n; i++) 699 { 700 if (m < T[n+1,i]) { m = T[n+1,i];} 701 } 702 return(m); 703 } 704 705 //first part: the diagonals 706 for (i = s; i <= n; i++) 707 { 708 if (T[i,i] > 0) 709 { 710 if ((T[i,i] >= 1) && (T[n+1,i] > 0)) {return(1);} 711 if ((T[i,i] == 1) && (T[n+1,i] == 0)) 712 { 713 T[i,i] = 0; 714 T[n+1,i] = 1; 715 return(growthAlg(T)); 716 } 717 } 718 } 719 720 //second part: searching for the last but one vertices 721 T2 = T2*T2; 722 for (i = s; i <= n; i++) 723 { 724 if ((intvec(T[i,1..n]) <> intvec(0)) && (intvec(T2[i,1..n]) == intvec(0))) 725 { 726 for (j = 1; j <= n; j++) 727 { 728 if ((T[i,j] > 0) && (m < T[n+1,j])) {m = T[n+1,j];} 729 } 730 T[n+1,i] = T[n+1,i] + m; 731 T[i,1..n] = NV; 732 return(growthAlg(T)); 733 } 734 } 735 m = 0; 736 737 //third part: searching for circles 738 for (i = s; i <= n; i++) 739 { 740 T2 = T[1..n,1..n]; 741 C = findCycleDFS(i,T2, intvec(i)); 742 if (C[1] > 0) 743 { 744 for (j = 2; j <= size(C); j++) 745 { 746 T[i,1..n] = T[i,1..n] + T[C[j],1..n]; 747 T[C[j],1..n] = NV; 748 } 749 for (j = 2; j <= size(C); j++) 750 { 751 T[1..n,i] = T[1..n,i] + T[1..n,C[j]]; 752 T[1..n,C[j]] = NV; 753 } 754 T[i,i] = T[i,i]  size(C) + 1; 755 m = 0; 756 for (j = 1; j <= size(C); j++) 757 { 758 m = m + T[n+1,C[j]]; 759 } 760 for (j = 1; j <= size(C); j++) 761 { 762 T[n+1,C[j]] = m; 763 } 764 return(growthAlg(T,i)); 765 } 766 else {ERROR("No Cycle found, something seems wrong! Please contact the authors.");} 767 } 768 769 m = 0; 770 for (i = 1; i <= n; i++) 771 { 772 if (m < T[n+1,i]) 773 { 774 m = T[n+1,i]; 775 } 776 } 777 return(m); 778 } 779 780 static proc GlDimSuffix(intvec v, intvec g) 781 { 782 //Computes the shortest r such that g is a suffix for vr 783 //only valid for lex orderings? 784 intvec r,gt,vt,lt,g2; 785 int lg,lv,l,i,c,f; 786 lg = size(g); lv = size(v); 787 if (lg <= lv) 788 { 789 l = lvlg; 790 } 791 else 792 { 793 l = 0; g2 = g[(lv+1)..lg]; 794 g = g[1..lv]; lg = size(g); 795 c = 1; 796 } 797 while (l < lv) 798 { 799 vt = v[(l+1)..lv]; 800 gt = g[1..(lvl)]; 801 lt = size(gt); 802 for (i = 1; i <= lt; i++) 803 { 804 if (vt[i]<>gt[i]) {l++; break;} 805 } 806 if (lt <=i ) { f = 1; break;} 807 } 808 if (f == 0) {return(g);} 809 r = g[(lvl+1)..lg]; 810 if (c == 1) {r = r,g2;} 811 return(r); 812 } 813 814 static proc isNormal(intvec V, list G) 815 { 816 int i,j,k,l; 817 k = 0; 818 for (i = 1; i <= size(G); i++) 819 { 820 if ( size(G[i]) <= size(V) ) 821 { 822 while ( size(G[i])+k <= size(V) ) 823 { 824 if ( G[i] == V[(1+k)..size(V)] ) {return(1);} 825 } 826 } 827 } 828 return(0); 829 } 830 831 static proc findDChain(list L) 832 { 833 list Li; int i,j; 834 for (i = 1; i <= size(L); i++) {Li[i] = size(L[i]);} 835 Li = sort(Li); Li = Li[1]; 836 return(Li[size(Li)]); 837 } 838 649 839 static proc isInList(intvec V, list L) 650 840 "USAGE: isInList(V,L); V an intvec, L a list of intvecs … … 684 874 } 685 875 876 877 static proc isPF(intvec P, intvec I) 878 " 879 PURPOSE: 880 checks, if a word P is a praefix of another word I 881 " 882 { 883 int n = size(P); 884 if (n <= 0  P == 0) {return(1);} 885 if (size(I) < n) {return(0);} 886 intvec IP = I[1..n]; 887 if (IP == P) {return(1);} 888 else {return(0);} 889 } 890 686 891 proc ivL2lpI(list L) 687 892 "USAGE: ivL2lpI(L); L a list of intvecs 688 893 RETURN: ideal 689 PURPOSE:Transforming a list of intvecs into an ideal of Letterplace monomials. 690 @* For the encoding of the variables see the overview. 894 PURPOSE:Transforming a list of intvecs into an ideal of Letterplace monomials 691 895 ASSUME:  Intvec corresponds to a Letterplace monomial 692 896 @*  basering has to be a Letterplace ring 897 NOTE:  Assumptions will not be checked! 693 898 EXAMPLE: example ivL2lpI; shows examples 694 899 " 695 { checkAssumptions(0,L);900 { 696 901 int i; ideal G; 697 902 poly p; … … 718 923 RETURN: poly 719 924 PURPOSE:Transforming an intvec into the corresponding Letterplace polynomial 720 @* For the encoding of the variables see the overview.721 925 ASSUME:  Intvec corresponds to a Letterplace monomial 722 926 @*  basering has to be a Letterplace ring … … 748 952 RETURN: ideal 749 953 PURPOSE:Converting a list of intmats into an ideal of corresponding monomials 750 @* The rows of the intmat corresponds to an intvec, which stores the751 @* monomial.752 @* For the encoding of the variables see the overview.753 954 ASSUME:  The rows of each intmat in L must correspond to a Letterplace monomial 754 955 @*  basering has to be a Letterplace ring … … 779 980 "USAGE: iv2lpMat(M); M an intmat 780 981 RETURN: ideal 781 PURPOSE:Converting an intmat into an ideal of the corresponding monomials. 782 @* The rows of the intmat corresponds to an intvec, which stores the 783 @* monomial. 784 @* For the encoding of the variables see the overview. 982 PURPOSE:Converting an intmat into an ideal of the corresponding monomials 785 983 ASSUME:  The rows of M must correspond to Letterplace monomials 786 984 @*  basering has to be a Letterplace ring … … 816 1014 "USAGE: lpId2ivLi(G); G an ideal 817 1015 RETURN: list 818 PURPOSE:Transforming an ideal into the corresponding list of intvecs. 819 @* For the encoding of the variables see the overview. 1016 PURPOSE:Transforming an ideal into the corresponding list of intvecs 820 1017 ASSUME:  basering has to be a Letterplace ring 821 1018 EXAMPLE: example lpId2ivLi; shows examples 822 1019 " 823 {int i,j,k; 1020 { 1021 int i,j,k; 824 1022 list M; 825 1023 checkAssumptions(0,M); … … 840 1038 "USAGE: lp2iv(p); p a poly 841 1039 RETURN: intvec 842 PURPOSE:Transforming a monomial into the corresponding intvec. 843 @* For the encoding of the variables see the overview. 1040 PURPOSE:Transforming a monomial into the corresponding intvec 844 1041 ASSUME:  basering has to be a Letterplace ring 845 1042 NOTE:  Assumptions will not be checked! … … 883 1080 RETURN: list 884 1081 PURPOSE:Converting an ideal into an list of intmats, 885 @* the corresponding intvecs forming the rows. 886 @* For the encoding of the variables see the overview. 1082 @* the corresponding intvecs forming the rows 887 1083 ASSUME:  basering has to be a Letterplace ring 888 1084 EXAMPLE: example lp2ivId; shows examples … … 925 1121 // main procedures 926 1122 1123 static proc lpGraphOfNormalWords(ideal G) 1124 "USAGE: lpGraphOfNormalWords(G); G a set of monomials in a letterplace ring 1125 RETURN: intmat 1126 PURPOSE: Constructs the graph of normal words induced by G 1127 @*: the adjacency matrix of the graph of normal words induced by G 1128 ASSUME:  basering is a Letterplace ring 1129  G are the leading monomials of a Groebner basis 1130 " 1131 { 1132 // construct the Graph of normal words [Studzinski page 78] 1133 // construct set of vertices 1134 int v = attrib(basering,"lV"); int d = attrib(basering,"uptodeg"); 1135 ideal V; poly p,q,w; 1136 ideal LG = lead(G); 1137 int i,j,k,b; intvec E,Et; 1138 for (i = 1; i <= v; i++){V = V, var(i);} 1139 for (i = 1; i <= size(LG); i++) 1140 { 1141 E = leadexp(LG[i]); 1142 if (E == intvec(0)) {V = V,monomial(intvec(0));} 1143 else 1144 { 1145 for (j = 1; j < d; j++) 1146 { 1147 Et = E[(j*v+1)..(d*v)]; 1148 if (Et == intvec(0)) {break;} 1149 else {V = V, monomial(Et);} 1150 } 1151 } 1152 } 1153 V = simplify(V,2+4); 1154 printf("V = %p", V); 1155 1156 1157 // construct incidence matrix 1158 1159 list LV = lpId2ivLi(V); 1160 intvec Ip,Iw; 1161 int n = size(V); 1162 intmat T[n+1][n]; 1163 for (i = 1; i <= n; i++) 1164 { 1165 // printf("for1 (i=%p, n=%p)", i, n); 1166 p = V[i]; Ip = lp2iv(p); 1167 for (j = 1; j <= n; j++) 1168 { 1169 // printf("for2 (j=%p, n=%p)", j, n); 1170 k = 1; b = 1; 1171 q = V[j]; 1172 w = lpNF(lpMult(p,q),LG); 1173 if (w <> 0) 1174 { 1175 Iw = lp2iv(w); 1176 while (k <= n) 1177 { 1178 // printf("while (k=%p, n=%p)", k, n); 1179 if (isPF(LV[k],Iw) > 0) 1180 {if (isPF(LV[k],Ip) == 0) {b = 0; k = n+1;} else {k++;} 1181 } 1182 else {k++;} 1183 } 1184 T[i,j] = b; 1185 // print("Incidence Matrix:"); 1186 // print(T); 1187 } 1188 } 1189 } 1190 return(T); 1191 } 1192 1193 // This proc is deprecated, see lpGkDim() in fpaprops.lib 1194 /* proc lpGkDim(ideal G) */ 1195 /* "USAGE: lpGkDim(G); G an ideal in a letterplace ring */ 1196 /* RETURN: int */ 1197 /* PURPOSE: Determines the Gelfand Kirillov dimension of A/<G> */ 1198 /* @*: 1 means it is infinite */ 1199 /* ASSUME:  basering is a Letterplace ring */ 1200 /*  G is a Groebner basis */ 1201 /* NOTE: see fpaprops.lib for a faster and more up to date version of this method */ 1202 /* " */ 1203 /* { */ 1204 /* return(growthAlg(lpGraphOfNormalWords(G))); */ 1205 /* } */ 1206 927 1207 proc ivDHilbert(list L, int n, list #) 928 1208 "USAGE: ivDHilbert(L,n[,degbound]); L a list of intmats, n an integer, … … 932 1212 ASSUME:  basering is a Letterplace ring 933 1213 @*  all rows of each intmat correspond to a Letterplace monomial 934 @* for the encoding of the variables see the overview935 1214 @*  if you specify a different degree bound degbound, 936 @* degbound <= attrib(basering,uptodeg) should hold.1215 @* degbound <= attrib(basering,uptodeg) holds 937 1216 NOTE:  If L is the list returned, then L[1] is an integer corresponding to the 938 1217 @* dimension, L[2] is an intvec which contains the coefficients of the … … 984 1263 ASSUME:  basering is a Letterplace ring. 985 1264 @*  All rows of each intmat correspond to a Letterplace monomial. 986 @* for the encoding of the variables see the overview987 1265 @*  If you specify a different degree bound degbound, 988 @* degbound <= attrib(basering,uptodeg) should hold.1266 @* degbound <= attrib(basering,uptodeg) holds. 989 1267 NOTE:  If L is the list returned, then L[1] is an integer, L[2] is an intvec 990 1268 @* which contains the coefficients of the Hilbert series and L[3] … … 1031 1309 RETURN: int, 0 if the dimension is finite, or 1 otherwise 1032 1310 PURPOSE:Decides, whether the Kdimension is finite or not 1033 ASSUME:  basering is a Letterplace ring 1034 @*  All rows of each intmat correspond to a Letterplace monomial 1035 @* For the encoding of the variables see the overview. 1036 NOTE:  n is the number of variables 1311 ASSUME:  basering is a Letterplace ring. 1312 @*  All rows of each intmat correspond to a Letterplace monomial. 1313 NOTE:  n is the number of variables. 1037 1314 EXAMPLE: example ivDimCheck; shows examples 1038 1315 " … … 1090 1367 ASSUME:  basering is a Letterplace ring. 1091 1368 @*  all rows of each intmat correspond to a Letterplace monomial 1092 @* for the encoding of the variables see the overview1093 1369 @*  if you specify a different degree bound degbound, 1094 @* degbound <= attrib(basering,uptodeg) should hold.1370 @* degbound <= attrib(basering,uptodeg) holds. 1095 1371 NOTE:  If degbound is set, a degree bound will be added. By default there 1096 1372 @* is no degree bound. … … 1176 1452 ASSUME:  basering is a Letterplace ring. 1177 1453 @*  all rows of each intmat correspond to a Letterplace monomial 1178 @* for the encoding of the variables see the overview1179 1454 @*  if you specify a different degree bound degbound, 1180 @* degbound <= attrib(basering,uptodeg) should hold.1455 @* degbound <= attrib(basering,uptodeg) holds. 1181 1456 NOTE:  If degbound is set, a degree bound will be added. By default there 1182 1457 @* is no degree bound. … … 1263 1538 " 1264 1539 { 1265 //checkAssumptions(0,M);1540 //checkAssumptions(0,M); 1266 1541 intvec L,A; 1267 1542 if (size(M) == 0){ERROR("There are no mistletoes, so it appears your dimension is infinite!");} … … 1274 1549 for (i = 2; i <= size(M); i++) 1275 1550 {A = M[i]; L = M[i1]; 1276 s = size(A);1277 if (s > size(L))1278 {d = size(L);1279 for (j = s; j > d; j) {Rt = insert(Rt,intvec(A[1..j]));}1280 A = A[1..d];1281 }1282 if (size(L) > s){L = L[1..s];}1283 while (A <> L)1284 {Rt = insert(Rt, intvec(A));1285 if (size(A) > 1)1286 {A = A[1..(size(A)1)];1287 L = L[1..(size(L)1)];1288 }1289 else {break;}1290 }1551 s = size(A); 1552 if (s > size(L)) 1553 {d = size(L); 1554 for (j = s; j > d; j) {Rt = insert(Rt,intvec(A[1..j]));} 1555 A = A[1..d]; 1556 } 1557 if (size(L) > s){L = L[1..s];} 1558 while (A <> L) 1559 {Rt = insert(Rt, intvec(A)); 1560 if (size(A) > 1) 1561 {A = A[1..(size(A)1)]; 1562 L = L[1..(size(L)1)]; 1563 } 1564 else {break;} 1565 } 1291 1566 } 1292 1567 return(Rt); … … 1313 1588 @* Otherwise the returned value may differ from the Kdimension. 1314 1589 @*  basering is a Letterplace ring. 1315 @*  mistletoes are stored as intvecs, as described in the overview1316 1590 EXAMPLE: example ivMis2Dim; shows examples 1317 1591 " … … 1321 1595 if (isInList(L,M) > 0) {print("1 is a mistletoe, therefore dim = 1"); return(1);} 1322 1596 int i,j,d,s; 1597 j = 1; 1323 1598 d = 1 + size(M[1]); 1324 1599 for (i = 1; i < size(M); i++) 1325 {j = 1; 1326 s = size(M[i]); if (s > size(M[i+1])){s = size(M[i+1]);} 1327 while ((M[i][j] == M[i+1][j]) && (j <= s)){j = j + 1;} 1328 d = d + size(M[i+1]) j + 1; 1600 {s = size(M[i]); if (s > size(M[i+1])){s = size(M[i+1]);} 1601 while ((M[i][j] == M[i+1][j]) && (j <= s)){j = j + 1;} 1602 d = d + size(M[i+1]) j + 1; 1329 1603 } 1330 1604 return(d); … … 1348 1622 PURPOSE:Orders a given set of mistletoes lexicographically 1349 1623 ASSUME:  basering is a Letterplace ring. 1350 @*  intvecs correspond to monomials, as explained in the overview 1624  intvecs correspond to monomials 1351 1625 NOTE:  This is preprocessing, it's not needed if the mistletoes are returned 1352 1626 @* from the sickle algorithm. … … 1374 1648 @* optional integer 1375 1649 RETURN: list, containing intvecs, the mistletoes of A/<L> 1376 PURPOSE:Computing the mistletoes for a given Groebner basis L , given by intmats1650 PURPOSE:Computing the mistletoes for a given Groebner basis L 1377 1651 ASSUME:  basering is a Letterplace ring. 1378 1652 @*  all rows of each intmat correspond to a Letterplace monomial 1379 @* as explained in the overview1380 1653 @*  if you specify a different degree bound degbound, 1381 @* degbound <= attrib(basering,uptodeg) should hold.1654 @* degbound <= attrib(basering,uptodeg) holds. 1382 1655 NOTE:  If degbound is set, a degree bound will be added. By default there 1383 1656 @* is no degree bound. … … 1457 1730 ASSUME:  basering is a Letterplace ring. 1458 1731 @*  all rows of each intmat correspond to a Letterplace monomial 1459 @* as explained in the overview1460 1732 @*  if you specify a different degree bound degbound, 1461 @* degbound <= attrib(basering,uptodeg) should hold.1733 @* degbound <= attrib(basering,uptodeg) holds. 1462 1734 NOTE:  If L is the list returned, then L[1] is an integer, L[2] is a list, 1463 1735 @* containing the mistletoes as intvecs. … … 1545 1817 ASSUME:  basering is a Letterplace ring. 1546 1818 @*  all rows of each intmat correspond to a Letterplace monomial 1547 @* as explained in the overview1548 1819 @*  if you specify a different degree bound degbound, 1549 @* degbound <= attrib(basering,uptodeg) should hold.1820 @* degbound <= attrib(basering,uptodeg) holds. 1550 1821 NOTE:  If L is the list returned, then L[1] is an intvec, L[2] is a list, 1551 1822 @* containing the mistletoes as intvecs. … … 1630 1901 RETURN: list 1631 1902 PURPOSE:Computing Kdimension and Hilbert series, starting with a lpideal 1632 ASSUME:  basering is a Letterplace ring. G is a Letterplace ideal.1903 ASSUME:  basering is a Letterplace ring. 1633 1904 @*  if you specify a different degree bound degbound, 1634 @* degbound <= attrib(basering,uptodeg) should hold.1905 @* degbound <= attrib(basering,uptodeg) holds. 1635 1906 NOTE:  If L is the list returned, then L[1] is an integer corresponding to the 1636 1907 @* dimension, L[2] is an intvec which contains the coefficients of the … … 1672 1943 RETURN: list 1673 1944 PURPOSE:Computing Kdimension, Hilbert series and mistletoes at once 1674 ASSUME:  basering is a Letterplace ring. G is a Letterplace ideal.1945 ASSUME:  basering is a Letterplace ring. 1675 1946 @*  if you specify a different degree bound degbound, 1676 @* degbound <= attrib(basering,uptodeg) should hold.1947 @* degbound <= attrib(basering,uptodeg) holds. 1677 1948 NOTE:  If L is the list returned, then L[1] is an integer, the Kdimension, 1678 1949 @* L[2] is an intvec, the Hilbert series and L[3] is an ideal, … … 1715 1986 RETURN: intvec, containing the coefficients of the Hilbert series 1716 1987 PURPOSE:Computing the Hilbert series 1717 ASSUME:  basering is a Letterplace ring. G is a Letterplace ideal.1988 ASSUME:  basering is a Letterplace ring. 1718 1989 @*  if you specify a different degree bound degbound, 1719 @* degbound <= attrib(basering,uptodeg) should hold.1990 @* degbound <= attrib(basering,uptodeg) holds. 1720 1991 NOTE:  If degbound is set, there will be a degree bound added. 0 means no 1721 1992 @* degree bound. Default: attrib(basering,uptodeg). … … 1753 2024 RETURN: int, 1 if Kdimension of the factor algebra is infinite, 0 otherwise 1754 2025 PURPOSE:Checking a factor algebra for finiteness of the Kdimension 1755 ASSUME:  basering is a Letterplace ring. G is a Letterplace ideal.2026 ASSUME:  basering is a Letterplace ring. 1756 2027 EXAMPLE: example lpDimCheck; shows examples 1757 2028 " … … 1781 2052 RETURN: int, the Kdimension of the factor algebra 1782 2053 PURPOSE:Computing the Kdimension of a factor algebra, given via an ideal 1783 ASSUME:  basering is a Letterplace ring . G is a Letterplace ideal.2054 ASSUME:  basering is a Letterplace ring 1784 2055 @*  if you specify a different degree bound degbound, 1785 @* degbound <= attrib(basering,uptodeg) should hold.2056 @* degbound <= attrib(basering,uptodeg) holds. 1786 2057 NOTE:  If degbound is set, there will be a degree bound added. 0 means no 1787 2058 @* degree bound. Default: attrib(basering, uptodeg). … … 1840 2111 RETURN: int, the Kdimension of the factor algebra 1841 2112 PURPOSE:Computing the Kdimension out of given mistletoes 1842 ASSUME:  basering is a Letterplace ring. G is a Letterplace ideal.2113 ASSUME:  basering is a Letterplace ring. 1843 2114 @*  M contains only monomials 1844 2115 NOTE:  The mistletoes have to be ordered lexicographically > OrdMisLex. … … 1864 2135 RETURN: ideal, containing the mistletoes, ordered lexicographically 1865 2136 PURPOSE:A given set of mistletoes is ordered lexicographically 1866 ASSUME:  basering is a Letterplace ring. G is a Letterplace ideal.2137 ASSUME:  basering is a Letterplace ring. 1867 2138 NOTE: This is preprocessing, it is not needed if the mistletoes are returned 1868 2139 @* from the sickle algorithm. … … 1885 2156 RETURN: ideal 1886 2157 PURPOSE:Computing the mistletoes of K[X]/<G> 1887 ASSUME:  basering is a Letterplace ring. G is a Letterplace ideal.2158 ASSUME:  basering is a Letterplace ring. 1888 2159 @*  if you specify a different degree bound degbound, 1889 @* degbound <= attrib(basering,uptodeg) should hold.2160 @* degbound <= attrib(basering,uptodeg) holds. 1890 2161 NOTE:  If degbound is set, there will be a degree bound added. 0 means no 1891 2162 @* degree bound. Default: attrib(basering,uptodeg). … … 1923 2194 RETURN: list 1924 2195 PURPOSE:Computing the Kdimension and the mistletoes 1925 ASSUME:  basering is a Letterplace ring. G is a Letterplace ideal.2196 ASSUME:  basering is a Letterplace ring. 1926 2197 @*  if you specify a different degree bound degbound, 1927 @* degbound <= attrib(basering,uptodeg) should hold.2198 @* degbound <= attrib(basering,uptodeg) holds. 1928 2199 NOTE:  If L is the list returned, then L[1] is an integer, the Kdimension, 1929 2200 @* L[2] is an ideal, the mistletoes. … … 1962 2233 RETURN: list 1963 2234 PURPOSE:Computing the Hilbert series and the mistletoes 1964 ASSUME:  basering is a Letterplace ring. G is a Letterplace ideal.2235 ASSUME:  basering is a Letterplace ring. 1965 2236 @*  if you specify a different degree bound degbound, 1966 @* degbound <= attrib(basering,uptodeg) should hold.2237 @* degbound <= attrib(basering,uptodeg) holds. 1967 2238 NOTE:  If L is the list returned, then L[1] is an intvec, corresponding to the 1968 2239 @* Hilbert series, L[2] is an ideal, the mistletoes. … … 2004 2275 RETURN: list 2005 2276 PURPOSE:Allowing the user to access all procs with one command 2006 ASSUME:  basering is a Letterplace ring. G is a Letterplace ideal.2277 ASSUME:  basering is a Letterplace ring. 2007 2278 @*  if you specify a different degree bound degbound, 2008 @* degbound <= attrib(basering,uptodeg) should hold.2279 @* degbound <= attrib(basering,uptodeg) holds. 2009 2280 NOTE: The returned object will always be a list, but the entries of the 2010 2281 @* returned list may be very different … … 2062 2333 sickle(G,0,0,1); // computes Hilbert series only 2063 2334 } 2335 2336 proc ivMaxIdeal(int l, int lonly) 2337 "USAGE: lpMaxIdeal(l, lonly); l an integer, lonly an integer 2338 RETURN: list 2339 PURPOSE: computes a list of free monomials in intvec presentation 2340 @* with length <= l 2341 @* if donly <> 0, only monomials of degree d are returned 2342 ASSUME:  basering is a Letterplace ring. 2343 NOTE: see also lpMaxIdeal() 2344 " 2345 { 2346 if (l < 0) { 2347 ERROR("l must not be negative") 2348 } 2349 list words; 2350 if (l == 0) { 2351 words = 0; 2352 return (words); 2353 } 2354 int lV = attrib(basering, "lV"); // variable count 2355 list prevWords; 2356 if (l > 1) { 2357 prevWords = ivMaxIdeal(l  1, lonly); 2358 } else { 2359 prevWords = 0; 2360 } 2361 for (int i = 1; i <= size(prevWords); i++) { 2362 if (size(prevWords[i]) >= l  1) { 2363 for (int j = 1; j <= lV; j++) { 2364 intvec word = prevWords[i]; 2365 word[l] = j; 2366 words = insert(words, word); 2367 kill word; 2368 } kill j; 2369 } 2370 } kill i; 2371 if (!lonly && l > 1) { 2372 words = prevWords + words; 2373 } 2374 return (words); 2375 } 2376 example { 2377 "EXAMPLE:"; echo = 2; 2378 ring r = 0,(a,b,c),dp; 2379 def R = makeLetterplaceRing(7); setring R; 2380 ivMaxIdeal(1,0); 2381 ivMaxIdeal(2,0); 2382 ivMaxIdeal(2,1); 2383 ivMaxIdeal(4,0); 2384 ivMaxIdeal(4,1); 2385 } 2386 2387 proc lpMaxIdeal(int d, int donly) 2388 "USAGE: lpMaxIdeal(d, donly); d an integer, donly an integer 2389 RETURN: ideal 2390 PURPOSE: computes a list of free monomials of degree at most d 2391 @* if donly <> 0, only monomials of degree d are returned 2392 ASSUME:  basering is a Letterplace ring. 2393 @*  d <= attrib(basering,uptodeg) holds. 2394 NOTE: analogous to maxideal(d) in the commutative case 2395 " 2396 { 2397 ivL2lpI(ivMaxIdeal(d, donly)); 2398 } 2399 example { 2400 "EXAMPLE:"; echo = 2; 2401 ring r = 0,(a,b,c),dp; 2402 def R = makeLetterplaceRing(7); setring R; 2403 lpMaxIdeal(1,0); 2404 lpMaxIdeal(2,0); 2405 lpMaxIdeal(2,1); 2406 lpMaxIdeal(4,0); 2407 lpMaxIdeal(4,1); 2408 } 2409 2410 proc monomialBasis(int d, int donly, ideal J) 2411 "USAGE: monomialBasis(d, donly, J); d, donly integers, J an ideal 2412 RETURN: ideal 2413 PURPOSE: computes a list of free monomials in a Letterplace 2414 @* basering R of degree at most d and not contained in <LM(J)> 2415 @* if donly <> 0, only monomials of degree d are returned 2416 ASSUME:  basering is a Letterplace ring. 2417 @*  d <= attrib(basering,uptodeg) holds. 2418 @*  J is a Groebner basis 2419 " 2420 { 2421 int nv = attrib(basering,"uptodeg"); 2422 if ((d>nv)  (d<0) ) 2423 { 2424 ERROR("incorrect degree"); 2425 } 2426 nv = attrib(basering,"lV"); // nvars 2427 if (d==0) 2428 { 2429 return(ideal(1)); 2430 } 2431 /* from now on d>=1 */ 2432 ideal I; 2433 if (size(J)==0) 2434 { 2435 I = lpMaxIdeal(d,donly); 2436 if (!donly) 2437 { 2438 // append 1 as the first element; d>=1 2439 I = 1, I; 2440 } 2441 return( I ); 2442 } 2443 // ok, Sickle misbehaves: have to remove all 2444 // elts from J of degree >d 2445 ideal JJ; 2446 int j; int sj = ncols(J); 2447 int cnt=0; 2448 for(j=1;j<=sj;j++) 2449 { 2450 if (deg(J[j]) <= d) 2451 { 2452 cnt++; 2453 JJ[cnt]=lead(J[j]); // only LMs are needed 2454 } 2455 } 2456 if (cnt==0) 2457 { 2458 // there are no elements in J of degree <= d 2459 // return free stuff and the 1 2460 I = monomialBasis(d, donly, std(0)); 2461 if (!donly) 2462 { 2463 I = 1, I; 2464 } 2465 return(I); 2466 } 2467 // from here on, Ibase is not zero 2468 ideal Ibase = lpMis2Base(lpSickle(JJ,d)); // the complete Kbasis modulo J up to d 2469 if (!donly) 2470 { 2471 // for not donly, give everything back 2472 // sort by DP starting with smaller terms 2473 Ibase = sort(Ibase,"Dp")[1]; 2474 return(Ibase); 2475 } 2476 /* !donly: pick out only monomials of degree d */ 2477 int i; int si = ncols(Ibase); 2478 cnt=0; 2479 I=0; 2480 for(i=1;i<=si;i++) 2481 { 2482 if (deg(Ibase[i]) == d) 2483 { 2484 cnt++; 2485 I[cnt]=Ibase[i]; 2486 } 2487 } 2488 kill Ibase; 2489 return(I); 2490 } 2491 example { 2492 "EXAMPLE:"; echo = 2; 2493 ring r = 0,(x,y),dp; 2494 def R = makeLetterplaceRing(7); setring R; 2495 ideal J = x(1)*y(2)*x(3)  y(1)*x(2)*y(3); 2496 option(redSB); option(redTail); 2497 J = letplaceGBasis(J); 2498 J; 2499 monomialBasis(2,1,std(0)); 2500 monomialBasis(2,0,std(0)); 2501 monomialBasis(3,1,J); 2502 monomialBasis(3,0,J); 2503 } 2504 2505 2506 /////////////////////////////////////////////////////////////////////////////// 2507 /* vl: stuff for conversion to Magma and to SD 2508 todo: doc, example 2509 */ 2510 static proc extractVars(r) 2511 { 2512 int i = 1; 2513 int j = 1; 2514 string candidate; 2515 list result = list(); 2516 for (i = 1; i<=nvars(r);i++) 2517 { 2518 candidate = string(var(i))[1,find(string(var(i)),"(")1]; 2519 if (!inList(result, candidate)) 2520 { 2521 result = insert(result,candidate,size(result)); 2522 } 2523 } 2524 return(result); 2525 } 2526 2527 static proc letterPlacePoly2MagmaString(poly h) 2528 { 2529 int pos; 2530 string s = string(h); 2531 while(find(s,"(")) 2532 { 2533 pos = find(s,"("); 2534 while(s[pos]!=")") 2535 { 2536 s = s[1,pos1]+s[pos+1,size(s)pos]; 2537 } 2538 if (size(s)!=pos) 2539 { 2540 s = s[1,pos1]+s[pos+1,size(s)pos]; // The last (")") 2541 } 2542 else 2543 { 2544 s = s[1,pos1]; 2545 } 2546 } 2547 return(s); 2548 } 2549 2550 static proc letterPlaceIdeal2SD(ideal I, int upToDeg) 2551 { 2552 int i; 2553 print("Don't forget to fill in the formal Data in the file"); 2554 string result = "<?xml version=\"1.0\"?>"+newline+"<FREEALGEBRA createdAt=\"\" createdBy=\"Singular\" id=\"FREEALGEBRA/\">"+newline; 2555 result = result + "<vars>"+string(extractVars(basering))+"</vars>"+newline; 2556 result = result + "<basis>"+newline; 2557 for (i = 1;i<=size(I);i++) 2558 { 2559 result = result + "<poly>"+letterPlacePoly2MagmaString(I[i])+"</poly>"+newline; 2560 } 2561 result = result + "</basis>"+newline; 2562 result = result + "<uptoDeg>"+ string(upToDeg)+"</uptoDeg>"+newline; 2563 result = result + "<Comment></Comment>"+newline; 2564 result = result + "<Version></Version>"+newline; 2565 result = result + "</FREEALGEBRA>"; 2566 return(result); 2567 } 2568 2064 2569 2065 2570 /////////////////////////////////////////////////////////////////////////////// … … 2098 2603 example lp2ivId; 2099 2604 example lpId2ivLi; 2100 } 2101 2102 2103 2104 2605 example lpSubstitute; 2606 } 2105 2607 2106 2608 /* 2107 Here are some examples one may try. Just copy them into your console. 2108 These are relations for braid groups, up to degree d: 2109 2110 2111 LIB "fpadim.lib"; 2112 ring r = 0,(x,y,z),dp; 2113 int d =10; // degree 2114 def R = makeLetterplaceRing(d); 2115 setring R; 2116 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), 2117 z(1)*x(2)*z(3)  y(1)*z(2)*x(3), x(1)*x(2)*x(3) + y(1)*y(2)*y(3) + 2118 z(1)*z(2)*z(3) + x(1)*y(2)*z(3); 2119 option(prot); 2120 option(redSB);option(redTail);option(mem); 2121 ideal J = system("freegb",I,d,3); 2122 lpDimCheck(J); 2123 sickle(J,1,1,1,d);//Computes mistletoes, Kdimension and the Hilbert series 2124 2125 2126 2127 LIB "fpadim.lib"; 2128 ring r = 0,(x,y,z),dp; 2129 int d =11; // degree 2130 def R = makeLetterplaceRing(d); 2131 setring R; 2132 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), 2133 z(1)*x(2)*z(3)  y(1)*z(2)*x(3), x(1)*x(2)*x(3) + y(1)*y(2)*y(3) + 2134 z(1)*z(2)*z(3) + x(1)*y(2)*z(3); 2135 option(prot); 2136 option(redSB);option(redTail);option(mem); 2137 ideal J = system("freegb",I,d,3); 2138 lpDimCheck(J); 2139 sickle(J,1,1,1,d); 2140 2141 2142 2143 LIB "fpadim.lib"; 2144 ring r = 0,(x,y,z),dp; 2145 int d = 6; // degree 2146 def R = makeLetterplaceRing(d); 2147 setring R; 2148 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), 2149 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); 2150 option(prot); 2151 option(redSB);option(redTail);option(mem); 2152 ideal J = system("freegb",I,d,3); 2153 lpDimCheck(J); 2154 sickle(J,1,1,1,d); 2609 Here are some examples one may try. Just copy them into your console. 2610 These are relations for braid groups, up to degree d: 2611 2612 LIB "fpadim.lib"; 2613 ring r = 0,(x,y,z),dp; 2614 int d =10; // degree 2615 def R = makeLetterplaceRing(d); 2616 setring R; 2617 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), 2618 z(1)*x(2)*z(3)  y(1)*z(2)*x(3), x(1)*x(2)*x(3) + y(1)*y(2)*y(3) + 2619 z(1)*z(2)*z(3) + x(1)*y(2)*z(3); 2620 option(prot); 2621 option(redSB);option(redTail);option(mem); 2622 ideal J = system("freegb",I,d,3); 2623 lpDimCheck(J); 2624 sickle(J,1,1,1,d);//Computes mistletoes, Kdimension and the Hilbert series 2625 2626 2627 2628 LIB "fpadim.lib"; 2629 ring r = 0,(x,y,z),dp; 2630 int d =11; // degree 2631 def R = makeLetterplaceRing(d); 2632 setring R; 2633 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), 2634 z(1)*x(2)*z(3)  y(1)*z(2)*x(3), x(1)*x(2)*x(3) + y(1)*y(2)*y(3) + 2635 z(1)*z(2)*z(3) + x(1)*y(2)*z(3); 2636 option(prot); 2637 option(redSB);option(redTail);option(mem); 2638 ideal J = system("freegb",I,d,3); 2639 lpDimCheck(J); 2640 sickle(J,1,1,1,d); 2641 2642 2643 2644 LIB "fpadim.lib"; 2645 ring r = 0,(x,y,z),dp; 2646 int d = 6; // degree 2647 def R = makeLetterplaceRing(d); 2648 setring R; 2649 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), 2650 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); 2651 option(prot); 2652 option(redSB);option(redTail);option(mem); 2653 ideal J = system("freegb",I,d,3); 2654 lpDimCheck(J); 2655 sickle(J,1,1,1,d); 2656 */ 2657 2658 /* 2659 Here are some examples, which can also be found in [studzins]: 2660 2661 // takes up to 880Mb of memory 2662 LIB "fpadim.lib"; 2663 ring r = 0,(x,y,z),dp; 2664 int d =10; // degree 2665 def R = makeLetterplaceRing(d); 2666 setring R; 2667 ideal I = 2668 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); 2669 option(prot); 2670 option(redSB);option(redTail);option(mem); 2671 ideal J = system("freegb",I,d,nvars(r)); 2672 lpDimCheck(J); 2673 sickle(J,1,1,1,d); // dimension is 24872 2674 2675 2676 LIB "fpadim.lib"; 2677 ring r = 0,(x,y,z),dp; 2678 int d =10; // degree 2679 def R = makeLetterplaceRing(d); 2680 setring R; 2681 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); 2682 option(prot); 2683 option(redSB);option(redTail);option(mem); 2684 ideal J = system("freegb",I,d,3); 2685 lpDimCheck(J); 2686 sickle(J,1,1,1,d); 2687 */ 2688 2689 2690 /* 2691 Example for computing GK dimension: 2692 returns a ring which contains an ideal I 2693 run gkDim(I) inside this ring and it should return 2n (the GK dimension 2694 of nth Weyl algebra including evaluation operators). 2695 2696 static proc createWeylEx(int n, int d) 2697 " 2698 " 2699 { 2700 int baseringdef; 2701 if (defined(basering)) // if a basering is defined, it should be saved for later use 2702 { 2703 def save = basering; 2704 baseringdef = 1; 2705 } 2706 ring r = 0,(d(1..n),x(1..n),e(1..n)),dp; 2707 def R = makeLetterplaceRing(d); 2708 setring R; 2709 ideal I; int i,j; 2710 2711 for (i = 1; i <= n; i++) 2712 { 2713 for (j = i+1; j<= n; j++) 2714 { 2715 I[size(I)+1] = lpMult(var(i),var(j)); 2716 } 2717 } 2718 2719 for (i = 1; i <= n; i++) 2720 { 2721 for (j = i+1; j<= n; j++) 2722 { 2723 I[size(I)+1] = lpMult(var(n+i),var(n+j)); 2724 } 2725 } 2726 for (i = 1; i <= n; i++) 2727 { 2728 for (j = 1; j<= n; j++) 2729 { 2730 I[size(I)+1] = lpMult(var(i),var(n+j)); 2731 } 2732 } 2733 for (i = 1; i <= n; i++) 2734 { 2735 for (j = 1; j<= n; j++) 2736 { 2737 I[size(I)+1] = lpMult(var(i),var(2*n+j)); 2738 } 2739 } 2740 for (i = 1; i <= n; i++) 2741 { 2742 for (j = 1; j<= n; j++) 2743 { 2744 I[size(I)+1] = lpMult(var(2*n+i),var(n+j)); 2745 } 2746 } 2747 for (i = 1; i <= n; i++) 2748 { 2749 for (j = 1; j<= n; j++) 2750 { 2751 I[size(I)+1] = lpMult(var(2*n+i),var(2*n+j)); 2752 } 2753 } 2754 I = simplify(I,2+4); 2755 I = letplaceGBasis(I); 2756 export(I); 2757 if (baseringdef == 1) {setring save;} 2758 return(R); 2759 } 2760 2761 proc TestGKAuslander3() 2762 { 2763 ring r = (0,q),(z,x,y),(dp(1),dp(2)); 2764 def R = makeLetterplaceRing(5); // constructs a Letterplace ring 2765 R; setring R; // sets basering to Letterplace ring 2766 ideal I; 2767 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); 2768 I = letplaceGBasis(I); 2769 lpGkDim(I); // must be 3 2770 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 2771 I = letplaceGBasis(I); // not finite BUT contains a poly in x,y only 2772 lpGkDim(I); // must be 4 2773 2774 ring r = 0,(y,x,z),dp; 2775 def R = makeLetterplaceRing(10); // constructs a Letterplace ring 2776 R; setring R; // sets basering to Letterplace ring 2777 ideal I; 2778 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 2779 I = letplaceGBasis(I); // computed as it would be homogenized; infinite 2780 poly p = x(1)*y(2)*y(3)*x(4)y(1)*x(2)*x(3)*y(4); 2781 lpNF(p, I); // 0 as expected 2782 2783 // with inverse of z 2784 ring r = 0,(iz,z,x,y),dp; 2785 def R = makeLetterplaceRing(11); // constructs a Letterplace ring 2786 R; setring R; // sets basering to Letterplace ring 2787 ideal I; 2788 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), 2789 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; 2790 I = letplaceGBasis(I); // 2791 setring r; 2792 def R2 = makeLetterplaceRing(23); // constructs a Letterplace ring 2793 setring R2; // sets basering to Letterplace ring 2794 ideal I = imap(R,I); 2795 lpGkDim(I); 2796 2797 2798 ring r = 0,(t,z,x,y),(dp(2),dp(2)); 2799 def R = makeLetterplaceRing(20); // constructs a Letterplace ring 2800 R; setring R; // sets basering to Letterplace ring 2801 ideal I; 2802 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), 2803 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 2804 I = letplaceGBasis(I); // computed as it would be homogenized; infinite 2805 LIB "elim.lib"; 2806 ideal Inoz = nselect(I,intvec(2,6,10,14,18,22,26,30)); 2807 for(int i=1; i<=20; i++) 2808 { 2809 Inoz=subst(Inoz,t(i),1); 2810 } 2811 ideal J = x(1)*y(2)*y(3)*x(4)y(1)*x(2)*x(3)*y(4); 2812 J = letplaceGBasis(J); 2813 2814 poly p = x(1)*y(2)*y(3)*x(4)y(1)*x(2)*x(3)*y(4); 2815 lpNF(p, I); // 0 as expected 2816 2817 ring r2 = 0,(x,y),dp; 2818 def R2 = makeLetterplaceRing(50); // constructs a Letterplace ring 2819 setring R2; 2820 ideal J = x(1)*y(2)*y(3)*x(4)y(1)*x(2)*x(3)*y(4); 2821 J = letplaceGBasis(J); 2822 } 2823 2155 2824 */ 2156 2825 2157 /* 2158 Here are some examples, which can also be found in [studzins]: 2159 2160 // takes up to 880Mb of memory 2161 LIB "fpadim.lib"; 2162 ring r = 0,(x,y,z),dp; 2163 int d =10; // degree 2164 def R = makeLetterplaceRing(d); 2165 setring R; 2166 ideal I = 2167 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); 2168 option(prot); 2169 option(redSB);option(redTail);option(mem); 2170 ideal J = system("freegb",I,d,nvars(r)); 2171 lpDimCheck(J); 2172 sickle(J,1,1,1,d); // dimension is 24872 2173 2174 2175 LIB "fpadim.lib"; 2176 ring r = 0,(x,y,z),dp; 2177 int d =10; // degree 2178 def R = makeLetterplaceRing(d); 2179 setring R; 2180 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); 2181 option(prot); 2182 option(redSB);option(redTail);option(mem); 2183 ideal J = system("freegb",I,d,3); 2184 lpDimCheck(J); 2185 sickle(J,1,1,1,d); 2186 */ 2826 2827 /* more tests : downup algebra A 2828 LIB "fpadim.lib"; 2829 ring r = (0,a,b,g),(x,y),Dp; 2830 def R = makeLetterplaceRing(6); // constructs a Letterplace ring 2831 setring R; 2832 poly F1 = g*x(1); 2833 poly F2 = g*y(1); 2834 ideal J = x(1)*x(2)*y(3)a*x(1)*y(2)*x(3)  b*y(1)*x(2)*x(3)  F1, 2835 x(1)*y(2)*y(3)a*y(1)*x(2)*y(3)  b*y(1)*y(2)*x(3)  F2; 2836 J = letplaceGBasis(J); 2837 lpGkDim(J); // 3 == correct 2838 2839 // downup algebra B 2840 LIB "fpadim.lib"; 2841 ring r = (0,a,b,g, p(1..7),q(1..7)),(x,y),Dp; 2842 def R = makeLetterplaceRing(6); // constructs a Letterplace ring 2843 setring R; 2844 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); 2845 int i; 2846 poly F1, F2; 2847 for(i=1;i<=7;i++) 2848 { 2849 F1 = F1 + p(i)*imn[i]; 2850 F2 = F2 + q(i)*imn[i]; 2851 } 2852 ideal J = x(1)*x(2)*y(3)a*x(1)*y(2)*x(3)  b*y(1)*x(2)*x(3)  F1, 2853 x(1)*y(2)*y(3)a*y(1)*x(2)*y(3)  b*y(1)*y(2)*x(3)  F2; 2854 J = letplaceGBasis(J); 2855 lpGkDim(J); // 3 == correct 2856 2857 */ 
Singular/LIB/freegb.lib
r44168a r3f58e0f 3 3 category="Noncommutative"; 4 4 info=" 5 LIBRARY: freegb.lib Compute twosided Groebner bases in free algebras via 6 @* letterplace 5 LIBRARY: freegb.lib Compute twosided Groebner bases in free algebras via letterplace approach 7 6 AUTHORS: Viktor Levandovskyy, viktor.levandovskyy@math.rwthaachen.de 8 @* Grischa Studzinski, grischa.studzinski@math.rwthaachen.de 9 10 OVERVIEW: For the theory, see chapter 'Letterplace' in the Singular Manual 7 Grischa Studzinski, grischa.studzinski@math.rwthaachen.de 8 9 OVERVIEW: For the theory, see chapter 'Letterplace' in the @sc{Singular} Manual 10 11 Support: Joint projects LE 2697/21 and KR 1907/31 of the Priority Programme SPP 1489: 12 'Algorithmische und Experimentelle Methoden in Algebra, Geometrie und Zahlentheorie' 13 of the German DFG 14 and Project II.6 of the transregional collaborative research centre 15 SFBTRR 195 'Symbolic Tools in Mathematics and their Application' of the German DFG 11 16 12 17 PROCEDURES: 13 makeLetterplaceRing(d); creates a ring with d blocks of shifted original 14 @* variables 15 letplaceGBasis(I); computes twosided Groebner basis of a letterplace ideal I 16 @* up to a degree bound 17 lpNF(f,I); normal form of f with respect to ideal I 18 freeGBasis(L, n); computes twosided Groebner basis of an ideal, encoded via 19 @* list L, up to degree n 18 makeLetterplaceRing(d); creates a ring with d blocks of shifted original variables 19 letplaceGBasis(I); computes twosided Groebner basis of a letterplace ideal I up to a degree bound 20 lpNF(f,I); twosided normal form of f with respect to ideal I 20 21 setLetterplaceAttributes(R,d,b); supplies ring R with the letterplace structure 21 22 freeGBasis(L, n); computes twosided Groebner basis of an ideal, encoded via list L, up to degree n 22 23 23 24 lpMult(f,g); letterplace multiplication of letterplace polynomials 24 25 shiftPoly(p,i); compute the ith shift of letterplace polynomial p 25 26 lpPower(f,n); natural power of a letterplace polynomial 26 lp2lstr(K, s); convert letterplace ideal to a list of modules 27 lst2str(L[, n]); convert a list (of modules) into polynomials in free algebra 28 mod2str(M[, n]); convert a module into a polynomial in free algebra 27 lieBracket(a,b[, N]); compute Lie bracket abba of two letterplace polynomials 28 29 lp2lstr(K, s); convert a letterplace ideal into a list of modules 30 lst2str(L[, n]); convert a list (of modules) into polynomials in free algebra via strings 31 mod2str(M[, n]); convert a module into a polynomial in free algebra via strings 29 32 vct2str(M[, n]); convert a vector into a word in free algebra 30 lieBracket(a,b[, N]); compute Lie bracket abba of two letterplace polynomials 31 serreRelations(A,z); compute the homogeneous part of Serre's relations 32 @* associated to a generalized Cartan matrix A 33 fullSerreRelations(A,N,C,P,d); compute the ideal of all Serre's relations 34 @* associated to a generalized Cartan matrix A 35 isVar(p); check whether p is a power of a single variable 33 34 serreRelations(A,z); compute the homogeneous part of Serre's relations associated to a generalized Cartan matrix A 35 fullSerreRelations(A,N,C,P,d); compute the ideal of all Serre's relations associated to a generalized Cartan matrix A 36 isVar(p); check whether p is a power of a single variable 36 37 ademRelations(i,j); compute the ideal of Adem relations for i<2j in char 0 37 38 … … 968 969 RETURN: ring 969 970 PURPOSE: creates a ring with the ordering, used in letterplace computations 970 NOTE: if h is given and nonzero, the pure homogeneous letterplace block 971 @* ordering will be used. 971 NOTE: h = 0 (default) : Dp ordering will be used 972 h = 2 : weights 1 used for all the variables, a tie breaker is a list of block of original ring 973 h = 1 : the pure homogeneous letterplace block ordering (applicable in the situation of homogeneous input ideals) will be used. 972 974 EXAMPLE: example makeLetterplaceRing; shows examples 973 975 " 974 976 { 975 int use_old_mlr= 0;977 int alternativeVersion = 0; 976 978 if ( size(#)>0 ) 977 979 { 978 if (( typeof(#[1]) == "int" )  ( typeof(#[1]) == "poly" ) ) 979 { 980 poly x = poly(#[1]); 981 if (x!=0) 982 { 983 use_old_mlr = 1; 984 } 985 } 986 } 987 if (use_old_mlr) 980 if (typeof(#[1]) == "int") 981 { 982 alternativeVersion = #[1]; 983 } 984 } 985 if (alternativeVersion == 1) 988 986 { 989 987 def @A = makeLetterplaceRing1(d); 990 988 } 991 else 992 { 993 def @A = makeLetterplaceRing2(d); 989 else { 990 if (alternativeVersion == 2) 991 { 992 def @A = makeLetterplaceRing2(d); 993 } 994 else { 995 def @A = makeLetterplaceRing4(d); 996 } 994 997 } 995 998 return(@A); … … 1205 1208 } 1206 1209 1210 static proc makeLetterplaceRing4(int d) 1211 "USAGE: makeLetterplaceRing2(d); d an integer 1212 RETURN: ring 1213 PURPOSE: creates a Letterplace ring with a Dp ordering, suitable for 1214 @* the use of nonhomogeneous letterplace 1215 NOTE: the matrix for the ordering looks as follows: first row is 1,1,...,1 1216 EXAMPLE: example makeLetterplaceRing2; shows examples 1217 " 1218 { 1219 1220 // ToDo future: inherit positive weights in the orig ring 1221 // complain on nonpositive ones 1222 1223 // d = up to degree, will be shifted to d+1 1224 if (d<1) {"bad d"; return(0);} 1225 1226 int uptodeg = d; int lV = nvars(basering); 1227 1228 int ppl = printlevelvoice+2; 1229 string err = ""; 1230 1231 int i,j,s; 1232 def save = basering; 1233 int D = d1; 1234 list LR = ringlist(save); 1235 list L, tmp, tmp2, tmp3; 1236 L[1] = LR[1]; // ground field 1237 L[4] = LR[4]; // quotient ideal 1238 tmp = LR[2]; // varnames 1239 s = size(LR[2]); 1240 for (i=1; i<=D; i++) 1241 { 1242 for (j=1; j<=s; j++) 1243 { 1244 tmp[i*s+j] = string(tmp[j])+"("+string(i+1)+")"; 1245 } 1246 } 1247 for (i=1; i<=s; i++) 1248 { 1249 tmp[i] = string(tmp[i])+"("+string(1)+")"; 1250 } 1251 L[2] = tmp; 1252 list OrigNames = LR[2]; 1253 1254 s = size(LR[3]); 1255 list ordering; 1256 ordering[1] = list("Dp",intvec(1: int(d*lV))); 1257 ordering[2] = LR[3][s]; // module ord to place at the very end 1258 LR[3] = ordering; 1259 1260 L[3] = LR[3]; 1261 attrib(L,"maxExp",1); 1262 def @R = ring(L); 1263 def @@R = setLetterplaceAttributes(@R,uptodeg,lV); 1264 return (@@R); 1265 } 1266 example 1267 { 1268 "EXAMPLE:"; echo = 2; 1269 ring r = 0,(x,y,z),(dp(1),dp(2)); 1270 def A = makeLetterplaceRing2(2); 1271 setring A; 1272 A; 1273 attrib(A,"isLetterplaceRing"); 1274 attrib(A,"uptodeg"); // degree bound 1275 attrib(A,"lV"); // number of variables in the main block 1276 } 1277 1207 1278 // P[s;sigma] approach 1208 1279 static proc makeLetterplaceRing3(int d) … … 1314 1385 attrib(A,"lV"); // number of variables in the main block 1315 1386 } 1316 1317 1318 1387 1319 1388 /* EXAMPLES: … … 2600 2669 if (i>N) 2601 2670 { 2602 ERROR("The total number of elements in input ideals must not exceed the dimension of the ground ring"); 2671 string s1="The total number of elements in input ideals"; 2672 string s2="must not exceed the dimension of the ground ring"; 2673 ERROR(s1+s2); 2603 2674 } 2604 2675 if (i < N) … … 3029 3100 */ 3030 3101 3031 //static 3032 proc lpMultX(poly f, poly g) 3102 static proc lpMultX(poly f, poly g) 3033 3103 { 3034 3104 /* multiplies two polys in a very general setting correctly */ … … 3083 3153 } 3084 3154 3085 // TODO:3086 3155 // multiply two letterplace polynomials, lpMult: done 3087 3156 // reduction/ Normalform? needs kernel stuff … … 3172 3241 //@* else there wouldn't be an dvec representation 3173 3242 3174 //Main procedure for the user3243 //Main procedure for the user 3175 3244 3176 3245 proc lpNF(poly p, ideal G) 3177 3246 "USAGE: lpNF(p,G); f letterplace polynomial, ideal I 3178 3247 RETURN: poly 3179 PURPOSE: computation of the normal form of p with respect to G3248 PURPOSE: computation of the normal form of p with respect to G 3180 3249 ASSUME: p is a Letterplace polynomial, G is a set Letterplace polynomials, 3181 3250 being a Letterplace Groebner basis (no check for this will be done) 3182 3251 NOTE: Strategy: take the smallest monomial wrt ordering for reduction 3183 @*For homogenous ideals the shift does not matter3184 @*For nonhomogenous ideals the first shift will be the smallest monomial3252  For homogenous ideals the shift does not matter 3253  For nonhomogenous ideals the first shift will be the smallest monomial 3185 3254 EXAMPLE: example lpNF; shows examples 3186 3255 " … … 3189 3258 G = sort(G)[1]; 3190 3259 list L = makeDVecI(G); 3191 return(normalize(lpNormalForm 1(p,G,L)));3260 return(normalize(lpNormalForm2(p,G,L))); 3192 3261 } 3193 3262 example … … 3214 3283 RETURN: list of intvecs 3215 3284 PURPOSE: convert G into a list of intvecs, corresponding to the exponent vector 3216 @*of the leading monomials of G3285 of the leading monomials of G 3217 3286 " 3218 3287 {int i; list L; … … 3220 3289 return(L); 3221 3290 } 3222 3223 3291 3224 3292 static proc delSupZero(intvec I) … … 3247 3315 } 3248 3316 3249 3250 3317 static proc delSupZeroList(list L) 3251 3318 "USUAGE:delSupZeroList(L); L a list, containing intvecs … … 3326 3393 } 3327 3394 3328 3329 3330 //the actual normalform procedure, if a user want not to presort the ideal, just make it not static 3331 3395 //the first normal form procedure, if a user want not to presort the ideal, just make it not static 3332 3396 3333 3397 static proc lpNormalForm1(poly p, ideal G, list L) … … 3358 3422 3359 3423 3424 // new VL; called from lpNF 3425 static proc lpNormalForm2(poly pp, ideal G, list L) 3426 "USUAGE:lpNormalForm2(p,G); 3427 RETURN:poly 3428 PURPOSE:computation of the normal form of p w.r.t. G 3429 ASSUME: p is a Letterplace polynomial, G is a set of Letterplace polynomials 3430 NOTE: Taking the first possible reduction 3431 " 3432 { 3433 poly one = 1; 3434 if ( (pp == 0)  (leadmonom(pp) == one) ) { return(pp); } 3435 poly p = pp; poly q; 3436 int i; int s; intvec V; 3437 while ( (p != 0) && (leadmonom(p) != one) ) 3438 { 3439 //"entered while with p="; p; 3440 V = makeDVec(delSupZero(leadexp(p))); 3441 i = 0; 3442 s = 1; 3443 //"look for divisor"; 3444 while ( (s == 1) && (i<size(L)) ) 3445 { 3446 i = i+1; 3447 s = dShiftDiv(V, L[i])[1]; 3448 } 3449 // now, out of here: either i=size(L) and s==1 => no reduction 3450 // otherwise: i<=size(L) and s!= 1 => reduction 3451 //"out of divisor search: s="; s; "i="; i; 3452 if (s != 1) 3453 { 3454 //"start reducing with G[i]:"; 3455 p = lpReduce(p,G[i],s); // lmreduction 3456 //"reduced to p="; p; 3457 } 3458 else 3459 { 3460 // ie no lmreduction possible; proceed with the tail reduction 3461 q = plead(p); 3462 p = lead(p); 3463 if (q!=0) 3464 { 3465 p = p + lpNormalForm2(q,G,L); 3466 } 3467 return(p); 3468 } 3469 } 3470 // out of while when p==0 or p == const 3471 return(p); 3472 } 3473 3474 3360 3475 3361 3476 … … 3521 3636 // // interface 3522 3637 3523 // proc whichshift(poly p, int numvars)3638 // static proc whichshift(poly p, int numvars) 3524 3639 // { 3525 3640 // // numvars = number of vars of the orig free algebra … … 3538 3653 3539 3654 // LIB "qhmoduli.lib"; 3540 // proc polyshift(poly p, int numvars)3655 // static proc polyshift(poly p, int numvars) 3541 3656 // { 3542 3657 // poly q = p; int i = 0; … … 3615 3730 lpMultX(a,b); // seems to work properly 3616 3731 } 3732 3733 /* THE FOLLOWING ARE UNDER DEVELOPMENT 3734 // copied following from freegb_wrkcp.lib by Karim Abou Zeid on 07.04.2017: 3735 // makeLetterplaceRingElim(int d) 3736 // makeLetterplaceRingNDO(int d) 3737 // setLetterplaceAttributesElim(def R, int uptodeg, int lV) 3738 // lpElimIdeal(ideal I) 3739 // makeLetterplaceRingWt(int d, intvec W) 3740 3741 static proc makeLetterplaceRingElim(int d) 3742 "USAGE: makeLetterplaceRingElim(d); d integers 3743 RETURN: ring 3744 PURPOSE: creates a ring with an elimination ordering 3745 NOTE: the matrix for the ordering looks as follows: first row is 1,..,0,1,0,.. 3746 @* then 0,1,0,...,0,0,1,0... and so on, lastly its lp 3747 @* this ordering is only correct if only polys with same shift are compared 3748 EXAMPLE: example makeLetterplaceRingElim; shows examples 3749 " 3750 { 3751 3752 // ToDo future: inherit positive weights in the orig ring 3753 // complain on nonpositive ones 3754 3755 // d = up to degree, will be shifted to d+1 3756 if (d<1) {"bad d"; return(0);} 3757 3758 int uptodeg = d; int lV = nvars(basering); 3759 3760 int ppl = printlevelvoice+2; 3761 string err = ""; 3762 3763 int i,j,s; intvec iV,iVl; 3764 def save = basering; 3765 int D = d1; 3766 list LR = ringlist(save); 3767 list L, tmp, tmp2, tmp3; 3768 L[1] = LR[1]; // ground field 3769 L[4] = LR[4]; // quotient ideal 3770 tmp = LR[2]; // varnames 3771 s = size(LR[2]); 3772 for (i=1; i<=D; i++) 3773 { 3774 for (j=1; j<=s; j++) 3775 { 3776 tmp[i*s+j] = string(tmp[j])+"("+string(i+1)+")"; 3777 } 3778 } 3779 for (i=1; i<=s; i++) 3780 { 3781 tmp[i] = string(tmp[i])+"("+string(1)+")"; 3782 } 3783 L[2] = tmp; 3784 L[3] = list(); 3785 list OrigNames = LR[2]; 3786 s = size(LR[3]); 3787 //creation of first block 3788 3789 if (s==2) 3790 { 3791 // not a blockord, 1 block + module ord 3792 tmp = LR[3][s]; // module ord 3793 for (i = 1; i <= lV; i++) 3794 { 3795 iV = (0: lV); 3796 iV[i] = 1; 3797 iVl = iV; 3798 for (j = 1; j <= D; j++) 3799 { iVl = iVl,iV; } 3800 L[3][i] = list("a",iVl); 3801 } 3802 // for (i=1; i<=d; i++) 3803 // { 3804 // LR[3][s1+i] = LR[3][1]; 3805 // } 3806 // LR[3][s+D] = tmp; 3807 //iV = (1:(d*lV)); 3808 L[3][lV+1] = list("lp",(1:(d*lV))); 3809 L[3][lV+2] = tmp; 3810 } 3811 else {ERROR("Please set the ordering of basering to dp");} 3812 // if (s>2) 3813 // { 3814 // // there are s1 blocks 3815 // int nb = s1; 3816 // tmp = LR[3][s]; // module ord to place at the very end 3817 // tmp2 = LR[3]; tmp2 = tmp2[1..nb]; 3818 // LR[3][1] = list("a",LTO); 3819 // //tmp3[1] = list("a",intvec(1: int(d*lV))); // degord, insert as the 1st 3820 // for (i=1; i<=d; i++) 3821 // { 3822 // tmp3 = tmp3 + tmp2; 3823 // } 3824 // tmp3 = tmp3 + list(tmp); 3825 // LR[3] = tmp3; 3826 // for (i=1; i<=d; i++) 3827 // { 3828 // for (j=1; j<=nb; j++) 3829 // { 3830 // // LR[3][i*nb+j+1]= LR[3][j]; 3831 // LR[3][i*nb+j+1]= tmp2[j]; 3832 // } 3833 // } 3834 // // size(LR[3]); 3835 // LR[3][(s1)*d+2] = tmp; 3836 // LR[3] = list("a",intvec(1: int(d*lV))) + LR[3]; // degord, insert as the 1st 3837 // remove everything behind nb*(D+1)+1 ? 3838 // tmp = LR[3]; 3839 // LR[3] = tmp[1..size(tmp)1]; 3840 // } 3841 // L[3] = LR[3]; 3842 def @R = ring(L); 3843 // setring @R; 3844 // int uptodeg = d; int lV = nvars(basering); // were defined before 3845 def @@R = setLetterplaceAttributesElim(@R,uptodeg,lV); 3846 return (@@R); 3847 } 3848 example 3849 { 3850 "EXAMPLE:"; echo = 2; 3851 ring r = 0,(x,y,z),lp; 3852 def A = makeLetterplaceRingElim(2); 3853 setring A; 3854 A; 3855 attrib(A,"isLetterplaceRing"); 3856 attrib(A,"uptodeg"); // degree bound 3857 attrib(A,"lV"); // number of variables in the main block 3858 } 3859 3860 3861 3862 static proc makeLetterplaceRingNDO(int d) 3863 "USAGE: makeLetterplaceRingNDO(d); d an integer 3864 RETURN: ring 3865 PURPOSE: creates a ring with a nondegree first ordering, suitable for 3866 @* the use of nonhomogeneous letterplace 3867 NOTE: the matrix for the ordering looks as follows: 3868 @* 'd' blocks of shifted original variables 3869 EXAMPLE: example makeLetterplaceRingNDO; shows examples 3870 " 3871 { 3872 3873 // ToDo future: inherit positive weights in the orig ring 3874 // complain on nonpositive ones 3875 3876 // d = up to degree, will be shifted to d+1 3877 if (d<1) {"bad d"; return(0);} 3878 3879 int uptodeg = d; int lV = nvars(basering); 3880 3881 int ppl = printlevelvoice+2; 3882 string err = ""; 3883 3884 int i,j,s; 3885 def save = basering; 3886 int D = d1; 3887 list LR = ringlist(save); 3888 list L, tmp, tmp2, tmp3; 3889 L[1] = LR[1]; // ground field 3890 L[4] = LR[4]; // quotient ideal 3891 tmp = LR[2]; // varnames 3892 s = size(LR[2]); 3893 for (i=1; i<=D; i++) 3894 { 3895 for (j=1; j<=s; j++) 3896 { 3897 tmp[i*s+j] = string(tmp[j])+"("+string(i+1)+")"; 3898 } 3899 } 3900 for (i=1; i<=s; i++) 3901 { 3902 tmp[i] = string(tmp[i])+"("+string(1)+")"; 3903 } 3904 L[2] = tmp; 3905 list OrigNames = LR[2]; 3906 // ordering: one 1..1 a above 3907 // ordering: d blocks of the ord on r 3908 // try to get whether the ord on r is blockord itself 3909 // TODO: make L(2) ordering! exponent is maximally 2 3910 s = size(LR[3]); 3911 if (s==2) 3912 { 3913 // not a blockord, 1 block + module ord 3914 tmp = LR[3][s]; // module ord 3915 for (i=1; i<=d; i++) 3916 { 3917 LR[3][i] = LR[3][1]; 3918 } 3919 // LR[3][s+D] = tmp; 3920 LR[3][d+1] = tmp; 3921 //LR[3][1] = list("a",intvec(1: int(d*lV))); // degord not wanted here 3922 } 3923 if (s>2) 3924 { 3925 // there are s1 blocks 3926 int nb = s1; 3927 tmp = LR[3][s]; // module ord to place at the very end 3928 tmp2 = LR[3]; tmp2 = tmp2[1..nb]; 3929 //tmp3[1] = list("a",intvec(1: int(d*lV))); // degord not wanted here 3930 for (i=1; i<=d; i++) 3931 { 3932 tmp3 = tmp3 + tmp2; 3933 } 3934 tmp3 = tmp3 + list(tmp); 3935 LR[3] = tmp3; 3936 // for (i=1; i<=d; i++) 3937 // { 3938 // for (j=1; j<=nb; j++) 3939 // { 3940 // // LR[3][i*nb+j+1]= LR[3][j]; 3941 // LR[3][i*nb+j+1]= tmp2[j]; 3942 // } 3943 // } 3944 // // size(LR[3]); 3945 // LR[3][(s1)*d+2] = tmp; 3946 // LR[3] = list("a",intvec(1: int(d*lV))) + LR[3]; // degord, insert as the 1st 3947 // remove everything behind nb*(D+1)+1 ? 3948 // tmp = LR[3]; 3949 // LR[3] = tmp[1..size(tmp)1]; 3950 } 3951 L[3] = LR[3]; 3952 def @R = ring(L); 3953 // setring @R; 3954 // int uptodeg = d; int lV = nvars(basering); // were defined before 3955 def @@R = setLetterplaceAttributes(@R,uptodeg,lV); 3956 return (@@R); 3957 } 3958 example 3959 { 3960 "EXAMPLE:"; echo = 2; 3961 ring r = 0,(x,y,z),lp; 3962 def A = makeLetterplaceRingNDO(2); 3963 setring A; 3964 A; 3965 attrib(A,"isLetterplaceRing"); 3966 attrib(A,"uptodeg"); // degree bound 3967 attrib(A,"lV"); // number of variables in the main block 3968 } 3969 3970 static proc setLetterplaceAttributesElim(def R, int uptodeg, int lV) 3971 "USAGE: setLetterplaceAttributesElim(R, d, b, eV); R a ring, b,d, eV integers 3972 RETURN: ring with special attributes set 3973 PURPOSE: sets attributes for a letterplace ring: 3974 @* 'isLetterplaceRing' = true, 'uptodeg' = d, 'lV' = b, 'eV' = eV, where 3975 @* 'uptodeg' stands for the degree bound, 3976 @* 'lV' for the number of variables in the block 0 3977 @* 'eV' for the number of elimination variables 3978 NOTE: Activate the resulting ring by using @code{setring} 3979 " 3980 { 3981 if (uptodeg*lV != nvars(R)) 3982 { 3983 ERROR("uptodeg and lV do not agree on the basering!"); 3984 } 3985 3986 3987 // Set letterplacespecific attributes for the output ring! 3988 attrib(R, "uptodeg", uptodeg); 3989 attrib(R, "lV", lV); 3990 attrib(R, "isLetterplaceRing", 1); 3991 attrib(R, "HasElimOrd", 1); 3992 return (R); 3993 } 3994 example 3995 { 3996 "EXAMPLE:"; echo = 2; 3997 ring r = 0,(x(1),y(1),x(2),y(2),x(3),y(3),x(4),y(4)),dp; 3998 def R = setLetterplaceAttributesElim(r, 4, 2, 1); setring R; 3999 attrib(R,"isLetterplaceRing"); 4000 lieBracket(x(1),y(1),2); 4001 } 4002 4003 4004 static proc lpElimIdeal(ideal I) 4005 " 4006 does not work for degree reasons (deg function does not work for lp rings > newone!) 4007 " 4008 { 4009 def lpring = attrib(basering,"isLetterplaceRing"); 4010 def lpEO = attrib(basering,"HasElimOrd"); 4011 if ( typeof(lpring)!="int" && typeof(lpEO)!="int") 4012 { 4013 ERROR("Ring is not a lpring with an elimination ordering"); 4014 } 4015 4016 //int nE = attrib(basering, "eV"); 4017 4018 return(letplaceGBasis(I)); 4019 } 4020 4021 4022 static proc makeLetterplaceRingWt(int d, intvec W) 4023 "USAGE: makeLetterplaceRingWt(d,W); d an integer, W a vector of positive integers 4024 RETURN: ring 4025 PURPOSE: creates a ring with a special ordering, suitable for 4026 @* the use of nonhomogeneous letterplace 4027 NOTE: the matrix for the ordering looks as follows: first row is W,W,W,... 4028 @* then there come 'd' blocks of shifted original variables 4029 EXAMPLE: example makeLetterplaceRing2; shows examples 4030 " 4031 { 4032 4033 // ToDo future: inherit positive weights in the orig ring 4034 // complain on nonpositive ones 4035 4036 // d = up to degree, will be shifted to d+1 4037 if (d<1) {"bad d"; return(0);} 4038 4039 int uptodeg = d; int lV = nvars(basering); 4040 4041 //check weightvector 4042 if (size(W) <> lV) {"bad weights"; return(0);} 4043 4044 int i; 4045 for (i = 1; i <= size(W); i++) {if (W[i] < 0) {"bad weights"; return(0);}} 4046 intvec Wt = W; 4047 for (i = 2; i <= d; i++) {Wt = Wt, W;} 4048 kill i; 4049 4050 int ppl = printlevelvoice+2; 4051 string err = ""; 4052 4053 int i,j,s; 4054 def save = basering; 4055 int D = d1; 4056 list LR = ringlist(save); 4057 list L, tmp, tmp2, tmp3; 4058 L[1] = LR[1]; // ground field 4059 L[4] = LR[4]; // quotient ideal 4060 tmp = LR[2]; // varnames 4061 s = size(LR[2]); 4062 for (i=1; i<=D; i++) 4063 { 4064 for (j=1; j<=s; j++) 4065 { 4066 tmp[i*s+j] = string(tmp[j])+"("+string(i+1)+")"; 4067 } 4068 } 4069 for (i=1; i<=s; i++) 4070 { 4071 tmp[i] = string(tmp[i])+"("+string(1)+")"; 4072 } 4073 L[2] = tmp; 4074 list OrigNames = LR[2]; 4075 // ordering: one 1..1 a above 4076 // ordering: d blocks of the ord on r 4077 // try to get whether the ord on r is blockord itself 4078 // TODO: make L(2) ordering! exponent is maximally 2 4079 s = size(LR[3]); 4080 if (s==2) 4081 { 4082 // not a blockord, 1 block + module ord 4083 tmp = LR[3][s]; // module ord 4084 for (i=1; i<=d; i++) 4085 { 4086 LR[3][s1+i] = LR[3][1]; 4087 } 4088 // LR[3][s+D] = tmp; 4089 LR[3][s+1+D] = tmp; 4090 LR[3][1] = list("a",Wt); // degord 4091 } 4092 if (s>2) 4093 { 4094 // there are s1 blocks 4095 int nb = s1; 4096 tmp = LR[3][s]; // module ord to place at the very end 4097 tmp2 = LR[3]; tmp2 = tmp2[1..nb]; 4098 tmp3[1] = list("a",Wt); // degord, insert as the 1st 4099 for (i=1; i<=d; i++) 4100 { 4101 tmp3 = tmp3 + tmp2; 4102 } 4103 tmp3 = tmp3 + list(tmp); 4104 LR[3] = tmp3; 4105 4106 } 4107 L[3] = LR[3]; 4108 def @R = ring(L); 4109 // setring @R; 4110 // int uptodeg = d; int lV = nvars(basering); // were defined before 4111 def @@R = setLetterplaceAttributes(@R,uptodeg,lV); 4112 return (@@R); 4113 } 4114 example 4115 { 4116 "EXAMPLE:"; echo = 2; 4117 ring r = 0,(x,y,z),(dp(1),dp(2)); 4118 def A = makeLetterplaceRingWt(2,intvec(1,2,3)); 4119 setring A; 4120 A; 4121 attrib(A,"isLetterplaceRing"); 4122 attrib(A,"uptodeg"); // degree bound 4123 attrib(A,"lV"); // number of variables in the main block 4124 } 4125 */
Note: See TracChangeset
for help on using the changeset viewer.