> < ^ From:

< ^ Subject:

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; fi; od; Append(v,[i]); od; return(v); end;

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; od; return(v); end;

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

...

fi;

Append(v,[i]);

A.representative.sylowSubgroups[2].parent := group;

od;

return(v);

end;

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.

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

> < [top]