Inefficiencies in StructureDescription

[olexandr-konovalov]

I've just came across two examples: SmallGroup(256, 56091) and SmallGroup(512,10494180) where StructureDescription takes enormously long time. It was running long enough without returning anything until I've interrupted the calculation - while it works for many other groups of these orders, even though it may take a while for some of them.

[stevelinton]

I had a look at the order 256 example. This group has almost 30000 normal subgroups, and once it has found those (takes about 11 seconds for me) it has to consider all pairs of appropriate orders to see if they are direct factors. The code for this in DirectFactorsOfGroup is not efficient. In particular it contains the line if IsTrivial( Intersection( N[i], N[j] ) ) which computes the exact intersection when all you want to know is whether it is trivial. Something like ForAll(N[i], IsOne(x) or not x in N[j]) would work better for these relatively small groups.

Actually an operations IntersectTrivially would be generally useful and often quicker than Intersection.

I think though that StructureDescription really needs a completely different approach for p-groups. It makes much more sense to describe them via one of the natural series. If you wanted a DirectFactorsOfGroup method I suspect a faster one could also be developed for these groups.

[stevelinton]

This group also has a large automorphism group, under which the normal subgroups fall into quite large orbits. There is no point in checking more than one subgroup from an orbit as a direct factor. ComplementClassesReps might also provide a faster way to do the check. In fact, using these two tricks I can show that it is not a direct product in a few seconds.

[hungaborhorvath]

Some weeks ago I have forked grpnames.g? to rewrite SemidirectFactorsOfGroup, because it was also very inefficient. I will look into the code of DriectFactorsOfGroup, as well, and make it more efficient. Thank you for the ideas.

BTW, what machine did you run it on so that it only took 11 seconds? It took my 2 years old laptop four and a half minutes just to compute NormalSubgroups for the 256 element example. The same calculation took slightly more than two minutes on a supercomputer (only used one node, though).

[stevelinton]

That's just a nearly three year old MacBookPro. I just rechecked and it's about 11.5 seconds. I do have CRISP loaded and I think some of the methods from that package make a difference.

In working on functions like these, you need to beware of changes that make them much faster for one type of group and much slower for another -- for instance computing the automorphism group may help a lot if there are many normal subgroups, but might be very slow to little purpose in other groups.

[hungaborhorvath]

Ah, yes, CRISP indeed made a difference, now it only takes 20 seconds. :-)

[olexandr-konovalov]

I've run some parallel checks of the performance of StructureDescription using 48 SCSCP servers.

I am going to post details of the setup elsewhere; for now, the essential command was

res:=ParListWithSCSCP( a, "StructureDescriptionById": noretry, timeout:=limit);

which permits to specify the upper limit for the number of seconds to waiting for the result of the remote procedure call and do not resubmit failed RPCs. This option is very useful for finding examples demonstrating the worst-case behaviour of the implementation.

That's what I've observed so far:

• order 64: each group takes less than a second, except [64,266] taking 6 seconds
• order 128: groups taking more than 10 seconds are those with numbers 2300, 2326, 2327

[stevelinton]

The documentation of StructureDescription specifically warns that it can be slow for p-groups.
I also think that it is simply not very useful or appropriate for p-groups — there are better ways to see their structure.

On the other hand DirectFactorsOfGroup is a natural enough operation, so speeding that up (and documenting it) could be useful.

Steve

On 21 Apr 2015, at 14:37, Alexander Konovalov notifications@github.com wrote:

I've run some parallel checks of the performance of StructureDescription using 48 SCSCP servers.

I am going to post details of the setup elsewhere; for now, the essential command was

res:=ParListWithSCSCP( a, "StructureDescriptionById": noretry, timeout:=limit);

which permits to specify the upper limit for the number of seconds to waiting for the result of the remote procedure call and do not resubmit failed RPCs. This option is very useful for finding examples demonstrating the worst-case behaviour of the implementation.

That's what I've observed so far:

• order 64: each group takes less than a second, except [64,266] taking 6 seconds
• order 128: groups taking more than 10 seconds are those with numbers 2300, 2326, 2327
—
Reply to this email directly or view it on GitHub.

