Changeset 5edf31 in git
- Timestamp:
- Dec 8, 2017, 4:44:05 PM (6 years ago)
- Branches:
- (u'spielwiese', '5b153614cbc72bfa198d75b1e9e33dab2645d9fe')
- Children:
- 704cbaecf6b62ba8be6484ad4578145ccf201ade
- Parents:
- a9ce913e25cd572600cea3656d41a7ecf2d8c146
- Location:
- Singular/LIB
- Files:
-
- 3 edited
Legend:
- Unmodified
- Added
- Removed
-
Singular/LIB/fpadim.lib
ra9ce91 r5edf31 9 9 10 10 Support: Joint projects LE 2697/2-1 and KR 1907/3-1 of the Priority Programme SPP 1489: 11 @* 'Algorithmische und Experimentelle Methoden in Algebra, Geometrie und Zahlentheorie' 12 @* of the German DFG 13 14 OVERVIEW: Given the free algebra A = K<x_1,...,x_n> and a (finite) Groebner basis 15 @* GB = {g_1,..,g_w}, one is interested in the K-dimension and in the 16 @* explicit K-basis of A/<GB>. 17 @* Therefore one is interested in the following data: 18 @* - the Ufnarovskij graph induced by GB 19 @* - the mistletoes of A/<GB> 20 @* - the K-dimension of A/<GB> 21 @* - the Hilbert series of A/<GB> 22 @* 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 SFB-TRR 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 17 GB = {g_1,..,g_w}, one is interested in the K-dimension and in the 18 explicit K-basis of A/<GB>. 19 Therefore one is interested in the following data: 20 - the Ufnarovskij graph induced by GB 21 - the mistletoes of A/<GB> (special monomials in a basis) 22 - the K-dimension of A/<GB> 23 - the Hilbert series of A/<GB> 24 23 25 @* The Ufnarovskij graph is used to determine whether A/<GB> has finite 24 26 @* K-dimension. One has to check if the graph contains cycles. … … 41 43 @* represented by its number, so variable one is represented as 1, 42 44 @* variable two as 2 and so on. The monomial x_1*x_3*x_2 for example will 43 @* be stored as (1,3,2). Multiplication is concatenation. Note that the re44 @* is no algorithm for computing the normal form yet, but for our case it45 @* is not needed. Note that the name fpadim.lib is short for dimensions of45 @* 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 46 48 @* finite presented algebras. 47 49 @* … … 56 58 57 59 ASSUMPTIONS: 58 @*- basering is always a Letterplace ring59 @*- all intvecs correspond to Letterplace monomials60 @* - if you specify a different degree bound d, 61 d <= attrib(basering,uptodeg) holds 62 @*In the procedures below, 'iv' stands for intvec representation60 - 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 63 65 and 'lp' for the letterplace representation of monomials 64 66 65 67 PROCEDURES: 66 68 67 lpGkDim(G); computes the Gelfand Kirillov dimension of A/<G>68 69 ivDHilbert(L,n[,d]); computes the K-dimension and the Hilbert series 69 70 ivDHilbertSickle(L,n[,d]); computes mistletoes, K-dimension and Hilbert series … … 90 91 lpSickleDim(G[,d,n]); computes the mistletoes and the K-dimension of A/<G> 91 92 sickle(G[,m,d,h]); can be used to access all lp main procedures 92 93 93 94 94 ivL2lpI(L); transforms a list of intvecs into an ideal of lp monomials … … 2333 2333 2334 2334 /////////////////////////////////////////////////////////////////////////////// 2335 /* vl: newstuff for conversion to Magma and to SD2335 /* vl: stuff for conversion to Magma and to SD 2336 2336 todo: doc, example 2337 2337 */ 2338 proc extractVars(r)2338 static proc extractVars(r) 2339 2339 { 2340 2340 int i = 1; … … 2353 2353 } 2354 2354 2355 proc letterPlacePoly2MagmaString(poly h)2355 static proc letterPlacePoly2MagmaString(poly h) 2356 2356 { 2357 2357 int pos; … … 2376 2376 } 2377 2377 2378 proc letterPlaceIdeal2SD(ideal I, int upToDeg)2378 static proc letterPlaceIdeal2SD(ideal I, int upToDeg) 2379 2379 { 2380 2380 int i; … … 2431 2431 example lp2ivId; 2432 2432 example lpId2ivLi; 2433 example lpGkDim;2434 example lpGlDimBound;2435 2433 example lpSubstitute; 2436 2434 } … … 2525 2523 of n-th Weyl algebra including evaluation operators). 2526 2524 2527 proc createWeylEx(int n, int d)2525 static proc createWeylEx(int n, int d) 2528 2526 " 2529 2527 " -
Singular/LIB/fpaprops.lib
ra9ce91 r5edf31 6 6 AUTHORS: Karim Abou Zeid, karim.abou.zeid at rwth-aachen.de 7 7 8 Support ed bythe transregional collaborative research centre8 Support: Project II.6 in the transregional collaborative research centre 9 9 SFB-TRR 195 'Symbolic Tools in Mathematics and their Application' of the German DFG 10 10 11 OVERVIEW: 11 12 Algorithms for computing various properties of quotient algebras in the letterplace case. … … 14 15 Huishi Li: Groebner bases in ring theory. World Scientific, 2010. 15 16 16 SEE ALSO: fpadim .lib, freegb.lib,17 SEE ALSO: fpadim_lib, freegb_lib 17 18 18 19 PROCEDURES: … … 22 23 lpGkDim(<GB>); compute the Gelfand Kirillov dimension of A/<GB> 23 24 lpGlDimBound(<GB>); compute an upper bound for the global dimension of A/<GB> 24 lpSubstitute(); substitute variable with polynom s25 lpSubstitute(); substitute variable with polynomials 25 26 lpCalcSubstDegBound(); utility for lpSubstitute 26 27 lpCalcSubstDegBounds(); utility for lpSubstitute … … 196 197 PURPOSE: Check whether R/<G> is semi prime, where R is the basering 197 198 ASSUME: - basering is a Letterplace ring 198 @*- G is a Groebner basis199 - G is a Groebner basis 199 200 " 200 201 { … … 295 296 PURPOSE: Check whether R/<G> is prime, where R is the basering 296 297 ASSUME: - basering is a Letterplace ring 297 @*- G is a Groebner basis298 - G is a Groebner basis 298 299 " 299 300 { … … 368 369 "USAGE: existsRoute(G,v,u); G a graph, v and u vertices 369 370 NOTE: don't pass anything to # (internal use for recursion) 370 @*routes always have at least one edge371 routes always have at least one edge 371 372 " 372 373 { … … 682 683 RETURN: intmat 683 684 PURPOSE: Constructs the Ufnarovskij graph induced by G 684 @*the adjacency matrix of the Ufnarovskij graph induced by G685 the adjacency matrix of the Ufnarovskij graph induced by G 685 686 ASSUME: - basering is a Letterplace ring 686 @*- G are the leading monomials of a Groebner basis687 - G are the leading monomials of a Groebner basis 687 688 " 688 689 { … … 792 793 proc lpGkDim(ideal G, list#) 793 794 "USAGE: lpGkDim(G); G an ideal in a letterplace ring, method an 794 @*optional integer. method = 0 uses the Ufnarovskij Graph795 @*and method = 1 uses the Graph of normal words to determine796 @*the Gelfand Kirillov dimension795 optional integer. method = 0 uses the Ufnarovskij Graph 796 and method = 1 uses the Graph of normal words to determine 797 the Gelfand Kirillov dimension 797 798 RETURN: int 798 799 PURPOSE: Determines the Gelfand Kirillov dimension of A/<G> 799 @*-1 means it is positive infinite800 -1 means it is positive infinite 800 801 ASSUME: - basering is a Letterplace ring 801 802 - G is a Groebner basis … … 837 838 EXAMPLE: example lpGlDimBound; shows example 838 839 NOTE: if I = LM(I), then the global dimension is equal the Gelfand 839 @*Kirillov dimension if it is finite840 @*Global dimension should be 0 for A/G = K and 1 for A/G = K<x1...xn>840 Kirillov dimension if it is finite 841 Global dimension should be 0 for A/G = K and 1 for A/G = K<x1...xn> 841 842 " 842 843 { … … 1015 1016 proc lpSubstitute(poly f, ideal s1, ideal s2, list #) 1016 1017 "USAGE: lpSubstitute(f,s1,s2[,G]); f letterplace polynomial, s1 list (ideal) of variables 1017 @*to replace, s2 list (ideal) of polynomials to replace with, G optional ideal to1018 @*reduce with.1018 to replace, s2 list (ideal) of polynomials to replace with, G optional ideal to 1019 reduce with. 1019 1020 RETURN: poly, the substituted polynomial 1020 1021 ASSUME: - basering is a Letterplace ring 1021 @*- G is a groebner basis,1022 @*- the current ring has a sufficient degbound (can be calculated with1023 @*lpCalcSubstDegBound())1022 - G is a groebner basis, 1023 - the current ring has a sufficient degbound (can be calculated with 1024 lpCalcSubstDegBound()) 1024 1025 EXAMPLE: example lpSubstitute; shows examples 1025 1026 " … … 1121 1122 proc lpCalcSubstDegBound(poly f, ideal s1, ideal s2) 1122 1123 "USAGE: lpCalcSubstDegBound(f,s1,s2); f letterplace polynomial, s1 list (ideal) of variables 1123 @*to replace, s2 list (ideal) of polynomials to replace with1124 to replace, s2 list (ideal) of polynomials to replace with 1124 1125 RETURN: int, the min degbound required to perform the substitution 1125 1126 ASSUME: - basering is a Letterplace ring … … 1157 1158 proc lpCalcSubstDegBounds(ideal I, ideal s1, ideal s2) 1158 1159 "USAGE: lpCalcSubstDegBounds(I,s1,s2); I list (ideal) of letterplace polynomials, s1 list (ideal) 1159 @*of variables to replace, s2 list (ideal) of polynomials to replace with1160 of variables to replace, s2 list (ideal) of polynomials to replace with 1160 1161 RETURN: int, the min degbound required to perform all of the substitutions 1161 1162 ASSUME: - basering is a Letterplace ring -
Singular/LIB/freegb.lib
ra9ce91 r5edf31 3 3 category="Noncommutative"; 4 4 info=" 5 LIBRARY: freegb.lib Compute two-sided Groebner bases in free algebras via 6 @* letterplace 5 LIBRARY: freegb.lib Compute two-sided Groebner bases in free algebras via letterplace approach 7 6 AUTHORS: Viktor Levandovskyy, viktor.levandovskyy@math.rwth-aachen.de 8 @*Grischa Studzinski, grischa.studzinski@math.rwth-aachen.de7 Grischa Studzinski, grischa.studzinski@math.rwth-aachen.de 9 8 10 9 OVERVIEW: For the theory, see chapter 'Letterplace' in the @sc{Singular} Manual 11 10 12 11 PROCEDURES: 13 makeLetterplaceRing(d); creates a ring with d blocks of shifted original 14 @* variables 15 letplaceGBasis(I); computes two-sided 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 two-sided Groebner basis of an ideal, encoded via 19 @* list L, up to degree n 12 makeLetterplaceRing(d); creates a ring with d blocks of shifted original variables 13 letplaceGBasis(I); computes two-sided Groebner basis of a letterplace ideal I up to a degree bound 14 lpNF(f,I); two-sided normal form of f with respect to ideal I 20 15 setLetterplaceAttributes(R,d,b); supplies ring R with the letterplace structure 21 16 freeGBasis(L, n); computes two-sided Groebner basis of an ideal, encoded via list L, up to degree n 22 17 23 18 lpMult(f,g); letterplace multiplication of letterplace polynomials 24 19 shiftPoly(p,i); compute the i-th shift of letterplace polynomial p 25 20 lpPower(f,n); natural power of a letterplace polynomial 26 lp2lstr(K, s); convert letter-place 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 21 lieBracket(a,b[, N]); compute Lie bracket ab-ba of two letterplace polynomials 22 23 lp2lstr(K, s); convert a letterplace ideal into a list of modules 24 lst2str(L[, n]); convert a list (of modules) into polynomials in free algebra via strings 25 mod2str(M[, n]); convert a module into a polynomial in free algebra via strings 29 26 vct2str(M[, n]); convert a vector into a word in free algebra 30 lieBracket(a,b[, N]); compute Lie bracket ab-ba 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 27 28 serreRelations(A,z); compute the homogeneous part of Serre's relations associated to a generalized Cartan matrix A 29 fullSerreRelations(A,N,C,P,d); compute the ideal of all Serre's relations associated to a generalized Cartan matrix A 30 isVar(p); check whether p is a power of a single variable 36 31 ademRelations(i,j); compute the ideal of Adem relations for i<2j in char 0 37 lpDelVar(); delete a variable from the current Letterplace ring38 32 39 33 SEE ALSO: fpadim_lib, LETTERPLACE … … 1322 1316 list LR = ringlist(basering); 1323 1317 1324 if (!(index >= 1 && index <= lV)) { return (basering) } // invalid index1318 if (!(index >= 1 && index <= lV)) { return (basering); } // invalid index 1325 1319 1326 1320 // remove frome the variable list … … 1357 1351 return (R); 1358 1352 } 1359 1360 1353 example 1354 { 1355 "EXAMPLE:"; echo = 2; 1356 ring r = 0,(x,y,z),dp; 1357 def A = makeLetterplaceRing(3); 1358 setring A; A; 1359 def R = lpDelVar(2); setring R; R; 1360 } 1361 1361 1362 1362 /* EXAMPLES: … … 2643 2643 if (i>N) 2644 2644 { 2645 ERROR("The total number of elements in input ideals must not exceed the dimension of the ground ring"); 2645 string s1="The total number of elements in input ideals"; 2646 string s2="must not exceed the dimension of the ground ring"; 2647 ERROR(s1+s2); 2646 2648 } 2647 2649 if (i < N) … … 3072 3074 */ 3073 3075 3074 //static 3075 proc lpMultX(poly f, poly g) 3076 static proc lpMultX(poly f, poly g) 3076 3077 { 3077 3078 /* multiplies two polys in a very general setting correctly */ … … 3126 3127 } 3127 3128 3128 // TODO:3129 3129 // multiply two letterplace polynomials, lpMult: done 3130 3130 // reduction/ Normalform? needs kernel stuff … … 3215 3215 //@* else there wouldn't be an dvec representation 3216 3216 3217 //Main procedure for the user3217 //Main procedure for the user 3218 3218 3219 3219 proc lpNF(poly p, ideal G) … … 3224 3224 being a Letterplace Groebner basis (no check for this will be done) 3225 3225 NOTE: Strategy: take the smallest monomial wrt ordering for reduction 3226 @*For homogenous ideals the shift does not matter3227 @*For non-homogenous ideals the first shift will be the smallest monomial3226 - For homogenous ideals the shift does not matter 3227 - For non-homogenous ideals the first shift will be the smallest monomial 3228 3228 EXAMPLE: example lpNF; shows examples 3229 3229 " … … 3257 3257 RETURN: list of intvecs 3258 3258 PURPOSE: convert G into a list of intvecs, corresponding to the exponent vector 3259 @*of the leading monomials of G3259 of the leading monomials of G 3260 3260 " 3261 3261 {int i; list L; … … 3263 3263 return(L); 3264 3264 } 3265 3266 3265 3267 3266 static proc delSupZero(intvec I) … … 3290 3289 } 3291 3290 3292 3293 3291 static proc delSupZeroList(list L) 3294 3292 "USUAGE:delSupZeroList(L); L a list, containing intvecs … … 3369 3367 } 3370 3368 3371 3372 3373 //the actual normalform procedure, if a user want not to presort the ideal, just make it not static 3374 3369 //the first normal form procedure, if a user want not to presort the ideal, just make it not static 3375 3370 3376 3371 static proc lpNormalForm1(poly p, ideal G, list L) … … 3401 3396 3402 3397 3403 // new VL 3404 proc lpNormalForm2(poly pp, ideal G, list L)3398 // new VL; called from lpNF 3399 static proc lpNormalForm2(poly pp, ideal G, list L) 3405 3400 "USUAGE:lpNormalForm2(p,G); 3406 3401 RETURN:poly 3407 PURPOSE:computation of the normal form of p w.r.t. G3402 PURPOSE:computation of the normal form of p w.r.t. G 3408 3403 ASSUME: p is a Letterplace polynomial, G is a set of Letterplace polynomials 3409 3404 NOTE: Taking the first possible reduction … … 3615 3610 // // interface 3616 3611 3617 // proc whichshift(poly p, int numvars)3612 // static proc whichshift(poly p, int numvars) 3618 3613 // { 3619 3614 // // numvars = number of vars of the orig free algebra … … 3632 3627 3633 3628 // LIB "qhmoduli.lib"; 3634 // proc polyshift(poly p, int numvars)3629 // static proc polyshift(poly p, int numvars) 3635 3630 // { 3636 3631 // poly q = p; int i = 0; … … 3710 3705 } 3711 3706 3712 3707 /* THE FOLLOWING IS UNDER DEVELOPMENT 3713 3708 // copied following from freegb_wrkcp.lib by Karim Abou Zeid on 07.04.2017: 3714 // procmakeLetterplaceRingElim(int d)3715 // procmakeLetterplaceRingNDO(int d)3716 // procsetLetterplaceAttributesElim(def R, int uptodeg, int lV)3717 // proclpElimIdeal(ideal I)3718 // procmakeLetterplaceRingWt(int d, intvec W)3719 3720 proc makeLetterplaceRingElim(int d)3709 // makeLetterplaceRingElim(int d) 3710 // makeLetterplaceRingNDO(int d) 3711 // setLetterplaceAttributesElim(def R, int uptodeg, int lV) 3712 // lpElimIdeal(ideal I) 3713 // makeLetterplaceRingWt(int d, intvec W) 3714 3715 static proc makeLetterplaceRingElim(int d) 3721 3716 "USAGE: makeLetterplaceRingElim(d); d integers 3722 3717 RETURN: ring … … 3839 3834 3840 3835 3841 proc makeLetterplaceRingNDO(int d)3836 static proc makeLetterplaceRingNDO(int d) 3842 3837 "USAGE: makeLetterplaceRingNDO(d); d an integer 3843 3838 RETURN: ring … … 3947 3942 } 3948 3943 3949 proc setLetterplaceAttributesElim(def R, int uptodeg, int lV)3944 static proc setLetterplaceAttributesElim(def R, int uptodeg, int lV) 3950 3945 "USAGE: setLetterplaceAttributesElim(R, d, b, eV); R a ring, b,d, eV integers 3951 3946 RETURN: ring with special attributes set … … 3981 3976 3982 3977 3983 proc lpElimIdeal(ideal I)3978 static proc lpElimIdeal(ideal I) 3984 3979 " 3985 3980 does not work for degree reasons (deg function does not work for lp rings -> newone!) … … 3999 3994 4000 3995 4001 proc makeLetterplaceRingWt(int d, intvec W)3996 static proc makeLetterplaceRingWt(int d, intvec W) 4002 3997 "USAGE: makeLetterplaceRingWt(d,W); d an integer, W a vector of positive integers 4003 3998 RETURN: ring … … 4102 4097 attrib(A,"lV"); // number of variables in the main block 4103 4098 } 4099 */
Note: See TracChangeset
for help on using the changeset viewer.