Changeset 5edf31 in git


Ignore:
Timestamp:
Dec 8, 2017, 4:44:05 PM (6 years ago)
Author:
Karim Abou Zeid <karim23697@…>
Branches:
(u'spielwiese', '5b153614cbc72bfa198d75b1e9e33dab2645d9fe')
Children:
704cbaecf6b62ba8be6484ad4578145ccf201ade
Parents:
a9ce913e25cd572600cea3656d41a7ecf2d8c146
Message:
Add changes from levandov
Location:
Singular/LIB
Files:
3 edited

Legend:

Unmodified
Added
Removed
  • Singular/LIB/fpadim.lib

    ra9ce91 r5edf31  
    99
    1010Support: 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'
     12of the German DFG
     13and Project II.6 of the transregional collaborative research centre
     14SFB-TRR 195 'Symbolic Tools in Mathematics and their Application' of the German DFG
     15
     16OVERVIEW: 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
    2325@*      The Ufnarovskij graph is used to determine whether A/<GB> has finite
    2426@*      K-dimension. One has to check if the graph contains cycles.
     
    4143@*      represented by its number, so variable one is represented as 1,
    4244@*      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 there
    44 @*      is no algorithm for computing the normal form yet, but for our case it
    45 @*      is not needed. Note that the name fpadim.lib is short for dimensions of
     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
    4648@*      finite presented algebras.
    4749@*
     
    5658
    5759ASSUMPTIONS:
    58 @* - basering is always a Letterplace ring
    59 @* - all intvecs correspond to Letterplace monomials
    60 @* - if you specify a different degree bound d,
    61 d <= attrib(basering,uptodeg) holds
    62 @* In the procedures below, 'iv' stands for intvec representation
     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
     64In the procedures below, 'iv' stands for intvec representation
    6365and 'lp' for the letterplace representation of monomials
    6466
    6567PROCEDURES:
    6668
    67 lpGkDim(G);                        computes the Gelfand Kirillov dimension of A/<G>
    6869ivDHilbert(L,n[,d]);       computes the K-dimension and the Hilbert series
    6970ivDHilbertSickle(L,n[,d]); computes mistletoes, K-dimension and Hilbert series
     
    9091lpSickleDim(G[,d,n]);      computes the mistletoes and the K-dimension of A/<G>
    9192sickle(G[,m,d,h]);         can be used to access all lp main procedures
    92 
    9393
    9494ivL2lpI(L);           transforms a list of intvecs into an ideal of lp monomials
     
    23332333
    23342334///////////////////////////////////////////////////////////////////////////////
    2335 /* vl: new stuff for conversion to Magma and to SD
     2335/* vl: stuff for conversion to Magma and to SD
    23362336todo: doc, example
    23372337 */
    2338 proc extractVars(r)
     2338static proc extractVars(r)
    23392339{
    23402340  int i = 1;
     
    23532353}
    23542354
    2355 proc letterPlacePoly2MagmaString(poly h)
     2355static proc letterPlacePoly2MagmaString(poly h)
    23562356{
    23572357  int pos;
     
    23762376}
    23772377
    2378 proc letterPlaceIdeal2SD(ideal I, int upToDeg)
     2378static proc letterPlaceIdeal2SD(ideal I, int upToDeg)
    23792379{
    23802380  int i;
     
    24312431  example lp2ivId;
    24322432  example lpId2ivLi;
    2433   example lpGkDim;
    2434   example lpGlDimBound;
    24352433  example lpSubstitute;
    24362434}
     
    25252523   of n-th Weyl algebra including evaluation operators).
    25262524
    2527    proc createWeylEx(int n, int d)
     2525   static proc createWeylEx(int n, int d)
    25282526   "
    25292527   "
  • Singular/LIB/fpaprops.lib

    ra9ce91 r5edf31  
    66AUTHORS: Karim Abou Zeid,       karim.abou.zeid at rwth-aachen.de
    77
    8 Supported by the transregional collaborative research centre
     8Support: Project II.6 in the transregional collaborative research centre
    99SFB-TRR 195 'Symbolic Tools in Mathematics and their Application' of the German DFG
     10
    1011OVERVIEW:
    1112Algorithms for computing various properties of quotient algebras in the letterplace case.
     
    1415Huishi Li: Groebner bases in ring theory. World Scientific, 2010.
    1516
    16 SEE ALSO:  fpadim.lib, freegb.lib,
     17SEE ALSO:  fpadim_lib, freegb_lib
    1718
    1819PROCEDURES:
     
    2223  lpGkDim(<GB>);          compute the Gelfand Kirillov dimension of A/<GB>
    2324  lpGlDimBound(<GB>);     compute an upper bound for the global dimension of A/<GB>
    24   lpSubstitute();         substitute variable with polynoms
     25  lpSubstitute();         substitute variable with polynomials
    2526  lpCalcSubstDegBound();  utility for lpSubstitute
    2627  lpCalcSubstDegBounds(); utility for lpSubstitute
     
    196197PURPOSE: Check whether R/<G> is semi prime, where R is the basering
    197198ASSUME: - basering is a Letterplace ring
    198 @*      - G is a Groebner basis
     199      - G is a Groebner basis
    199200"
    200201{
     
    295296PURPOSE: Check whether R/<G> is prime, where R is the basering
    296297ASSUME: - basering is a Letterplace ring
    297 @*      - G is a Groebner basis
     298      - G is a Groebner basis
    298299"
    299300{
     
    368369"USAGE: existsRoute(G,v,u); G a graph, v and u vertices
    369370NOTE: don't pass anything to # (internal use for recursion)
    370 @*    routes always have at least one edge
     371routes always have at least one edge
    371372"
    372373{
     
    682683RETURN: intmat
    683684PURPOSE: Constructs the Ufnarovskij graph induced by G
    684 @*      the adjacency matrix of the Ufnarovskij graph induced by G
     685      the adjacency matrix of the Ufnarovskij graph induced by G
    685686ASSUME: - basering is a Letterplace ring
    686 @*      - G are the leading monomials of a Groebner basis
     687      - G are the leading monomials of a Groebner basis
    687688"
    688689{
     
    792793proc lpGkDim(ideal G, list#)
    793794"USAGE: lpGkDim(G); G an ideal in a letterplace ring, method an
    794 @*       optional integer. method = 0 uses the Ufnarovskij Graph
    795 @*       and method = 1 uses the Graph of normal words to determine
    796 @*       the Gelfand Kirillov dimension
     795       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
    797798RETURN: int
    798799PURPOSE: Determines the Gelfand Kirillov dimension of A/<G>
    799 @*      -1 means it is positive infinite
     800      -1 means it is positive infinite
    800801ASSUME: - basering is a Letterplace ring
    801802- G is a Groebner basis
     
    837838EXAMPLE: example lpGlDimBound; shows example
    838839NOTE: if I = LM(I), then the global dimension is equal the Gelfand
    839 @*    Kirillov dimension if it is finite
    840 @*    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>
    841842"
    842843{
     
    10151016proc lpSubstitute(poly f, ideal s1, ideal s2, list #)
    10161017"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 to
    1018 @*  reduce with.
     1018  to replace, s2 list (ideal) of polynomials to replace with, G optional ideal to
     1019  reduce with.
    10191020RETURN: poly, the substituted polynomial
    10201021ASSUME: - basering is a Letterplace ring
    1021 @*      - G is a groebner basis,
    1022 @*      - the current ring has a sufficient degbound (can be calculated with
    1023 @*      lpCalcSubstDegBound())
     1022      - G is a groebner basis,
     1023      - the current ring has a sufficient degbound (can be calculated with
     1024      lpCalcSubstDegBound())
    10241025EXAMPLE: example lpSubstitute; shows examples
    10251026"
     
    11211122proc lpCalcSubstDegBound(poly f, ideal s1, ideal s2)
    11221123"USAGE: lpCalcSubstDegBound(f,s1,s2); f letterplace polynomial, s1 list (ideal) of variables
    1123 @*  to replace, s2 list (ideal) of polynomials to replace with
     1124  to replace, s2 list (ideal) of polynomials to replace with
    11241125RETURN: int, the min degbound required to perform the substitution
    11251126ASSUME: - basering is a Letterplace ring
     
    11571158proc lpCalcSubstDegBounds(ideal I, ideal s1, ideal s2)
    11581159"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 with
     1160  of variables to replace, s2 list (ideal) of polynomials to replace with
    11601161RETURN: int, the min degbound required to perform all of the substitutions
    11611162ASSUME: - basering is a Letterplace ring
  • Singular/LIB/freegb.lib

    ra9ce91 r5edf31  
    33category="Noncommutative";
    44info="
    5 LIBRARY: freegb.lib   Compute two-sided Groebner bases in free algebras via
    6 @*                    letterplace
     5LIBRARY: freegb.lib   Compute two-sided Groebner bases in free algebras via letterplace approach
    76AUTHORS: Viktor Levandovskyy,     viktor.levandovskyy@math.rwth-aachen.de
    8 @*       Grischa Studzinski,      grischa.studzinski@math.rwth-aachen.de
     7       Grischa Studzinski,      grischa.studzinski@math.rwth-aachen.de
    98
    109OVERVIEW: For the theory, see chapter 'Letterplace' in the @sc{Singular} Manual
    1110
    1211PROCEDURES:
    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
     12makeLetterplaceRing(d); creates a ring with d blocks of shifted original variables
     13letplaceGBasis(I); computes two-sided Groebner basis of a letterplace ideal I up to a degree bound
     14lpNF(f,I); two-sided normal form of f with respect to ideal I
    2015setLetterplaceAttributes(R,d,b); supplies ring R with the letterplace structure
    21 
     16freeGBasis(L, n);  computes two-sided Groebner basis of an ideal, encoded via list L, up to degree n
    2217
    2318lpMult(f,g);    letterplace multiplication of letterplace polynomials
    2419shiftPoly(p,i); compute the i-th shift of letterplace polynomial p
    2520lpPower(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
     21lieBracket(a,b[, N]);  compute Lie bracket ab-ba of two letterplace polynomials
     22
     23lp2lstr(K, s);  convert a letterplace ideal into a list of modules
     24lst2str(L[, n]); convert a list (of modules) into polynomials in free algebra via strings
     25mod2str(M[, n]); convert a module into a polynomial in free algebra via strings
    2926vct2str(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
     28serreRelations(A,z); compute the homogeneous part of Serre's relations associated to a generalized Cartan matrix A
     29fullSerreRelations(A,N,C,P,d); compute the ideal of all Serre's relations associated to a generalized Cartan matrix A
     30isVar(p);              check whether p is a power of a single variable
    3631ademRelations(i,j);    compute the ideal of Adem relations for i<2j in char 0
    37 lpDelVar();     delete a variable from the current Letterplace ring
    3832
    3933SEE ALSO: fpadim_lib, LETTERPLACE
     
    13221316  list LR = ringlist(basering);
    13231317
    1324   if (!(index >= 1 && index <= lV)) { return (basering) } // invalid index
     1318  if (!(index >= 1 && index <= lV)) { return (basering); } // invalid index
    13251319
    13261320  // remove frome the variable list
     
    13571351  return (R);
    13581352}
    1359 
    1360 
     1353example
     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}
    13611361
    13621362/* EXAMPLES:
     
    26432643  if (i>N)
    26442644  {
    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);
    26462648  }
    26472649  if (i < N)
     
    30723074*/
    30733075
    3074 //static
    3075 proc lpMultX(poly f, poly g)
     3076static proc lpMultX(poly f, poly g)
    30763077{
    30773078  /* multiplies two polys in a very general setting correctly */
     
    31263127}
    31273128
    3128 // TODO:
    31293129// multiply two letterplace polynomials, lpMult: done
    31303130// reduction/ Normalform? needs kernel stuff
     
    32153215//@* else there wouldn't be an dvec representation
    32163216
    3217 //Mainprocedure for the user
     3217//Main procedure for the user
    32183218
    32193219proc lpNF(poly p, ideal G)
     
    32243224being a Letterplace Groebner basis (no check for this will be done)
    32253225NOTE: Strategy: take the smallest monomial wrt ordering for reduction
    3226 @*     For homogenous ideals the shift does not matter
    3227 @*     For non-homogenous ideals the first shift will be the smallest monomial
     3226-     For homogenous ideals the shift does not matter
     3227-     For non-homogenous ideals the first shift will be the smallest monomial
    32283228EXAMPLE: example lpNF; shows examples
    32293229"
     
    32573257RETURN: list of intvecs
    32583258PURPOSE: convert G into a list of intvecs, corresponding to the exponent vector
    3259 @* of the leading monomials of G
     3259 of the leading monomials of G
    32603260"
    32613261{int i; list L;
     
    32633263 return(L);
    32643264}
    3265 
    32663265
    32673266static proc delSupZero(intvec I)
     
    32903289}
    32913290
    3292 
    32933291static proc delSupZeroList(list L)
    32943292"USUAGE:delSupZeroList(L); L a list, containing intvecs
     
    33693367}
    33703368
    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
    33753370
    33763371static proc lpNormalForm1(poly p, ideal G, list L)
     
    34013396
    34023397
    3403 // new VL
    3404 proc lpNormalForm2(poly pp, ideal G, list L)
     3398// new VL; called from lpNF
     3399static proc lpNormalForm2(poly pp, ideal G, list L)
    34053400"USUAGE:lpNormalForm2(p,G);
    34063401RETURN:poly
    3407 PURPOSE:computation of the normalform of p w.r.t. G
     3402PURPOSE:computation of the normal form of p w.r.t. G
    34083403ASSUME: p is a Letterplace polynomial, G is a set of Letterplace polynomials
    34093404NOTE: Taking the first possible reduction
     
    36153610// // interface
    36163611
    3617 // proc whichshift(poly p, int numvars)
     3612// static proc whichshift(poly p, int numvars)
    36183613// {
    36193614// // numvars = number of vars of the orig free algebra
     
    36323627
    36333628// LIB "qhmoduli.lib";
    3634 // proc polyshift(poly p,  int numvars)
     3629// static proc polyshift(poly p,  int numvars)
    36353630// {
    36363631//   poly q = p; int i = 0;
     
    37103705}
    37113706
    3712 
     3707/* THE FOLLOWING IS UNDER DEVELOPMENT
    37133708// copied following from freegb_wrkcp.lib by Karim Abou Zeid on 07.04.2017:
    3714 // proc makeLetterplaceRingElim(int d)
    3715 // proc makeLetterplaceRingNDO(int d)
    3716 // proc setLetterplaceAttributesElim(def R, int uptodeg, int lV)
    3717 // proc lpElimIdeal(ideal I)
    3718 // proc makeLetterplaceRingWt(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
     3715static proc makeLetterplaceRingElim(int d)
    37213716"USAGE:  makeLetterplaceRingElim(d); d integers
    37223717RETURN:  ring
     
    38393834
    38403835
    3841 proc makeLetterplaceRingNDO(int d)
     3836static proc makeLetterplaceRingNDO(int d)
    38423837"USAGE:  makeLetterplaceRingNDO(d); d an integer
    38433838RETURN:  ring
     
    39473942}
    39483943
    3949 proc setLetterplaceAttributesElim(def R, int uptodeg, int lV)
     3944static proc setLetterplaceAttributesElim(def R, int uptodeg, int lV)
    39503945"USAGE: setLetterplaceAttributesElim(R, d, b, eV); R a ring, b,d, eV integers
    39513946RETURN: ring with special attributes set
     
    39813976
    39823977
    3983 proc lpElimIdeal(ideal I)
     3978static proc lpElimIdeal(ideal I)
    39843979"
    39853980does not work for degree reasons (deg function does not work for lp rings -> newone!)
     
    39993994
    40003995
    4001 proc makeLetterplaceRingWt(int d, intvec W)
     3996static proc makeLetterplaceRingWt(int d, intvec W)
    40023997"USAGE:  makeLetterplaceRingWt(d,W); d an integer, W a vector of positive integers
    40033998RETURN:  ring
     
    41024097  attrib(A,"lV"); // number of variables in the main block
    41034098}
     4099*/
Note: See TracChangeset for help on using the changeset viewer.