


The
examples in the preceding pages were performed under Debian Linux on
an IBM Thinkpad laptop with a 1.4 GHz Celeron M processor and 256MB of
memory. An uncompiled version of the HAP library was used. Each example
took anything from a few seconds to over two hours to
run. It may well be that the performance of several key functions is far from optimal, and that the library could benefit from further work on these. We discuss this below. 

1.
ResolutionFiniteGroup(gens,n) a) This function underlies most computations of ZGresolutions for a finite group G. When n=2 the function just computes a group presentation for G, and the method is essentially that of John Cannon's algorithm used in the GAP function PresentationViaCosetTable(G). The timings (in milliseconds) gap> P:=ResolutionFiniteGroup([(1,2),(1,2,3,4,5,6)],2);;time; 7599 gap> P:=PresentationViaCosetTable(Group([(1,2),(1,2,3,4,5,6)]));;time; 21 suggest that the run time of the resolution function is not optimal. Some of the timing discrepancy arises because the resolution function first computes the multiplication for G. This pays off when n>2. Nevertheless, there is a large remaining discrepancy between the timings which needs investigation. b) The performance of the resolution function for higher n is also very sensitive to the choice of generators. For certain generating sets the function produces a significantly "bigger" resolution which can require excessive memory and run time. This is a feature of the algorithm rather than the implementation, and might be worth further investigation. 

2.
ResolutionNormalSeries(N,n) a) This function finds a resolution for G by repeatedly applying a perturbation technique to a sequence of normal subgroups G=N_{1}>N_{2}>...>N_{k}=1. The resolution for G is got by combining resolutions for the quotients N_{i}/N_{i+1}. The ZGresolution will have a reasonably small number of free generators in each dimension provided each Z(N_{i}/N_{i+1})resolution has not too many generators. Nevertheless, the boundary of a generator in the ZGresolution can sometimes be problematically large, as the following example shows. gap> G:=SmallGroup(64,7);; N1:=GeneratorsOfGroup(G);; gap> N2:=GeneratorsOfGroup(NormalSubgroups(G)[6]);; N3:=Identity(G);; gap> R:=ResolutionNormalSeries([N1,N2,N3],6);;time; 26250 gap> List([1..R!.dimension(6)], i>Length(R!.boundary(6,i))); [ 8, 1446, 1077, 4164, 4280, 4700, 1100, 435, 776, 524, 659, 30, 139, 4, 8, 8 ] If the resolution R is only required for mod 2 cohomology calculations then the problem of large boundaries can sometimes be overcome by setting a fourth parameter equal to 2 as follows. gap> R:=ResolutionNormalSeries([N1,N2,N3],80,false,2);;time; 131960 gap> TR:=TensorWithIntegersModP(R,2);;time; 0 gap> Homology(TR,79,2);time; 80 950 This shows that for the 7th group G of order 64 we have H_{79}(G,Z_{2}) = (Z_{2})^{80}. For integral cohomology calculations it might be worth investigating if higher dimensional Tietze simplifications could sometimes be used to overcome the problem of resolution generators with large boundaries. b) The computation gap> L:=LowerCentralSeries(SylowSubgroup(MathieuGroup(24),2)); gap> R:=ResolutionNormalSeries(L,7);; took just under two hours to produce seven terms of an integral ZPresolution for the Sylow 2subgroup P (order 1024) of M_{24}. The resolution R has just over 11000 generators in dimension 7. The function Homology(TR,6) naively applies GAP's Smith Normal Form algorithm to the chain complex TR = R(×)_{ZP}Z and, in view of the number of generators in dimension 7, would probably take for ever to complete. However, the matrices for the boundary maps in TR are in upper triangular block form, and so GAP's SNF algorithm could be applied in a divideandconquer fashion to calculate the 6th homology of P. A function for this divideandconquer approach needs to be written. 

3.
PrimePartDerivedFunctor(G,R,n) The second integral homology of, say, the Sylow 2subgroup of S_{14} can be calculated using a standard GAP function gap> G:=SylowSubgroup(SymmetricGroup(14),2);; gap> AbelianInvariantsMultiplier(G);time; [ 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2 ] 974539 which takes about 16 minutes to complete. The following HAP functions are significantly quicker at this calculation. gap> L:=PCentralSeries(SylowSubgroup(SymmetricGroup(14),2));; gap> R:=ResolutionNormalSeries(L,3);;time; 2241 gap> TR:=TensorWithIntegers(R);; time; 0 gap> Homology(TR,2);time; [ 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2 ] 614 In versions of GAP prior to version 4.4.6 the standard function AbelianInvariantsMultiplier() ran very much faster but sometimes gave the wrong answer. Despite its unreliability, this older function was certainly based on a sound algorithm and it is probably more realistic to compare HAP's timings against the older function. For example, the GAP version 4.4.4 commands gap> AbelianInvariantsMultiplier(MathieuGroup(23));time; [ 2 ] 5650 take under 6 seconds to calculate the second integral homology of the Mathieu group M_{23}. (The calculation is not correct since in fact H_{2}(M_{23},Z) = 0.) The Sylow psubgroups of M_{23} are noncyclic for p=2,3 only. So HAP's function PrimePartOfIntegralHomology() can be used to calculate H_{2}(M_{23},Z)=0 as follows. Note however that this approach is a good bit slower than GAP version 4.4.4's standard function. gap> G:=MathieuGroup(23);; P2:=SylowSubgroup(G,2);; P3:=SylowSubgroup(G,3);; gap> gensP2:=GeneratorsOfGroup(P2);; gensP3:=GeneratorsOfGroup(P3);; gap> R:=ResolutionFiniteGroup(gensP2,3);;time; 690 gap> S:=ResolutionFiniteGroup(gensP3,3);;time; 0 gap> T:=TensorWithIntegers;; gap> PrimePartDerivedFunctor(G,R,T,2);time; [ ] 7764 gap> PrimePartDerivedFunctor(G,S,T,2);time; [ ] 419 The discrepancy between the timings for the two approaches is probably because the function PrimePartOfIntegralHomology() computes a resolution for a large number of double coset representative of P in G. It should be possible to restrict the computations to a subset of these representatives. Sometimes HAP's functions are a bit faster than even the older AbelianInvariantsMultiplier() function. Compare for example the GAP version 4.4.4 commands gap> P:=SylowSubgroup(SymmetricGroup(20),2);; gap> AbelianInvariantsMultiplier(P); time; [ 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2 ] 672120 versus gap> R:=ResolutionNormalSeries(BigStepLCS(P,8),3);; time; 6882 gap> TR:=TensorWithIntegers(R);;time; 0 gap> Homology(TR,2);time; [ 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2 ] 2381 (In GAP version 4.4.6 the function AbelianInvariantsMultiplier(G) ran for about 10 minutes on G=M_{23} before exceeding the permitted memory. It failed to complete in over an hour for G the Sylow 2subgroup of S_{20}.) 

