######################################################################## ## Resolution Graham Ellis ## Refactorization Robert F. Morse ## ## ## Usage: Resolution(g, dim) ## where g can be a group or a set of generators for a group ## dim the number of dimensions to compute ## ## ## \$Id: resolution.modified.g,v 1.22 2003/07/04 19:04:24 unialg Exp \$ ## Resolution:= function(g,dim) local ## Global variables for internal functions (set by Resolution) ## Elts, MT, SizeElts, Toggle1, Toggle2, G, ## Internal functions ZeroSkeleton, MaxComplex, Reso; #################################################################### #################################################################### ## A function which inputs a group G and outputs ## the zero-skeleton of the Cayley graph of G together with the ## action of G on the vertices. ## ZeroSkeleton:= function(G) local Vertices, # The set [1..Order(G)] CVertices, # A singleton subset of Vertices. VerticesActG, # A function (Vertices x G) --> Vertices giving the # action of G. DataV, # A list of the preceding three variables. SizeEdge, # The number of generators in Gens. Edge, # A function which inputs an integer i in # [1..SizeEdge] and returns the two (signed) # vertices # in the boundary of the edge representing the i-th # generator in Gens. DataE; # A list of the preceding two variables. Vertices:=[1..Size(G)]; CVertices:=[1]; VerticesActG:= function(f,g) local k,j; k:=((f-1) mod SizeElts)+1; return f-k+MT[g][k]; end; DataV:=[Vertices,CVertices,VerticesActG]; Edge:= function(i) local ret; ret:= [-PositionSorted(Elts,Identity(G)), PositionSorted(Elts,GeneratorsOfGroup(G)[i])]; ret := Collected(ret); Apply(ret, x->[AbsInt(x[1]),SignInt(x[1])*x[2]]); return ret; end; SizeEdge:=Length(GeneratorsOfGroup(G)); DataE:=[SizeEdge,Edge,Edge]; return [DataV,DataE,Elts]; end; ## ## ## End of the ZeroSkeleton function. #################################################################### #################################################################### #################################################################### #################################################################### ## A function which inputs a maximal contractible n-dimensional ## subcomplex ## of the space X = the universal cover of a classifying space ## for G, and ## outputs a maximal contractible (n+1)-dimensional subcomplex X. MaxComplex:= function(Elts,DataF,DataP) local ## The following variables are used to represent ## the input data. ## R, Faces, # A set [1..m] representing the n-cells in # X = universal cover of the classifying # space BG. CFaces, # A subset of Faces consisting of those # n-cells in the contractible subcomplex. FacesActG, # A function (Faces x G) --> G # giving the action of G # on the n-cells of X. FaceWeights, # A list of length Size(Faces). # FaceWeights[i]=1 if the # ith n-cell can be contracted into # the subcomplex; # else FaceWeights[i]=0. Polytope, # A function which inputs an integer # in [1..LengthPoly] # and returns a list of (signed) integers in # Faces. The # list Polytope(i) represents the oriented # faces of an # (n+1)-cell in X. These (n+1) cells are # (more than) # sufficient to generate all n-syzygies. LengthPoly, # The number of n-syzygies supplied. ## The following variables are used to represent the output data. ## NewFaces, NewCFaces, NewDataF, NewDataP, NewPolytope, NewLengthPoly, ## The following variables are used within the function. ## Boundary, # A function which inputs an integer in # NewFaces and # returns a list of integers in Faces. # Boundary(i) is # the list of faces in the boundary of the # i-th (n+1)-cell of X. Contraction, SignedPoly, PolySize, ShiftPolytope, Complex, NewCFacesComplement, Shift, Try, p, q, Bcanidates, Bdone, BCloseN, BAction, BList, FContraction, f, g, s, t, i, j; R := Runtime(); ## Initialize Variables from formal parameters ## Faces:=DataF[1]; CFaces:=DataF[2]; FacesActG:=DataF[3]; LengthPoly:=DataP[1]; Polytope:=DataP[2]; PolySize:=0; ## Local function to MaxComplex to compute ## the "closure" of a polytope (referenced by ## the formal parameter "index"). By closure ## we mean find all elements of G (possible none) that ## make one edge go to one and all others go to zero. ## BCloseN:= function(index) local R,j,sum,tmp, p,s,g,set,elim; R := Runtime(); s:= index; set:=false; elim:=[]; for g in [1..SizeElts] do if not g in Try[s] then j := 1; sum := 0; repeat tmp := FaceWeights[FacesActG(SignedPoly[s][j][1],g)]* AbsInt(SignedPoly[s][j][2]); if tmp=1 then p:=j; fi; sum := sum+tmp; j := j+1; until sum >1 or j > Length(SignedPoly[s]); if sum = 0 then Add(elim,g); fi; if sum =1 then if not s in Shift then Add(Shift,s); fi; Complex[s][g]:=true; Add(elim,g); set := true; FaceWeights[FacesActG(SignedPoly[s][p][1],g)]:=0; ## Save data necessary to compute Contraction ## if Toggle2 then Add(BAction,[s,p,g]); fi; if Sum(FaceWeights)=0 then Append(Try[s],elim); return true; fi; fi; fi; od; Append(Try[s],elim); return set; end; ## Initialize computed local variables ## ## FaceWeights:= ListWithIdenticalEntries(Size(Faces),1); for f in CFaces do FaceWeights[f]:=0; od; Complex := List([1..LengthPoly],x->BlistList([1..SizeElts],[])); Shift:=[]; Contraction:=List([1..Size(Faces)],x->Set([])); Try := List([1..LengthPoly],x->Set([])); BAction:=[]; SignedPoly:=[]; ## The initialization of SignedPoly takes a significant ## amount of time. Progress is reported for information to user. ## This information could be done with an InfoLevel ## contruct. ## for s in [1..LengthPoly] do if (s mod 10000)=0 then Print("Building SignedPoly: s= ", s, " out of ",LengthPoly,"\n"); fi; SignedPoly[s]:=Polytope(s); od; ## Sort BSignedPoly by size so that those elements of shortest ## length will be used first. ## Sort(SignedPoly, function(c0,c1) return Sum(List(c0,x->AbsInt(x[2])))< Sum(List(c1,x->AbsInt(x[2]))); end); ################################################################ ## Find Complex ## ## Find the smallest set of polytopes that ## close FaceWeights (forces all of it entries to zero) ## ## Find the first element in poly in which we can form a closure ## i.e. at least one element of G reduces FaceWeight ## if First([1..Length(SignedPoly)], x->BCloseN(x))=fail then Error("Panic we cannot start closure"); fi; ## Find a/the (smallest?) set of Polytopes that force ## all elements of FaceWeights to zero ## Bcanidates := []; while Sum(FaceWeights)>0 do ## Find the next candidate in BSignedPoly for closure ## and add to Bshift ## Bcanidates := Filtered([Maximum(Shift)+1..Length(SignedPoly)], x->not x in Shift); if First([1..Length(Bcanidates)], x->BCloseN(Bcanidates[x]))=fail then Error("Panic we cannot get another closure element"); fi; if Sum(FaceWeights)>0 then ## Close Shift polytopes ## repeat until ForAll(Shift,x->not BCloseN(x)); fi; od; Complex := Complex{Shift}; ## Build a data structure to create on the fly contraction data ## Contraction:=[]; BList :=[]; for q in BAction do s:=q[1]; p:=q[2]; g:=q[3]; Add(BList,FacesActG(SignedPoly[s][p][1],g)); Bdone :=[]; for j in SignedPoly[s] do if not j[1]=SignedPoly[s][p][1] and FacesActG(j[1],g) in BList then Add(Bdone, Position(BList,FacesActG(j[1],g))); fi; od; Add(Contraction, [SignInt(SignedPoly[s][p][2])* ((Position(Shift,s)-1)*SizeElts+g), StructuralCopy(Bdone)]); od; ## ## "Complex" is now computed. ################################################################ ## This function will find the jth index of contraction without ## computing the whole original data structure. ## ## BList is an index set that finds the proper starting point ## to look in Contraction (which is represented as an ## adjacency list) and follows each index in the adjacency list ## recursively -- done with a simple stack variable to find ## the contraction entry "j". ## FContraction := function(j) local ret, p, p1, Stack, nodes; p := Position(BList,j); if p=fail then return Collected([]); fi; if IsEmpty(Contraction[p][2]) then return [[Contraction[p][1],1]]; fi; Stack := Contraction[p][2]; nodes := [Contraction[p][1]]; ret :=[[Contraction[p][1],1]]; repeat p := Stack[Length(Stack)]; Stack := Stack{[1..Length(Stack)-1]}; p1 := Position(nodes,Contraction[p][1]); if p1<>fail then ret[p1][2]:=ret[p1][2]+1; else Add(ret,[Contraction[p][1],1]); Add(nodes,Contraction[p][1]); fi; Append(Stack,Contraction[p][2]); until IsEmpty(Stack); return ret; end; ################################################################ ## This function is used to compute the function returned to the ## the user. ## ShiftPolytope:= function(j) local ret,p; ret:=[]; for p in SignedPoly[Shift[j]] do Append(ret, ListWithIdenticalEntries(AbsInt(p[2]), SignInt(p[2])*p[1])); od; return ret; end; ################################################################ ## The Boundary function. ## Boundary:= function(t) local p,f,g,s; s:=AbsInt(t); f:=QuoInt(s-1,SizeElts)+1; g:=1+((s-1) mod SizeElts); p:=SignInt(t)*ShiftPolytope(f); Apply(p,i->SignInt(i)*FacesActG(AbsInt(i),g)); return p; end; ## ## ################################################################ ################################################################ ## The NewPolytope function. ## NewPolytope:= function(i) local ret, C,L,L1,L2,p; L:=[]; for p in Boundary(NewCFacesComplement[i]) do; C:= FContraction(AbsInt(p)); Apply(C, x->[-SignInt(p)*x[1],x[2]]); Append(L,C); od; Append(L, Collected([NewCFacesComplement[i]])); Apply(L, x->[AbsInt(x[1]),SignInt(x[1])*x[2]]); if Toggle1 then ## This code is like a counting sort and is linear in ## the length of L L2 := []; for p in L do if IsBound(L2[p[1]]) then L2[p[1]]:=L2[p[1]]+p[2]; else L2[p[1]]:=p[2]; fi; od; L1 :=[]; for p in [1..Length(L2)] do if IsBound(L2[p]) and not IsZero(L2[p]) then Add(L1,[p,L2[p]]); fi; od; else L1:=L; fi; return L1; end; ## ## ################################################################ PolySize:=Length(Shift); NewFaces:=[1..SizeElts*PolySize]; NewLengthPoly:=PolySize*SizeElts - Sum(List([1..Length(Complex)], i->Length(Filtered(Complex[i],j->j=true)))); NewCFacesComplement:=[]; NewCFaces:=[]; for s in NewFaces do i:=(s-1) mod SizeElts; j:=QuoInt(s-1,SizeElts); if Complex[1+j][1+i] = false then Add(NewCFacesComplement,s); else Add(NewCFaces,s); fi; od; NewDataF:=[NewFaces, NewCFaces, FacesActG]; NewDataP:=[NewLengthPoly,NewPolytope]; ## Actual returned data and references to data structures ## ## NewDataF : NewFaces, NewCFaces, FacesActG ## NewFaces --> Range ## NewCFaces --> List ## FacesActG --> function from ZeroSkeleton ## NewDataP : NewLengthPoly, NewPolytope ## NewLengthPoly --> Integer ## NewPolytope --> function which refers to the ## functions FContraction, Boundary, ## and list NewCFaceComplement ## FContraction --> Contraction (list of lists) ## Boundary --> function ShiftPolytope ## ## Shift : List of poly that closes FaceWeights ## ShiftPolytope: Function which references SignedPoly and ## Shift. return [NewDataF,NewDataP,Shift,ShiftPolytope]; end; ## ## ## End of the MaxComplex function. #################################################################### #################################################################### #################################################################### #################################################################### ## A function which inputs a set Gens of a group G and a ## positive integer dim, and outputs a free ZG-resolution ## of Z upto to dimension dim. ## Reso:= function(G,dim) local D, # The resolution is returned as a list D. For i>=1 # D[i+1] is a pair [n,f]. The variable n is a # non-negative integer equal to the ZG-rank of the # i-th module in the resolution. The variable f is a # function; for 1 <=j <= n the function f returns # a list f(j) of signed integers representing the # boundary of the j-th generator of the i-th module; # in this list f(j) an integer m represents the p-th # generator of the (i-1)-th module acted on by the # g-th element of G, where m-1 = (p-1) |G| + (g-1). Act, # The variable Act is a function [1..n|G|] x [1..|G|] # --> [1..|n||G|] representing the action of G. BCprev, BCnext, BD, Barray, C, i,retfunc; BCprev:=ZeroSkeleton(G); Act:=BCprev[1][3]; BD:=[]; retfunc := function(Array) return function(j) local A; A:= Array; return A[j]; end; end; ## Using the previous/next setup eliminates ## having memory references to unneeded data structures ## such as Contraction and SignedPoly from earlier iterations. ## for i in [1..dim] do ## Special processing for dim 2 case (nonabelian) ## if not(i=2) then Toggle1:=true; else Toggle1:=false; fi; ## Don't compute contraction for the last iteration ## won't be used ## if i=dim then Toggle2:=false; else Toggle2:=true; fi; ## BCnext is computed via the call ## BCprev[3] --> Elements of the group (constant) ## BCprev[1] --> DataF (range, list, function) ## BCprev[2] --> DataP BCnext := MaxComplex(Elts,BCprev[1],BCprev[2]); Print("Completed dimension ", i, " out of ", dim, ".\n"); ## Build a copy of the returned values to break ## referenced data which can be very large and the ## returned values does not need all this data ## Barray := List([1..Length(BCnext[3])], y->BCnext[4](y)); BD[i] := [Size(BCnext[3]), retfunc(Barray), Length(BCnext[4](Size(BCnext[3])))]; BCprev := BCnext; od; return [BD,Act]; end; ## ## ## End of the Reso function. #################################################################### #################################################################### #################################################################### ## Begin Resolution ## ## Resolution can take a group or a set of generators of a group ## as a first parameter ## if IsGroup(g) then G := g; else G := Group(g); fi; ## Initialize global variables ## Elts := Elements(G); MT := MultiplicationTable(Elts); SizeElts := Size(G); return Reso(G,dim); end; ## ## End of resolution ######################################################################## ########################################################################