Quelle aboutPerformance.html Sprache: HTML

products/sources/formale Sprachen/GAP/pkg/hap/www/SideLinks/About/aboutPerformance.html

<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
 <meta http-equiv="content-type"
content="text/html; charset=ISO-8859-1">
 <title>AboutHap</title>
</head>
<body
style="color: rgb(0, 0, 153); background-color: rgb(204, 255, 255);"
alink="#000066" link="#000066" vlink="#000066">
 
<table
style="text-align: left; margin-left: auto; margin-right: auto; color: rgb(0, 0, 102);"
border="0" cellpadding="20" cellspacing="10">
 <tbody>
 <tr align="center">
 <th style="vertical-align: top;">
 <table style="width: 100%; text-align: left;" cellpadding="2"
cellspacing="2">
 <tbody>
 <tr>
 <td style="vertical-align: top;"><a
href="aboutAbelianCategories.html">Previous</a> 
 </td>
 <td
style="text-align: center; vertical-align: top; color: rgb(0, 0, 102);"><big>About HAP: Computational Issues 
 </big></td>
 <td style="text-align: right; vertical-align: top;"> 
 </td>
 </tr>
 </tbody>
 </table>
 <big></big> 
 </th>
 </tr>
 <tr>
 <td
style="vertical-align: top; background-color: rgb(255, 255, 255); text-align: left;">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. 
 </td>
 </tr>
 <tr>
 <td
style="background-color: rgb(255, 255, 255); vertical-align: top;">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. 
 </td>
 </tr>
 <tr>
 <td
style="text-align: left; background-color: rgb(255, 255, 255); vertical-align: top;">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. 
 </td>
 </tr>
 <tr>
 <td
style="vertical-align: top; background-color: rgb(255, 255, 255);">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
style="font-family: helvetica,arial,sans-serif;">
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.) 
 </td>
 </tr>
 <tr>
 <td style="vertical-align: top;">
 <table
style="margin-left: auto; margin-right: auto; width: 100%; text-align: left;"
border="0" cellpadding="2" cellspacing="2">
 <tbody>
 <tr>
 <td style="vertical-align: top;"><a
style="color: rgb(0, 0, 102);" href="aboutAbelianCategories.html">Previous
Page</a> 
 </td>
 <td style="text-align: center; vertical-align: top;"><a
href="aboutContents.html">Contents</a> 
 </td>
 <td style="text-align: right; vertical-align: top;"><a
href="aboutExtensions.html"> 
 </a> </td>
 </tr>
 </tbody>
 </table>
 <a href="aboutTopology.html"> 
 </a> </td>
 </tr>
 </tbody>
</table>
 
 
</body>
</html>

Messung V0.5

¤ Dauer der Verarbeitung: 0.13 Sekunden (vorverarbeitet) ¤

Wurzel

Suchen

Beweissystem der NASA

Beweissystem Isabelle

NIST Cobol Testsuite

Cephes Mathematical Library

Wiener Entwicklungsmethode

Haftungshinweis

Die Informationen auf dieser Webseite wurden nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit, noch Qualität der bereit gestellten Informationen zugesichert.

Bemerkung:

Die farbliche Syntaxdarstellung und die Messung sind noch experimentell.