[hungaborhorvath]

I am thinking that there should be a separate method for Abelian groups (maybe calculating from AbelianInvariants, or simply from G^p, G^{p^2}, whatever), and then for a general nonperfect group one could try to lift a decomposition of G/G' into a possible decomposition of G using (A \times B)'=(A') \times (B'). I will think about it and try to code it. I think it should be faster than the current decomposition.

[hungaborhorvath]

On second thought, it might be better to do this with Z(G) instead of G'. I will think it through.

[hungaborhorvath]

Neeraj Kayal and Timur Nezhmetdinov gave a fast algorithm for direct product decomposition:

Neeraj Kayal and Timur Nezhmetdinov, Factoring Groups Efficiently, in International Colloquium on Automata, Languages and Programming (ICALP) , Springer Verlag, 2009.
http://research.microsoft.com/apps/pubs/default.aspx?id=102435

I am implementing the code into grpnames.g?

[stevelinton]

I notice that the input to the algorithm in that paper is the group given in the form of a multiplication table.

For many groups, simply writing that down will be infeasibly slow or memory consuming, although it might be useful for p-groups for small p such as the ones that started this discussion.

Steve

On 25 Apr 2015, at 18:54, hungaborhorvath notifications@github.com wrote:

Neeraj Kayal and Timur Nezhmetdinov gave a fast algorithm for direct product decomposition:

Neeraj Kayal and Timur Nezhmetdinov, Factoring Groups Efficiently, in International Colloquium on Automata, Languages and Programming (ICALP) , Springer Verlag, 2009.
http://research.microsoft.com/apps/pubs/default.aspx?id=102435

I am implementing the code into grpnames.g?

—
Reply to this email directly or view it on GitHub.

[hungaborhorvath]

I read through the algorithm. For centerless groups I think it is basically polynomial (probably quadratic) in the number of conjugacy classes of G (after they are computed). For groups having Abelian factors it is pretty fast. For non-centerless groups having only nonabelian factors you actually need to go through 2^s subsets, where s is some bound on the number of direct factor components (and they can only bound s by log |G|). So It is not that bad.

Of course, if there are very few normal subgroups, then it is faster to check them. After I implemented the algorithm, I will compare the old and the new method and see which should be used when.

There are some obvious possible enhancements. For example if the group is nilpotent, then we know that it is the direct product of its Sylow subgroups, so we really need to decompose those. Or if the group is given as a direct product, then again, we already have a decomposition to start with. I also think that the bound on s can be decreased by checking e.g. the number of minimal normal subgroups.

In fact, all of the groups mentioned in the thread have only one minimal normal subgroup, therefore they cannot be decomposed as a direct product. I think for solvable group it is cheap to calculate minimal normal subgroups (for p-groups they are contained in the center), so this could be a very quick way to decide for some p-groups that they are direct indecomposable.

[olexandr-konovalov]

On 27 Apr 2015, at 16:04, james-d-mitchell notifications@github.com wrote:

I'm not sure if this is related to changes made here or not, but currently at the tip of the master branch doing StructureDescription(Group(())) returns fail where as in GAP 4.7.7 it returns "1".

Thanks, but I can't reproduce this (tip of the master branch, GAP started with -r -A).

[james-d-mitchell]

I deleted the comment almost immediately after I made it, it was my
mistake, nothing to do with anything in this issue.

On Wed, 29 Apr 2015 at 21:46 Alexander Konovalov notifications@github.com
wrote:

On 27 Apr 2015, at 16:04, james-d-mitchell notifications@github.com
wrote:

I'm not sure if this is related to changes made here or not, but
currently at the tip of the master branch doing
StructureDescription(Group(())) returns fail where as in GAP 4.7.7 it
returns "1".

Thanks, but I can't reproduce this (tip of the master branch, GAP started
with -r -A).

—
Reply to this email directly or view it on GitHub
https://github.com/gap-system/gap/issues/160#issuecomment-97580508.[image:
Web Bug from
https://github.com/notifications/beacon/AGYFdxgxvebM86Zjet--_sAyvEre2DaOks5oETptgaJpZM4EEHgq.gif]