Knowing the Center makes it impossible to compute NormalSubgroups #369
Comments
|
I did some checking about the known attributes of G after computing the center: gap> KnownAttributesOfObject(G); If I call Size and OrbitsDomain, then I have all of these attributes, except for the center, and GAP still computes the normal subgroups without a hitch: gap> Size(G); Therefore the Centre attribute must be the one that causes the problem. However, a simple grep HasCent lib/* only gave me lib/alglie.gi in the function LieCentre, which is about algebras, not groups. |
|
@hungaborhorvath Thanks. Could you please try to debug this using TraceMethods, ApplicableMethods etc? You may try this in the master branch here, which has some recent improvements by @ChrisJefferson. |
|
If nobody will do it, then I will make an attempt. However, I have never used ApplicableMethod, in fact even ApplicableMethod(Size, G); gave me an error message. :-( TraceMethod(NormalSubgroups, ChiefSeries); gives me the following if the Center is calculated: gap> NormalSubgroups(G);; If the Center was not known originally, then I do not get the two ChiefSeries getter lines: gap> NormalSubgroups(G);; Further, 'Many complements' error message (according to grep) can only be found in the function SubgroupsSolvableGroup, which cannot be traced by TraceMethod. It might be called from line 1934 of lib/grplatt.gi, but I do not know how to make sure. :-( |
olexandr-konovalov
added
the
kind: bug
|
@hungaborhorvath : Agree that the Chief Series looks very different. We get there from This branch of code is never run if we don't run Center first, I'm not entirely sure why, I'm hoping someone will pop up who is more expert in this. It's possible (and would be annoying) that for some reason you just get a bad ChiefSeries, which is never promised to be unique. But I'm hoping someone can do better than that. |
|
I can reproduce this with GAP 4.6.5 and 4.5.7. Haven't tried other releases yet. Could someone try 4.4.12? |
|
In fact, we can prove it's the Unfortunately, this is well outside my area of expertise I'm afraid. |
|
@hungaborhorvath The correct syntax is |
|
@ChrisJefferson And Anyway, I thinkt the person with most expertise on this code is @hulpke so hopefully he knows more |
|
@hungaborhorvath and in addition, to make the output informative, G should not have size known already - otherwise you will get just the system getter instead of actual methods that may be applied. |
I think this is an unavoidable side-effect: Calculating the center happens to use a chief series, which then is stored and this one particular chief series does not work well. This could happen in other situations. What is happening is that the normal subgroups code — my ISSAC paper from ’98 - in some cases uses invariant subgroups as there seem to be many complements. This is code which currently does not use the solvable radical, though this might be useful, if only for consistency. Alexander
|
|
Ahh, of course -- I did not read the initial report carefully enough, and was under the impression that there was a wrong result. But now I see that the algorithm just takes a loooong time. That indeed makes sense. Using the solvable radical method then indeed should resolve this (in particular, ensure this computation always succeds in a timely fashion, no matter whether you computed a center first or not ;). |
|
I am sorry, but I do not understand. HasChiefSeries(G) returns false whether or not I calculate Center(G) first. In my second post I wrote what are the known attributes of G after computing the center, and ChiefSeries is not among them. |
|
No, but |
stevelinton
added
kind: enhancement
|
You can see the basic distinction in the following: Neither Chief series is wrong, they just differ in the order of the factors, and it turns out one of them is better than the other for the algorithms that lists all the normal subgroups. Obviously it would be good to improve the normal subgroups algorithm to automatically choose a good chief series, but I have no idea if this is feasible. |
|
Having the series go through the solvable radical did not help (in fact it turns out in this example to always run in the bad case ….), but I think I have a solution: The problem arises if in a subgroup there are tons of normal complements, but few of which are normal in the whole group. In this case it is worth to look at the action on complements on the cohomology side (an affine linear action) to determine those which remain fixed under the whole group. I have implemented this (the action is a bit tricky in the case of groups which are not solvable) and in the example it removes the problem (and gives a notable speedup). While teststandard.g runs OK, it has — as any such changes — the potential to mess up manual examples or package tests. I’m happy to commit the change now, but I’m also happy to wait for after 4.8. Any opinions? Best, Alexander |
|
I would vote for now. I would start it testing by testing my new DirectFactorsOfGroup algorithm. |
|
We don't normally vote on such things... @hulpke Well, the "standard" way, IMHO, would be for you to open a pull request with your changes, so that people can test it (e.g. @hungaborhorvath ) and possible review it; also, the test suite is run on all PRs. Then we can decide whether to merge it. |
|
@fingolfin I understand. However my setup (this is a relic of the switch to git...) is that I'm working off the main repository. I think to be able to do pull requests, I will need to work with a copied repository. Doing so is on my list for the winter break. |
|
@hulpke No, not at all. I do all my work in a single clone of the gap repository, just on multiple branches. :) |
|
@fingolfin I looked at the documentation and it said that for pull requests I need to fork the main repository. I have not done this. Can I do a pull request in my situation? |
|
@hulpke OK - my understanding is that you have now some changes implemented in the clone of the main GAP repository, which you haven't committed yet, and now you would like to do a pull request, so you want to have them in fork. I think the following would work:
Step-by-step guidance IMHO should be like that, assuming that you start in the directory
Now you will see that it points to the main repository To change this, do:
After that, others will be able to see your changes even before you will submit a pull request. I suggest to do this first (you will need to do these steps only once!), and then think about PR after that. |
|
@alex-konovalov in my part of git. My setup now (on office and home machine) is: [Abulafia:~/gap4] ahulpke% git remote -v In origin I created a branch Further questions (Sorry -- I have not used these features before and did not find this for sure in the documentation):
Thank you! Alexander |
|
@hulpke Great - welcome to the forking club :) Trying to answer your questions, Requesting password for authentication I think you've used instructions from elsewhere and configured https access instead of ssh which you have used before. Do this: You may call Creating a branch and its lifecycle It is suggested to pick up more informative name than Creating Pull Request See this help page. Often this is even more simpler - if you've just pushed your branch to your fork, then when you will open the repo on GitHub, it will expect you creating a PR and will suggest this, and it will by default compare your branch with master branch of the main repo. How do I keep my repository updated with the changes from gap-system/gap? Please see Syncing a fork Do I need to move any changes I do that should go back to the main repository through pull requests? No - for small obviously correct changes, if you have write access to the main repository, it's fine to do them there. Pull requests are useful for things that we want:
|
|
This should be fixed by #376 and may be closed as soon as that PR will be merged and pass the tests. |
|
There are still situations when choosing a bad chiefseries makes the computations ridiculously longer. gap> tpg := ReadAsFunction("Df/testpermgroups.g")();; gap> tpg := ReadAsFunction("Df/testpermgroups.g")();; Not sure if anything could be done about this, just reporting. Have some more examples like that if needed. |
|
@hungaborhorvath |
|
Using the following test files, it is possible to compare the two methods, if anybody wants that: http://riemann.math.unideb.hu/~ghorvath/testDf.tar.bz2 I checked for groups of size up to 255. This test showed that the new method was at least 200ms and at least 10% faster for 21 groups, the old method was faster for 32 groups. However, one should probably check fo big permutation groups. There are some in the attached file in testpermgroups.g. |
|
Ok, I did some tests on big permutation groups. The new method ran out of memory sooner than the old one (computed on 4667, while the old method computed on 4670). Further, the new method was faster (by at least 200ms and by at least 10%) for 79 groups, while the old method was faster for 92 groups. The maximal difference was 12sec. |
|
If anyone is interested, I run the old and the new NormalSubgroups method for SmallGroup order different from 512, 768, 1024, 1280, 1536, 1792 (up to order 2015), and on about 8000 big permutation groups. The outputs were always the same (for the permutation groups the sizes of the normal subgroups were the same), and the computing times were about the same, as well. I considered two computing times different if the difference was at least 200ms and at least 10%. For SmallGroups the old method was faster 2104 many times, of which 154 many times by the amount 1-10 seconds. The new method was faster 2311 many times, of which 19 times by the amount 1-10 seconds and once by 17 seconds. For the big permutation groups, the old method was faster 391 many times, the new method was faster 297 many times. As for the differences, the old method was faster by 100-400 ms twice, one of the group was this: The new method was faster 4 times by at least 100 seconds, and once by 20 minutes for the following group: I am guessing that the bigger differences come from starting from a different chiefseries, but I am not sure. If anyone is interested, I can put up these test files to somewhere for download. Otherwise, if there are no more comments, I think this issue could be closed. |
For the following group, NormalSubgroups computes on my machine in about 50 seconds. However, if I compute the Center first (which is trivial for this particular group), then I only get
I Many (2097152) complements!
and do not ever get the normal subgroups. (I let it run for about half an hour, no change in the output.) I guess it is not an intended behaviour to not be able to compute something with having more information....
I came across this example when I was testing my new version of DirectFactorsOfGroup, where I check whether the center of the group is trivial or not, because if not, then one can pull back the direct factors of G/Center(G) without computing all normal subgroups. However, if this method fails, then I need to compute the normal subgroups and do a brute force search. In particular, it is useful to me to compute the center of the group.
Tested with the current master branch on debian linux. The result is the same with or without using the package CRISP.
Here is the relevant code:
gap> G := Group( (1,4)(2,3)(7,10)(8,9)(12,15)(13,14)(16,19)(17,18)(20,23)(21,22)(25,36)(26, 29)(28,31)(30,33)(32,35)(38,60)(39,48)(40,62)(41,64)(42,61)(43,63)(44, 53)(45,55)(47,51)(49,52)(50,54)(56,65)(59,66), (1,5,9)(2,10,6)(11,64,33)(12,62,31)(13,37,29)(14,35,16)(15,48,34)(17,55, 36)(18,60,25)(19,21,26)(20,53,27)(22,46,32)(23,63,30)(24,61,28)(39,42, 40)(41,43,44)(47,49,56)(50,65,58)(51,66,57)(52,59,54), (1,10)(5,6)(11,37)(12,62)(13,48)(15,60)(16,35)(17,61)(18,64)(19,26)(20, 55)(22,53)(23,63)(24,46)(25,32)(27,34)(28,33)(29,36)(38,50)(40,54)(41, 49)(42,52)(43,47)(45,51)(57,58)(65,66), (1,4,5,3,2)(6,8,9,10,7)(11,49,54, 50,53,25,39)(12,64,28,45,14,34,40)(13,17,59,57,62,35,32)(15,66,60,30,37, 16,41)(18,56,58,63,26,29,22)(19,42,20,65,55,31,46)(21,27,43,23,61,33, 38)(24,52,47,51,48,36,44), (17,18)(27,34)(41,42)(49,52)(56,59)(61,64)(65, 66), (4,6,7,5)(17,18)(27,34)(41,42)(49,52)(56,59)(61,64)(65,66) );;
gap> Center(G);
Group(())
gap> Size(NormalSubgroups(G)); time;
I Many (2097152) complements!
gap> G := Group( (1,4)(2,3)(7,10)(8,9)(12,15)(13,14)(16,19)(17,18)(20,23)(21,22)(25,36)(26, 29)(28,31)(30,33)(32,35)(38,60)(39,48)(40,62)(41,64)(42,61)(43,63)(44, 53)(45,55)(47,51)(49,52)(50,54)(56,65)(59,66), (1,5,9)(2,10,6)(11,64,33)(12,62,31)(13,37,29)(14,35,16)(15,48,34)(17,55, 36)(18,60,25)(19,21,26)(20,53,27)(22,46,32)(23,63,30)(24,61,28)(39,42, 40)(41,43,44)(47,49,56)(50,65,58)(51,66,57)(52,59,54), (1,10)(5,6)(11,37)(12,62)(13,48)(15,60)(16,35)(17,61)(18,64)(19,26)(20, 55)(22,53)(23,63)(24,46)(25,32)(27,34)(28,33)(29,36)(38,50)(40,54)(41, 49)(42,52)(43,47)(45,51)(57,58)(65,66), (1,4,5,3,2)(6,8,9,10,7)(11,49,54, 50,53,25,39)(12,64,28,45,14,34,40)(13,17,59,57,62,35,32)(15,66,60,30,37, 16,41)(18,56,58,63,26,29,22)(19,42,20,65,55,31,46)(21,27,43,23,61,33, 38)(24,52,47,51,48,36,44), (17,18)(27,34)(41,42)(49,52)(56,59)(61,64)(65, 66), (4,6,7,5)(17,18)(27,34)(41,42)(49,52)(56,59)(61,64)(65,66) );;
gap> Size(NormalSubgroups(G)); time;
35
48964
The text was updated successfully, but these errors were encountered: