-
Notifications
You must be signed in to change notification settings - Fork 161
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Inefficiencies in StructureDescription #160
Comments
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. |
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. |
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). |
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. |
Ah, yes, CRISP indeed made a difference, now it only takes 20 seconds. :-) |
I've run some parallel checks of the performance of I am going to post details of the setup elsewhere; for now, the essential command was
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:
|
The documentation of StructureDescription specifically warns that it can be slow for p-groups. On the other hand DirectFactorsOfGroup is a natural enough operation, so speeding that up (and documenting it) could be useful.
|
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. |
On second thought, it might be better to do this with Z(G) instead of G'. I will think it through. |
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. I am implementing the code into grpnames.g? |
I notice that the input to the algorithm in that paper is the group given in the form of a multiplication table.
|
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. |
On 27 Apr 2015, at 16:04, james-d-mitchell notifications@github.com wrote:
Thanks, but I can't reproduce this (tip of the master branch, GAP started with |
I deleted the comment almost immediately after I made it, it was my On Wed, 29 Apr 2015 at 21:46 Alexander Konovalov notifications@github.com
|
After a busy summer break and an even more busy September, I came back to optimizing the DirectFactorsOfGroup code. During the testing of several different algorithms, I came across a problem, which is probably some stupid coding mistake on my part, but somehow I cannot rectify this on my own. The following code is a rewriting of the original DirectFactorsOfGroup code as
However, testing shows that on a 96-element group it gives only two direct factors, rather than the correct three, if_CRISP_is_used. Without CRISP it gives the correct result. The code: DeclareOperation( "IsTrivialNormalIntersectionInList",[IsList, IsGroup, IsGroup]); ############################################################################# #M IsTrivialNormalIntersectionInList( , , ) . . . . generic method InstallMethod( IsTrivialNormalIntersectionInList, function( L, U, V )
end); InstallGlobalFunction( DirectFactorsOfGroupFromList, function ( G, NList, MinList )
end ); With CRISP I have only two direct factors. gap> G := Group([ (6,7)(8,9)(10,11)(12,13)(14,15)(16,17)(18,19)(20,21)(22,23)(24,25), (3,4)(6,8)(13,15)(16,18)(23,25), (8,9)(12,13)(16,17)(20,21)(24,25) ]); Without CRISP I have the correct three direct factors. gap> G := Group([ (6,7)(8,9)(10,11)(12,13)(14,15)(16,17)(18,19)(20,21)(22,23)(24,25), (3,4)(6,8)(13,15)(16,18)(23,25), (8,9)(12,13)(16,17)(20,21)(24,25) ]); Could someone tell me what I am doing wrong in the code? Edit: somehow some comments of the code came out in a very ugly formatting, so I just removed them. |
@hungaborhorvath |
My results are with CRISP 1.3.9. I downloaded them from the page you suggested, as well. Edit: I tried it again with a completely new gap on a different machine. I cloned https://github.com/gap-system/gap, compiled it, put only GAPDoc 1.5.1 and CRISP 1.3.9 into pkg, loaded the above code and obtained only 2 direct factors. If I removed the CRISP folder from pkg, then it gave me 3 direct factors. Edit2: Another interesting thing I noticed is that if there are some previous other computations in the same GAP session, then it produces the correct answer with CRISP, as well. E.g. if I start with the code H := Group([ (2,3)(4,5)(7,8)(9,10), (4,5)(9,10), (3,11)(6,12)(9,13) ]); then afterwards the direct factors of above G are computed as they should. I am not entirely sure what other previous computations will make this difference, but I have now reproduced this on two different machines, both are Debian Jessie based systems with Bunsenlabs netinstall if matters, and the gap is a cloned version of the github one, freshly compiled, only GAPDoc 1.5.1 and CRISP 1.3.9. |
@hungaborhorvath DirectFactorsOfGroupFromList(G, NormalSubgroups(G), MinimalNormalSubgroups(G)); a number of times. About one in three attempts, it fails. (Also tried switching back to gmp 5, but as expected, this doesn't change anything.) I cannot reproduce the problem with the stable-4.7 branch – even when running the above code 1000 times. In fact, if one sets the assertion level to 1, a CRISP routine detects an inconsistency: a modulo pcgs returns wrong exponents, e.g., at the break caused by the assertion, enter ExponentsOfPcElement (gpcgs, gpcgs[1]); which will return [0,0] instead of [1,0]. However, I don't know the perm pcgs code well enough to further diagnose this. Cheers Burkhard. |
Something is very fishy here..... I tried it with v4.7.5 (this is the gap version bundled with debian jessie). With CRISP it seems to give the right result all the time. Without CRISP, it still gives 3 direct factors, but one of the factors is changing if I call the code again..... ┌───────┐ GAP, Version 4.7.5 of 24-May-2014 (free software, GPL) The first factors in the two separate runs are even setwise different (but of course they are isomorphic). BTW, is this the right place to report this problem, or should I make a separate issue? |
The issue with the GAP master branch seems to be resolved now (see #327). |
What is the status of this issue? It seems that the initial computations @alex-konovalov tried still are slow, as it still tries to find all normal subgroups, and there are just too many Personally, I'd argue that this is not really an issue, but just life... Even if we improve the algorithm further, I am sure we'll be able to find new cases where it does not perform well. |
These are all timings on my own laptop with current master:
Of course I have no idea how these compare to the timings of @alex-konovalov , but the first two groups did not even give a result in half an hour, so I would not call this slow.... Edit: I just ran the last four groups on my laptop using the old
|
@hungaborhorvath thanks for the edit - that's exactly what I was going to ask. I think this may now be closed. It lead to some improvements, and I agree with @fingolfin that the corner cases are "just life". |
I've just came across two examples:
SmallGroup(256, 56091)
andSmallGroup(512,10494180)
whereStructureDescription
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.The text was updated successfully, but these errors were encountered: