Previous About HAP: Computational Issues
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 ZG-resolutions 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=N1>N2>...>Nk=1. The resolution for G is got by combining resolutions for the quotients Ni/Ni+1. The ZG-resolution will have a reasonably small number of free generators in each dimension provided each Z(Ni/Ni+1)-resolution has not too many generators. Nevertheless, the boundary of a generator in the ZG-resolution 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 H79(G,Z2) = (Z2)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 ZP-resolution for the Sylow 2-subgroup P (order 1024) of M24. 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(×)ZPZ 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 divide-and-conquer fashion to calculate the 6th homology of P. A function for this divide-and-conquer approach needs to be written.
3. PrimePartDerivedFunctor(G,R,n) The second integral homology of, say, the Sylow 2-subgroup of S14 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 M23. (The calculation is not correct since in fact H2(M23,Z) = 0.) The Sylow p-subgroups of M23 are non-cyclic for p=2,3 only. So HAP's function PrimePartOfIntegralHomology() can be used to calculate H2(M23,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=M23 before exceeding the permitted memory.  It failed to complete in over an hour for G the Sylow 2-subgroup of S20.)
Previous Page Contents