<Section>
    <Heading>The Memory Problem</Heading>
    
    (to finish properly - just a sketch so far)
    <P/>
    The problem with the standard approach is that each stage of the 
    resolution requries more and more memory to calculate. The 
    <Package>HAP</Package> computes the resolution in the fast, naive 
    way. The important stage here is computing the kernel of a module 
    homorphism. In the 
    standard <Package>HAP</Package> case, a homorphism is represented
    by a <M>m</M> by <M>n|G|</M> matrix of generators. This is expanded out
    to a full <M>m|G|</M> by <M>n|G|</M> F-homorphism matrix and the kernel
    found using &GAP;'s <K>NullspaceMat</K>, which needs about 2.5 times the 
    storage of the input matrix.
    <P/>
    <Package>HAPprime</Package> makes more use of the module structure
    to compute the kernel without ever expanding the whole F-homorphism
    matrix, and so saving a lot of memory.
    <P/>
    One solution is to divide the homorphism <M>M</M> into two halves 
    (which we shall call <M>U</M> and <M>V</M>). The kernel of the 
    homorphism is then the sum of the kernels of <M>U</M> and <M>V</M>,
    together with the pre-image in <M>U</M> and <M>V</M> of the 
    intersection of <M>U</M> and <M>V</M>.
    <P/>
    The kernels of <M>U</M> and <M>V</M> can be computed in exactly
    the same manner, so this part is divide-and-conquer. Unfortunately,
    the intersection of <M>U</M> and <M>V</M> cannot be computed in a
    divide and conquer manner. What is worse, the standard &GAP; method
    for computing the intersection of two spaces 
    (<K>SumIntersectionMat</K>) would take 3.5 times the memory of the 
    original <M>m|G|</M> by <M>n|G|</M> matrix, i.e. worse than the naive
    approach!
    
    </Section>
    
    <Section>
    <Heading>Solution 1: Using Compressed F-Echelon Representation</Heading>
      
    The standard method for calculating the intersection of two vector spaces
    starts with having a F-basis for both in echelon form. We have developed
    a method for expressing an echelon F-basis in a compressed form, which 
    only takes about 1/30 the memory of expressing the full expanded F-basis.
    We can do this for each of <M>U</M> and <M>V</M> in turn, and then 
    calculate the intersection while leaving one of them in compressed form: 
    this only takes about twice as as much memory as the full expansion of 
    either <M>U</M> or <M>V</M>. 
    <P/>
    However, this is slow and it it is not obvious how the memory usage can be
    reduced further.
    
    </Section>
    <Section>
    <Heading>Solution 2: G-Echelon Generators</Heading>
      
    The problem with Solution 1 is computing the intersection. Solution 2
    massages the homorphism generators to make the intersection as small 
    as possible (and ideally to zero).
    <P/>
    The function <K>EchelonModuleGenerators</K> takes a set of module 
    generators and returns a new set for the same module, but which are 
    in something close to a semi-echelon form. Consider the following 
    example:
<Example><![CDATA[
gap> G := SmallGroup(16, 5);
<pc group of size 16 with 4 generators>
gap> v := RandomMat(6, 64, GF(2));
<a 6x64 matrix over GF2>
gap> DisplayModule(v,G);
[...11.1.11...11.|1.1.111.11.1.11.|.......111..1111|11.1..11.1.11..1]
[..1..1..1111.111|11..1..1....1..1|.1..11.11..1.11.|.....111....11..]
[.111..1.1111.11.|...11111.1...1.1|.1.1111.....11.1|..1.11111.11....]
[.1..11....11...1|111.1..1..1..111|.1.11....1.11..1|1.111.1.1111.111]
[.1.1...1...1.1..|...1111..11.....|.1..1..1.....1.1|1111.11....11.11]
[11....1.1..1.1.1|11.111111.11.1.1|1.111..1.......1|.1.1....1.1..11.]
gap> e := EchelonModuleGenerators(v, G);;
gap> DisplayModule(e.generators,G);
[.1.1...1...1.1..|................|................|................]
[................|...............1|................|................]
[................|11....1......1..|................|................]
[................|................|..111..1..1.11..|................]
[................|................|................|11.1.1..1.111.1.]
]]></Example>
    Both sets of vectors generate exactly the same vector space, but 
    the generators after <K>EchelonModuleGenerators</K> are in a much 
    nicer form. The modules generates by rows 1, 4 and 5 are independent,
    as is the module generated by the combination of rows 2 and 3. The 
    nullspace of the overall matrix is simply the sum of the 
    nullspaces of those four subspaces: there is no intersection to be
    calculated.
    <P/>
    This split nullspace calculation can be performed using the function
    <K>GensNullspaceGModuleNew</K>:
<Example><![CDATA[
gap> GensNullspaceGModuleNew(rec(gens:=e.generators, group:=G));
[ <a GF2 vector of length 80> ]
]]></Example>

    <P/> 
    In the case of the kernels required for a resolution, the decomposition
    is rarely as nice, but it is still hoped that the intersection will
    be small (this still needs checking, however!).
      
    </Section>