<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en">
<head>
<title>GAP (HAPprime) - Chapter 2: Examples</title>
<meta http-equiv="content-type" content="text/html; charset=UTF-8" />
<meta name="generator" content="GAPDoc2HTML" />
<link rel="stylesheet" type="text/css" href="manual.css" />
</head>
<body>
<div class="chlinktop"><span class="chlink1">Goto Chapter: </span><a href="chap0.html">Top</a> <a href="chap1.html">1</a> <a href="chap2.html">2</a> <a href="chap3.html">3</a> <a href="chapInd.html">Ind</a> </div>
<div class="chlinkprevnexttop"> <a href="chap0.html">Top of Book</a> <a href="chap1.html">Previous Chapter</a> <a href="chap3.html">Next Chapter</a> </div>
<p><a id="X7A489A5D79DA9E5C" name="X7A489A5D79DA9E5C"></a></p>
<div class="ChapSects"><a href="chap2.html#X7A489A5D79DA9E5C">2 <span class="Heading">Examples</span></a>
<div class="ContSect"><span class="nocss"> </span><a href="chap2.html#X81FB934A87FCAA22">2.1 <span class="Heading">Computing the mod p group cohomology</span></a>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap2.html#X78EE4D0386321E3B">2.2 <span class="Heading">Computing mod-p cohomology rings and their Poincaré series</span></a>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2.html#X81BCBAA18423E1C8">2.2-1 <span class="Heading">A ring presentation for the mod p cohomology (up to degree n)</span></a>
</span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2.html#X825971A27C00C1B6">2.2-2 <span class="Heading">Calculating a provably-correct mod-p cohomology</span></a>
</span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2.html#X78F3639083A7DE62">2.2-3 <span class="Heading">Computing Poincaré series</span></a>
</span>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap2.html#X87AD96A584D60140">2.3 <span class="Heading">Comparing the memory usage and speed of <strong class="pkg">HAPprime</strong> and <strong class="pkg">HAP</strong>'s
<code class="keyw">ResolutionPrimePowerGroup</code> functions</span></a>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2.html#X85FFD31A7B362DFF">2.3-1 <span class="Heading"><strong class="pkg">HAPprime</strong> takes less memory to store resolutions</span></a>
</span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2.html#X848CF4C483C3F6E4">2.3-2 <span class="Heading"><strong class="pkg">HAPprime</strong> takes less memory to compute resolutions</span></a>
</span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2.html#X7CA386948072CFF4">2.3-3 <span class="Heading">Automatic selection of the best method</span></a>
</span>
</div>
</div>
<h3>2 <span class="Heading">Examples</span></h3>
<p><a id="X81FB934A87FCAA22" name="X81FB934A87FCAA22"></a></p>
<h4>2.1 <span class="Heading">Computing the mod p group cohomology</span></h4>
<p>Let G be a group and F be a field, and let FG be the group ring of G over F. A free FG-resolution of the ground ring is an exact sequence of module homomorphisms</p>
<p class="pcenter">
... ---> M_(n+1) ---> M_n ---> M_(n-1) ---> ... ---> M_1 ---> FG --->> F
</p>
<p>Where each M_n is a free FG-module and the image of d_n+1: M_n+1 -> M_n equals the kernel of d_n: M_n -> M_n-1 for all n > 0. The maps d_n are called boundary homomorphisms. In <strong class="pkg">HAPprime</strong> we consider the case where G is a p-group and F is the prime field GF(p), and this is assumed from now on.</p>
<p>If we now define the Abelian group D_n to be Hom(M_n, F), the set of all homomorphisms M_n -> F, we can obtain the dual of this sequence, which will be a cochain complex of Abelian group homomorphisms</p>
<p class="pcenter">
... <--- D_(n+1) <--- D_n ---> D_(n-1) <--- ... <--- D_1 <--- F <--- F
</p>
<p>Each group D_n will be isomorphic to F^|M_n| where |M_n| is the rank of the module M_n. Unlike the resolution, this sequence will generally not be exact, but one can define the mod-p cohomology group of G at degree n to be</p>
<p class="pcenter">
H^n(G, F) = ker(D_n ---> D_(n+1)) / im(D_(n-1) ---> D_n)
</p>
<p>for all n > 0. As with the D_n, the mod-p cohomology groups will also be isomorphic to vector spaces over F. In the case where the resolution R is minimal (where each module M_n has the minimal number of generators), the dimensions of the (co)homology groups H^n(G, F) are identical to the dimensions of the resolution modules M_n. The group cohomology (and the similar group homology) is an invariant of G, and does not depend on a particular free FG-resolution.</p>
<p>In the general case, there are thus two stages to computing the group cohomology of G up to the nth cohomology group:</p>
<ol>
<li><p>Compute R, a free FG-resolution for FG, with at least n+1 terms.</p>
</li>
<li><p>Construct the cochain complex C from R and compute the n homology groups of C</p>
</li>
</ol>
<p>For example, to calculate the 9th mod-p cohomology group of the 134th order 64 in the <strong class="pkg">GAP</strong> small groups library (which is the Sylow 2-subgroup of the Mathieu group M_12), we can use the <strong class="pkg">HAPprime</strong> function <code class="func">ResolutionPrimePowerGroupRadical</code> (<a href="chap3.html#X86934BE9858F7199"><b>3.1-1</b></a>) to compute 10 terms of a free FG-resolution for G and then use <strong class="pkg">HAP</strong> functions to find the rank b_9 of the cohomology group, which will be isomorphic to F^b_9. Alternatively, since <code class="func">ResolutionPrimePowerGroupRadical</code> (<a href="chap3.html#X86934BE9858F7199"><b>3.1-1</b></a>) always returns a minimal resolution, the cohomology group dimensions can be read directly from the resolution.</p>
<table class="example">
<tr><td><pre>
gap> G := SmallGroup(64, 134);;
gap> # First construct a FG-resolution for the group G
gap> R := ResolutionPrimePowerGroupRadical(G, 10);
Resolution of length 10 in characteristic 2 for <pc group of size 64 with
6 generators> .
No contracting homotopy available.
A partial contracting homotopy is available.
gap> # Convert this into a cochain complex (over the prime field with p=2)
gap> C := HomToIntegersModP(R, 2);
Cochain complex of length 10 in characteristic 2 .
gap> # And get the rank of the 9th cohomology group
gap> b9 := Cohomology(C, 9);
55
gap>
gap> # Since R is a free resolution, the ranks of the cohomology groups
gap> # are the same as the module ranks in R
gap> ResolutionModuleRanks(R);
[ 3, 6, 10, 15, 21, 28, 36, 45, 55, 66 ]</pre></td></tr></table>
<p><a id="X78EE4D0386321E3B" name="X78EE4D0386321E3B"></a></p>
<h4>2.2 <span class="Heading">Computing mod-p cohomology rings and their Poincaré series</span></h4>
<p>The mod-p group cohomology of a p-group G, given a field F = GF(p), has a multiplicative structure, and so the group</p>
<p class="pcenter">
H^*(G, F) = H^0(G, F) + H^1(G, F) + H^2(G, F) + ...
</p>
<p>is a ring. Since H^*(G, F) is isomorphic to a vector space over F, it is also an algebra, in fact a graded algebra: for elements e in H^n(G, F) and f in H^m(G, F), the product ef is an element of H^m+n(G, F).</p>
<p>Some functions for investigating the ring structure of H^*(G, F) using <strong class="pkg">GAP</strong> are already provided by <strong class="pkg">HAP</strong>, and also by Marcus Bishop's <strong class="pkg">Crime</strong> package <span class="URL"><a href="http://www.math.uic.edu/~marcus/Crime/">http://www.math.uic.edu/~marcus/Crime/</a></span>. There have also been implementations using other systems, in particular, Jon Carlson has computed the cohomology rings for all 2-groups of order 64 and fewer using MAGMA (see <span class="URL"><a href="http://www.math.uga.edu/~lvalero/cohointro.html">http://www.math.uga.edu/~lvalero/cohointro.html</a></span> for results) and David Green has calculated the same, and some of order 128, using C (see <span class="URL"><a href="http://www.math.uni-wuppertal.de/~green/Coho_v2/index.html">http://www.math.uni-wuppertal.de/~green/Coho_v2/index.html</a></span> for results).</p>
<p><a id="X81BCBAA18423E1C8" name="X81BCBAA18423E1C8"></a></p>
<h5>2.2-1 <span class="Heading">A ring presentation for the mod p cohomology (up to degree n)</span></h5>
<p>The cohomology ring H^*(G, F) is an infinite vector space, but if all elements of degree higher than some degree n are ignored, a related finite algebra can be considered. Multiplication in this finite algebra can be represented by a multiplication table giving the product of each basis element in the vector space (up to products of degree n). The <strong class="pkg">HAP</strong> function <code class="func">ModPCohomologyRing</code> (<a href="/home/pas/GAP/pkg/Hap1.8/doc/chap8.html#X7A9561E47A4994F5"><b>HAP: ModPCohomologyRing</b></a>) computes such a finite algebra representation for the mod-p cohomology ring of a p-group G for a given value of n.</p>
<p>The full infinite-dimensional cohomology ring has a finite presentation as a quotient ring</p>
<p class="pcenter">
H^*(G, F) = F[x_1, x_2, ..., x_n] / (I_1, I_2, ..., I_m)
</p>
<p>where the polynomial ring indeterminates x_i each have an associated degree d_i and the I_j are relations which together generate an ideal in the ring. Given a finite algebra A, the <strong class="pkg">HAPprime</strong> function <code class="func">ModPCohomologyRingPresentation</code> (<a href="chap3.html#X85CFF2AB7A7A99D2"><b>3.3-1</b></a>) calculates a presentation for the ring, modulo any generating elements of degree higher than n. If H^*(G, F) has no generators or relations in degrees higher than n, then a ring presentation for an algebra computed via <code class="func">ModPCohomologyRing</code> (<a href="/home/pas/GAP/pkg/Hap1.8/doc/chap8.html#X7A9561E47A4994F5"><b>HAP: ModPCohomologyRing</b></a>) followed by <code class="func">ModPCohomologyRingPresentation</code> (<a href="chap3.html#X85CFF2AB7A7A99D2"><b>3.3-1</b></a>) will be the same as a ring presentation for H^*(G, F).</p>
<p>We shall calculate a ring presentation for the group <code class="code">G := SmallGroup(16, 3)</code>:</p>
<table class="example">
<tr><td><pre>
gap> G := SmallGroup(16, 3);;
gap> A := ModPCohomologyRing(G, 5);
<algebra of dimension 34 over GF(2)>
gap> ModPCohomologyRingPresentation(A);
Graded algebra GF(2)[ x_1, x_2, x_3, x_4, x_5 ] /
[ x_1*x_2, x_1^2, x_1*x_5, x_2^2*x_3+x_5^2 ] with indeterminate degrees
[ 1, 1, 2, 2, 2 ]</pre></td></tr></table>
<p>The object returned by <code class="func">ModPCohomologyRingPresentation</code> (<a href="chap3.html#X85CFF2AB7A7A99D2"><b>3.3-1</b></a>) tells us that</p>
<p class="pcenter">
H^*(G, F) = F[v,w,x,y,z] / (v^2, vw, vz, w^2y+z^2)
</p>
<p>where the indeterminates v and w are in degree one and the rest are in degree two. This assumes, however, that there are no generating elements in any degree higher than five. See Section <a href="chap2.html#X825971A27C00C1B6"><b>2.2-2</b></a> below for a method that also computes the maximum degree necessary to present the cohomology ring, and so avoids this limitation.</p>
<p>As well as taking the algebra as an argument, the function <code class="func">ModPCohomologyRingPresentation</code> (<a href="chap3.html#X85CFF2AB7A7A99D2"><b>3.3-1</b></a>) can also take a group or a free FG-resolution, and a value for n, in which case it performs the calculation of the algebra as well.</p>
<p><a id="X825971A27C00C1B6" name="X825971A27C00C1B6"></a></p>
<h5>2.2-2 <span class="Heading">Calculating a provably-correct mod-p cohomology</span></h5>
<p>Using the <strong class="pkg">HAP</strong> function <code class="func">ModPCohomologyRing</code> (<a href="/home/pas/GAP/pkg/Hap1.8/doc/chap8.html#X7A9561E47A4994F5"><b>HAP: ModPCohomologyRing</b></a>), <strong class="pkg">HAPprime</strong> can calculate a presentation for the cohomology ring H^*(G, F) as described in Section <a href="chap2.html#X81BCBAA18423E1C8"><b>2.2-1</b></a>) It is known (Evens 1961) that mod-p cohomology rings are finitely-generated, and hence given a sufficiently-large n the presentation calculated in the above manner will be the complete ring. <strong class="pkg">HAPprime</strong> can compute a sufficient value for n (in fact, it will be near, and usually at, the minimum). <strong class="pkg">HAPprime</strong> uses the original Evens proof constructively. For a group G, a Lyndon-Hochschild-Serre spectral sequence can be computed. This will converge, and the limiting sheet of the sequence will be a ring which is an associated graded ring of the mod-p cohomology ring H^*(G, F). This means that, while it will not necessarily be isomorphic to H^*(G, F), it will have the same additive structure, and the generators and relations will lie in the same degrees. Thus the maximum degree in the presentation for the last sheet of the spectral sequence is a sufficient value for n. The spectral sequence computation requires minimal resolutions and correct cohomology rings for two smaller groups (a central subgroup N and the quotient group G/N), but these rings can be in turn computed by the same process (and the cohomology rings for some small groups can simply be stated). The cohomology ring for G will thus be proved correct by induction.</p>
<p>When called with just a group (i.e. no value for n), <code class="func">ModPCohomologyRingPresentation</code> (<a href="chap3.html#X85CFF2AB7A7A99D2"><b>3.3-1</b></a>) performs this spectral sequence calculation to find n and then calculates the cohomology ring using this value for n. In the example below we use this function, and by setting the value of <code class="func">InfoHAPprime</code> (<a href="chap1.html#X80E9D70E843A8C2C"><b>1.6-1</b></a>) to 1, we can see the details of the spectral sequence calculation.</p>
<table class="example">
<tr><td><pre>
gap> SetInfoLevel(InfoHAPprime, 1);
gap> G := SmallGroup(16, 3);;
gap> A := ModPCohomologyRingPresentation(G);
#I E_2 = GF(2)[ x_1, x_2 ] x GF(2)[ x_3, x_4 ]
#I with generator degrees [ 1, 1 ] and [ 1, 1 ] respectively
#I d_2(x_1) = zero
#I d_2(x_2) = zero
#I d_2(x_3) = x_1*x_2
#I d_2(x_4) = x_1^2
#I E_3 = GF(2)[ x_5, x_6, x_7, x_8, x_9 ]/[ x_6*x_9, x_6^2, x_5*x_6, x_5^2*x\
_7+x_9^2 ]
#I E_3 = GF(2)[ x_2, x_1, x_4^2, x_3^2, x_1*x_3+x_2*x_4 ]/[ x_1^2*x_3+x_1*x_\
2*x_4, x_1^2, x_1*x_2, x_1^2*x_3^2 ]
#I d_3(x_2) = zero
#I d_3(x_1) = zero
#I d_3(x_4^2) = zero
#I d_3(x_3^2) = x_1^2*x_2+x_1*x_2^2 = 0*Z(2) mod I
#I d_3(x_1*x_3+x_2*x_4) = zero
#I E_4 = GF(2)[ x_10, x_11, x_12, x_13, x_14 ]/[ x_11*x_14, x_11^2, x_10*x_1\
1, x_10^2*x_12+x_14^2 ]
#I E_4 = GF(2)[ x_2, x_1, x_4^2, x_3^2, x_1*x_3+x_2*x_4 ]/[ x_1^2*x_3+x_1*x_\
2*x_4, x_1^2, x_1*x_2, x_1^2*x_3^2 ]
#I d_4(x_2) = zero
#I d_4(x_1) = zero
#I d_4(x_4^2) = zero
#I d_4(x_3^2) = zero
#I d_4(x_1*x_3+x_2*x_4) = zero
#I E_inf = GF(2)[ x_10, x_11, x_12, x_13, x_14 ]/[ x_11*x_14, x_11^2, x_10*x\
_11, x_10^2*x_12+x_14^2 ]
#I E_inf = GF(2)[ x_2, x_1, x_4^2, x_3^2, x_1*x_3+x_2*x_4 ]/[ x_1^2*x_3+x_1*\
x_2*x_4, x_1^2, x_1*x_2, x_1^2*x_3^2 ]
#I Renaming indeterminates and sorting into increasing degree
Graded algebra GF(2)[ x_1, x_2, x_3, x_4, x_5 ] /
[ x_1*x_2, x_1^2, x_1*x_5, x_2^2*x_3+x_5^2 ] with indeterminate degrees
[ 1, 1, 2, 2, 2 ]
gap> # Now extract data about the presentation
gap> BaseRing(A);
GF(2)[x_1,x_2,x_3,x_4,x_5]
gap> GeneratorsOfPresentationIdeal(A);
[ x_1*x_2, x_1^2, x_1*x_5, x_2^2*x_3+x_5^2 ]
gap> IndeterminateDegrees(A);
[ 1, 1, 2, 2, 2 ]
gap> MaximumDegreeForPresentation(A);
4
</pre></td></tr></table>
<p>This (the correct cohomology ring) is in fact the same as the presentation computed in Section <a href="chap2.html#X81BCBAA18423E1C8"><b>2.2-1</b></a> using n=5 since there are no generators or relations of degree greater than four.</p>
<p><a id="X78F3639083A7DE62" name="X78F3639083A7DE62"></a></p>
<h5>2.2-3 <span class="Heading">Computing Poincaré series</span></h5>
<p>The Poincaré series for the mod-p cohomology ring H^*(G, F) is the infinite series</p>
<p class="pcenter">
a_0 + a_1x + a_2x^2 + a_3x^3 + ...
</p>
<p>where a_k is the dimension of the vector space H^k(G, F). The Poincaré function is a rational function P(x)/Q(x) which is equal to the Poincaré series.</p>
<p>The ranks of the modules in a minimal resolution for a group G are identical to the dimensions a_k, so a minimal resolution can be used to calculate the Poincaré series without first calculating the cohomology ring. This is the method used by the <strong class="pkg">HAP</strong> function <code class="func">PoincareSeries</code> (<a href="/home/pas/GAP/pkg/Hap1.8/doc/chap7.html#X850CDAFE801E2B2A"><b>HAP: PoincareSeries</b></a>), but will only give the correct answer for a sufficiently-long resolution. <strong class="pkg">HAP</strong> has a method for calculating a resolution that is likely to be long enough, but cannot prove that this is sufficient.</p>
<p><strong class="pkg">HAPprime</strong> can instead calculate a provably-correct Poincaré series for a mod-p cohomology ring, and without first calculating the ring itself. The final sheet of a Lyndon-Hochschild-Serre spectral sequence for a group G will be a ring with the same additive structure as the cohomology ring for G. This will thus have the same Poincaré series, and can be used to provide the Poincaré series for the cohomology ring without having to also compute the cohomology ring. This is implemented in the <strong class="pkg">HAPprime</strong> function <code class="func">PoincareSeriesLHS</code> (<a href="chap3.html#X7E1A4C8781A02CD0"><b>3.2-1</b></a>).</p>
<p>As well as being provably correct, <code class="func">PoincareSeriesLHS</code> (<a href="chap3.html#X7E1A4C8781A02CD0"><b>3.2-1</b></a>) is also often faster than the related <strong class="pkg">HAP</strong> function, as demonstrated in this example:</p>
<table class="example">
<tr><td><pre>
gap> G := SmallGroup(64, 210);;
gap> # Compute the Poincare series using HAP
gap> P1 := PoincareSeries(G);time;
(x_1^4+x_1^2+x_1+1)/(-x_1^7+3*x_1^6-5*x_1^5+7*x_1^4-7*x_1^3+5*x_1^2-3*x_1+1)
46434
gap> # Compute the Poincare series using HAPprime
gap> P2 := PoincareSeriesLHS(G);time;
(x_1^4+x_1^2+x_1+1)/(-x_1^7+3*x_1^6-5*x_1^5+7*x_1^4-7*x_1^3+5*x_1^2-3*x_1+1)
1889
gap> P1 = P2;
true
</pre></td></tr></table>
<p>In this case, <strong class="pkg">HAP</strong> needs to compute 14 terms of a resolution for this group of order 64 before it is confident that it has a stable Poincaré series. By contrast <strong class="pkg">HAPprime</strong>, in calculating the spectral sequence, needs to compute 5 terms of two resolutions of groups of order 8 and then construct a (non-minimal) resolution for G (also of length 5) from these two. Both methods give the same answer, but only <strong class="pkg">HAPprime</strong>'s is guaranteed to be correct.</p>
<p><a id="X87AD96A584D60140" name="X87AD96A584D60140"></a></p>
<h4>2.3 <span class="Heading">Comparing the memory usage and speed of <strong class="pkg">HAPprime</strong> and <strong class="pkg">HAP</strong>'s
<code class="keyw">ResolutionPrimePowerGroup</code> functions</span></h4>
<p>For small p-groups, the group ring FG can be considered as a vector space of rank |G| with the elements of G as its basis elements. Each module M_n in a FG-resolution is also a vector space (of dimension |M_n||G|) and the boundary maps d_n can be represented as vector space homomorphisms. As a result, standard linear algebra techniques can be used to compute a minimal resolution by constructing a sequence of module homomorphisms where the kernel of one map is the image of the next, and where the modules have minimal generating sets. See Chapter <a href="/home/pas/GAP/pkg/happrime-0.3.2/doc/datatypes/chap2.html#X7C0B125E7D5415B4"><b>HAPprime Datatypes: Resolutions</b></a> in the datatypes manual for further details.</p>
<p>As the groups get larger, this approach becomes less feasible due to the amount of time and memory needed to store and compute the null space of large matrices. The <strong class="pkg">HAP</strong> function <code class="func">ResolutionPrimePowerGroup</code> (<a href="/home/pas/GAP/pkg/Hap1.8/doc/chap1.html#X8735FC5E7BB5CE3A"><b>HAP: ResolutionPrimePowerGroup</b></a>) and the <strong class="pkg">HAPprime</strong> functions <code class="func">ResolutionPrimePowerGroupRadical</code> (<a href="chap3.html#X86934BE9858F7199"><b>3.1-1</b></a>) and <code class="func">ResolutionPrimePowerGroupGF</code> (<a href="chap3.html#X86934BE9858F7199"><b>3.1-1</b></a>) all use this linear algebra approach, but the <strong class="pkg">HAPprime</strong> functions are optimised to save memory, allowing the computation of resolutions which are longer, or are of larger groups, than are possible using <strong class="pkg">HAP</strong> alone.</p>
<p><a id="X85FFD31A7B362DFF" name="X85FFD31A7B362DFF"></a></p>
<h5>2.3-1 <span class="Heading"><strong class="pkg">HAPprime</strong> takes less memory to store resolutions</span></h5>
<p>Consider computing a resolution of a group of an arbitrary group of order 128, <code class="code">G = SmallGroup(128, 844)</code> using <strong class="pkg">HAP</strong>. Computation is performed on a dual-core Intel Core2Duo running at 2.66MHz, and the memory available to <strong class="pkg">GAP</strong> is the standard initial allocation of 256Mb.</p>
<table class="example">
<tr><td><pre>
gap> G := SmallGroup(128, 844);;
gap> R := ResolutionPrimePowerGroup(G, 9);
Resolution of length 9 in characteristic 2 for <pc group of size 128 with
7 generators> .
gap> time;
27685
gap> # Can we construct a resolution of length ten?
gap> R := ResolutionPrimePowerGroup(G, 10);
exceeded the permitted memory (`-o' command line option) at
res := SemiEchelonMatDestructive( List( mat, ShallowCopy ) );
called from
SemiEchelonMat( NullspaceMat( BndMat ) ) called from
ZGbasisOfKernel( i - 1 ) called from
<function>( <arguments> ) called from read-eval-loop
Entering break read-eval-print loop ...
you can 'quit;' to quit to outer loop, or
you can 'return;' to continue
</pre></td></tr></table>
<p>The <strong class="pkg">HAPprime</strong> function <code class="func">ResolutionPrimePowerGroupRadical</code> (<a href="chap3.html#X86934BE9858F7199"><b>3.1-1</b></a>) uses an almost identical algorithm, but stores its boundary maps more efficiently. As a result, with the same memory allowance:</p>
<table class="example">
<tr><td><pre>
gap> G := SmallGroup(128, 844);;
gap> R := ResolutionPrimePowerGroupRadical(G, 9);
Resolution of length 9 in characteristic 2 for <pc group of size 128 with
7 generators> .
No contracting homotopy available.
A partial contracting homotopy is available.
gap> time;
25321
gap> # Can we construct a resolution of length ten?
gap> R := ExtendResolutionPrimePowerGroupRadical(R);;
gap> # Yes! How about eleven?
gap> R := ExtendResolutionPrimePowerGroupRadical(R);
Resolution of length 11 in characteristic 2 for <pc group of size 128 with
7 generators> .
No contracting homotopy available.
A partial contracting homotopy is available.
gap> ResolutionModuleRanks(R);
[ 3, 6, 11, 19, 30, 44, 62, 85, 113, 146, 185 ]
gap>
gap> # But it will run out of memory if we try to go to twelve terms
gap> R := ExtendResolutionPrimePowerGroupRadical(R);
exceeded the permitted memory (`-o' command line option) at
...
</pre></td></tr></table>
<p>The <strong class="pkg">HAPprime</strong> version can compute two further terms of the resolution, which given the sizes of the additional modules represents a considerable improvement. Just representing the homomorphism d_10: (FG)^146 -> (FG)^113 as vectors requires nearly as much memory again as representing the first nine homomorphisms. To compute and store the same resolution of length 11 using <code class="func">ResolutionPrimePowerGroup</code> (<a href="/home/pas/GAP/pkg/Hap1.8/doc/chap1.html#X8735FC5E7BB5CE3A"><b>HAP: ResolutionPrimePowerGroup</b></a>) would need a little over three times the memory used here by <strong class="pkg">HAPprime</strong>. The time taken by both versions is very similar.</p>
<p>In the example above, note also the use of the <strong class="pkg">HAPprime</strong> function <code class="func">ExtendResolutionPrimePowerGroupRadical</code> (<a href="chap3.html#X7B435C307F28D44F"><b>3.1-2</b></a>), which makes it much easier to add terms to an existing resolution. In standard <strong class="pkg">HAP</strong>, if one decides that a resolution is too short and that more terms are required, then the entire resolution must be computed again from scratch.</p>
<p><a id="X848CF4C483C3F6E4" name="X848CF4C483C3F6E4"></a></p>
<h5>2.3-2 <span class="Heading"><strong class="pkg">HAPprime</strong> takes less memory to compute resolutions</span></h5>
<p>The function <code class="func">ResolutionPrimePowerGroupGF</code> (<a href="chap3.html#X86934BE9858F7199"><b>3.1-1</b></a>) uses a new algorithm to compute the kernel of FG-module homomorphisms when FG-modules are represented using a set of G-generating vectors (see <a href="/home/pas/GAP/pkg/happrime-0.3.2/doc/datatypes/chap6.html#X82F28552819A6542"><b>HAPprime Datatypes: FG-module homomorphisms</b></a> in the datatypes reference manual). This provides a further memory saving over <code class="func">ResolutionPrimePowerGroupRadical</code> (<a href="chap3.html#X86934BE9858F7199"><b>3.1-1</b></a>), although at the cost of a much slower computation time:</p>
<table class="example">
<tr><td><pre>
gap> G := SmallGroup(128, 844);;
gap> R := ResolutionPrimePowerGroupGF(G, 9);
Resolution of length 9 in characteristic 2 for <pc group of size 128 with
7 generators> .
No contracting homotopy available.
A partial contracting homotopy is available.
gap> time;
422742
gap> R := ExtendResolutionPrimePowerGroupGF(R);;
gap> R := ExtendResolutionPrimePowerGroupGF(R);;
gap> R := ExtendResolutionPrimePowerGroupGF(R);;
gap> R := ExtendResolutionPrimePowerGroupGF(R);;
gap> R := ExtendResolutionPrimePowerGroupGF(R);;
gap> R := ExtendResolutionPrimePowerGroupGF(R);;
Resolution of length 15 in characteristic 2 for <pc group of size 128 with
7 generators> .
No contracting homotopy available.
A partial contracting homotopy is available.
gap> ResolutionModuleRanks(R);
[ 3, 6, 11, 19, 30, 44, 62, 85, 113, 146, 185, 231, 284, 344, 412 ]
gap> # But it will run out of (the inital 256Mb) of memory at sixteen terms
</pre></td></tr></table>
<p>Using <code class="func">ResolutionPrimePowerGroupGF</code> (<a href="chap3.html#X86934BE9858F7199"><b>3.1-1</b></a>) we can get a further four terms of the resolution. For this resolution, this represents a memory saving of a factor of five over <code class="func">ResolutionPrimePowerGroupRadical</code> (<a href="chap3.html#X86934BE9858F7199"><b>3.1-1</b></a>) and fifteen over <code class="func">ResolutionPrimePowerGroup</code> (<a href="/home/pas/GAP/pkg/Hap1.8/doc/chap1.html#X8735FC5E7BB5CE3A"><b>HAP: ResolutionPrimePowerGroup</b></a>), although it does take fifteen times as long as either of those just to compute the first nine terms, and scales less well with size.</p>
<p><a id="X7CA386948072CFF4" name="X7CA386948072CFF4"></a></p>
<h5>2.3-3 <span class="Heading">Automatic selection of the best method</span></h5>
<p>The two functions <code class="func">ResolutionPrimePowerGroupRadical</code> (<a href="chap3.html#X86934BE9858F7199"><b>3.1-1</b></a>) and <code class="func">ResolutionPrimePowerGroupGF</code> (<a href="chap3.html#X86934BE9858F7199"><b>3.1-1</b></a>) offer a trade-off between time and memory. The function <code class="func">ResolutionPrimePowerGroupAutoMem</code> (<a href="chap3.html#X86934BE9858F7199"><b>3.1-1</b></a>) automates the decision of which version to use, switching from the <code class="code">Radical</code> to the <code class="code">GF</code> version when it estimates that it is about to run out of available memory for the faster version. In this example, we have also increase the <code class="func">InfoHAPprime</code> (<a href="chap1.html#X80E9D70E843A8C2C"><b>1.6-1</b></a>) info level to display progress information. At level two, the rank of each module in the resolution is displayed as it is calculated, giving an indication of progress. With this setting, the user is also notified when the <code class="code">AutoMem</code> function switches, and the <code class="code">GF</code> function displays a rolling estimate of its completion time (which is not shown since that output is overwritten when completed)</p>
<table class="example">
<tr><td><pre>
gap> G := SmallGroup(128, 844);;
gap> SetInfoLevel(InfoHAPprime, 2);
gap> R := ResolutionPrimePowerGroupAutoMem(G, 15);
#I Dimension 2: rank 6
#I Dimension 3: rank 11
#I Dimension 4: rank 19
#I Dimension 5: rank 30
#I Dimension 6: rank 44
#I Dimension 7: rank 62
#I Dimension 8: rank 85
#I Dimension 9: rank 113
#I Finding kernel of homomorphism by splitting:
#I - Finding kernel of U
#I - Finding kernel of V
#I - Finding intersection of U and V
#I - Finding intersection preimages
#I Dimension 10: rank 146
#I Finding kernel of homomorphism by splitting:
#I - Finding kernel of U
#I - Finding kernel of V
#I - Finding intersection of U and V
#I - Finding intersection preimages
#I Dimension 11: rank 185
#I Finding kernel of homomorphism by splitting:
#I - Finding kernel of U
#I - Finding kernel of V
#I - Finding intersection of U and V
#I - Finding intersection preimages
#I Dimension 12: rank 231
#I Finding kernel of homomorphism by splitting:
#I - Finding kernel of U
#I - Finding kernel of V
#I - Finding intersection of U and V
#I - Finding intersection preimages
#I Dimension 13: rank 284
#I Finding kernel of homomorphism by splitting:
#I - Finding kernel of U
#I - Finding kernel of V
#I - Finding intersection of U and V
#I - Finding intersection preimages
#I Dimension 14: rank 344
#I Finding kernel of homomorphism by splitting:
#I - Finding kernel of U
#I - Finding kernel of V
#I - Finding intersection of U and V
#I - Finding intersection preimages
#I Dimension 15: rank 412
Resolution of length 15 in characteristic 2 for <pc group of size 128 with
7 generators> .
No contracting homotopy available.
A partial contracting homotopy is available.
gap> StringTime(time);
" 5:45:53.613"
</pre></td></tr></table>
<div class="chlinkprevnextbot"> <a href="chap0.html">Top of Book</a> <a href="chap1.html">Previous Chapter</a> <a href="chap3.html">Next Chapter</a> </div>
<div class="chlinkbot"><span class="chlink1">Goto Chapter: </span><a href="chap0.html">Top</a> <a href="chap1.html">1</a> <a href="chap2.html">2</a> <a href="chap3.html">3</a> <a href="chapInd.html">Ind</a> </div>
<hr />
<p class="foot">generated by <a href="http://www.math.rwth-aachen.de/~Frank.Luebeck/GAPDoc">GAPDoc2HTML</a></p>
</body>
</html>
distrib
>
Mandriva
>
2010.0
>
i586
>
media
>
contrib-release
>
by-pkgid
>
91213ddcfbe7f54821d42c2d9e091326
>
files
>
1510
