> < ^ Date: Mon, 10 Apr 1995 19:28:00 +0100 (WET)
> < ^ From: Martin Schoenert <martin.schoenert@math.rwth-aachen.de >
< ^ Subject: Re: Memory Use
Walter Carlip wrote in his e-mail message of 1995/03/29

I'm puzzled by Gap's use of memory. I find that "Gasman" fails to obtain
"bags" for many computations I attempt. Let me give a particular
example. I was investigating the cardinality of the set
{g | <A,g> has abelian Sylow 2-subgroup} as A ranges over the conjugacy
classes of subgroups of a group G and g ranges over elements of G. I
have Gap the group G = SymmetricGroup(6), which is not too large (720).
While Gap had no difficulty computing the ConjugacyClassesSubgroups, or
doing other computations with G, it choked on my program:

Myvector := function(group,classes,prime)
  local A,g,i,v;    v:=[];
  for A in classes do
    i:= 0;
    for g in Elements(group) do
      if IsAbelian(SylowSubgroup(Closure(A.representative,g),prime)) then
        i:= i+1;

Sorry that it took me so long to answer, but I had a hard time to find
the reason for this problem (an early experiment lead me totally astray).
This behaviour is caused by a bug in the GAP library. This problem will
be fixed in the upgrade to 3.4.2. If you can't wait until then, simply
insert the following line in your function.

Myvector := function(group,classes,prime)
  local A,g,i,v;    v:=[];
  for A in classes do
    i:= 0;
    Append(v,[i]);  # why don't you use 'Add(v,i)' here?
    A.representative.sylowSubgroups[2].parent := group;

With this modification the entire computation can be done with a 16 MByte
workspace. It can be made quite a bit faster if you first test whether
the Sylow subgroup of the representative itself is abelian, before you
extend the representative with all the elements.

Myvector := function(group,classes,prime)
local A,g,i,v; v:=[];
for A in classes do
i:= 0;
if IsAbelian(SylowSubgroup(A.representative,2)) then
A.representative.sylowSubgroups[2].parent := group;

There are of course many additional tricks that can be used to speed up
this computation. Probably the most worthwhile is to test the size of
the closure first, to avoid to compute the Sylow subgroup. If 4 does not
divide 'Size(<closure>)', then <closure> has an abelian Sylow subgroup.
On the other hand, if 16 divides 'Size(<closure>)', then <closure> has a
non-abelian Sylow subgroup.

And now for those who are interested, a description of the problem.

GAP stores in 'group.conjugacyClassesSubgroups' the list of conjugacy
classes. If <class> is such a class, '<class>.representative' is its
representative. If <class> has been handled in the outer for-loop, then
'<class>.representative.sylowSubgroups[2]' is a Sylow 2-subgroup of the
representative (this is computed during the first iteration through the
inner for-loop, when the representative is extended with the identity).
This subgroup <sylow> should contain in '<sylow>.parent' a reference
back to 'group'.

But in certain situations (basically if '<class>.representative' or an
appropriate factor acts transitively but imprimitively), a copy of
'group' is made and assigned to '<sylow>.parent'. This is a full copy of
'group', i.e., the conjugacy classes, their representatives, and the
Sylow subgroups of the representatives are also copied. Thus the size of
the data approximately doubles.

This doubling happens every time the certain situation occurs. Until the
30th class it happens only once or twice, so it is not a problem. But
after that it happens for almost every class, so it comes to an
exponential explosion. After the 46th class, the data occupies about
32 MByte. By extrapolation we see that we would need about 32 GByte to
complete the computation.

Walter Carlip continued

Question: Is Gap having difficulty with this because it attempts to save
every bit of information it computes, i.e., a list of each subgroup <A,g>
together with its sylow 2-subgroup? If this is the problem, is there a
way to tell Gap to discard intermediate results (when known to be no
longer needed)?

GAP saves the group, its conjugacy classes, their representative, and the
Sylow subgroups of the representatives. But this is not a problem, all
in all it amounts to less than 1/2 MByte. GAP does *not* remember each
subgroup <A,g> together with its Sylow subgroup. But if GAP would store
those, then the way to discard them would be to find out where they are
saved, and to use 'Unbind' to get rid of them.

Hope this helps.


-- .- .-. - .. -.  .-.. --- ...- . ...  .- -. -. .. -.- .-
Martin Sch"onert,   Martin.Schoenert@Math.RWTH-Aachen.DE,   +49 241 804551
Lehrstuhl D f"ur Mathematik, Templergraben 64, RWTH, 52056 Aachen, Germany

> < [top]