{"action":"created","issue":{"url":"https://api.github.com/repos/gap-system/gap/issues/379","labels_url":"https://api.github.com/repos/gap-system/gap/issues/379/labels{/name}","comments_url":"https://api.github.com/repos/gap-system/gap/issues/379/comments","events_url":"https://api.github.com/repos/gap-system/gap/issues/379/events","html_url":"https://github.com/gap-system/gap/pull/379","id":119371863,"number":379,"title":"Enhance DirectFactorsOfGroup for faster StructureDescription","user":{"login":"hungaborhorvath","id":11720671,"avatar_url":"https://avatars.githubusercontent.com/u/11720671?v=3","gravatar_id":"","url":"https://api.github.com/users/hungaborhorvath","html_url":"https://github.com/hungaborhorvath","followers_url":"https://api.github.com/users/hungaborhorvath/followers","following_url":"https://api.github.com/users/hungaborhorvath/following{/other_user}","gists_url":"https://api.github.com/users/hungaborhorvath/gists{/gist_id}","starred_url":"https://api.github.com/users/hungaborhorvath/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/hungaborhorvath/subscriptions","organizations_url":"https://api.github.com/users/hungaborhorvath/orgs","repos_url":"https://api.github.com/users/hungaborhorvath/repos","events_url":"https://api.github.com/users/hungaborhorvath/events{/privacy}","received_events_url":"https://api.github.com/users/hungaborhorvath/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":0,"created_at":"2015-11-29T17:32:37Z","updated_at":"2015-12-01T10:01:42Z","closed_at":null,"pull_request":{"url":"https://api.github.com/repos/gap-system/gap/pulls/379","html_url":"https://github.com/gap-system/gap/pull/379","diff_url":"https://github.com/gap-system/gap/pull/379.diff","patch_url":"https://github.com/gap-system/gap/pull/379.patch"},"body":"The default DirectFactorsOfGroup attribute has undergone a serious\r\nenhancement, without having proper documentation, yet.\r\n\r\n- The Kayal-Nezhmetdinov algorithm is implemented with some tweaks under the\r\n  attribute DirectFactorsOfGroupKN. From now on, it is referred to as the\r\n  KN method.\r\n  Some parts of the code is reused in the main DirectFactorsOfGroup\r\n  attribute, but there are no direct calls to DirectFactorsOfGroupKN.\r\n- The KN method has an algorithm for computing a direct complement to a\r\n  normal subgroup. This is implemented in the operation\r\n  ComplementNormalSubgroup. This particular operation (in theory) should\r\n  work for infinite groups, as well.\r\n- The main DirectFactorsOfGroup algorithm works as follows:\r\n  - for Abelian groups computes the decomposition to cyclic groups of\r\n    prime-power order,\r\n    (for infinite Abelian groups the output is only a list of the direct\r\n    factors instead of a set, because calling Set on the factors might\r\n    not finish running in reasonable time;\r\n    infinite non-Abelian groups are not handled, at all)\r\n  - for nilpotent groups it calls itself on the Sylow subgroups,\r\n  - checks several sufficient conditions for the group being direct\r\n    indecomposable,\r\n  - looks for Abelian cyclic components from the center of the group,\r\n  - checks for more sufficient conditions for the group being direct\r\n    indecomposable,\r\n  - computes the normal subgroups and the minimal normal subgroups, and\r\n    calls DirectFactorsOfGroupFromList.\r\n- DirectFactorsOfGroupFromList is a more efficient version of the old\r\n  factorization method. It essentially searches through the normal subgroups\r\n  (2nd argument, which is a list) by size and looks for a complement from\r\n  the same list. If it finds a complement then the first factor is direct\r\n  indecomposable, the second is decomposed further using the same list\r\n  filtered from the clearly noncomplemented normal subgroups.\r\n  Trivial intersection is checked by IsTrivialNormalIntersectionInList,\r\n  which checks if any of the minimal subgroups (3rd argument, which is a\r\n  list) is contained in both normal subgroups. This is faster than computing\r\n  the normal intersection and checking if that is trivial.\r\n- IsTrivialNormalIntersection is implemented in cases where one knows more\r\n  about the structure of the group.\r\n- Cases where the group is already a direct product or already has\r\n  NormalSubgroups computed are handled in separate methods.\r\n- Some lines contained a space at their end, these spaces are all removed\r\n  automatically by the text editor.\r\n\r\nTested on SmallGroups of order different than 512, 768, 1024, 1280, 1536,\r\n1792, and on a couple hundred test permutation groups.\r\n\r\nMore times than not the new method was significantly (>200ms, >10%) faster\r\nthan the old method, in many cases because it immediately found the group\r\nis direct indecomposable, rather than spending much time computing the\r\nnormal subgroups. In particular, the groups specifically mentioned in \r\nissue #160 are factored almost instantly now. \r\n\r\nThe KN method seems to be drastically slower if the direct factors are\r\nnon-Abelian. Computing normal subgrups in such cases is much faster.\r\nHowever, the implementation is kept for possible future enhancements."},"comment":{"url":"https://api.github.com/repos/gap-system/gap/issues/comments/160920040","html_url":"https://github.com/gap-system/gap/pull/379#issuecomment-160920040","issue_url":"https://api.github.com/repos/gap-system/gap/issues/379","id":160920040,"user":{"login":"fingolfin","id":241512,"avatar_url":"https://avatars.githubusercontent.com/u/241512?v=3","gravatar_id":"","url":"https://api.github.com/users/fingolfin","html_url":"https://github.com/fingolfin","followers_url":"https://api.github.com/users/fingolfin/followers","following_url":"https://api.github.com/users/fingolfin/following{/other_user}","gists_url":"https://api.github.com/users/fingolfin/gists{/gist_id}","starred_url":"https://api.github.com/users/fingolfin/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/fingolfin/subscriptions","organizations_url":"https://api.github.com/users/fingolfin/orgs","repos_url":"https://api.github.com/users/fingolfin/repos","events_url":"https://api.github.com/users/fingolfin/events{/privacy}","received_events_url":"https://api.github.com/users/fingolfin/received_events","type":"User","site_admin":false},"created_at":"2015-12-01T10:01:42Z","updated_at":"2015-12-01T10:01:42Z","body":"Thanks for your submission, appreciated. I'll add comments to your code changes next, as part of reviewing this PR.\r\n\r\nOne immediate comment: You mention tests you performed. It would be good if you could add some tests to this PR, too. \r\n\r\nI am also somewhat concerned about the method being drastically slower in certain cases. Can you provide a few concrete examples were things get noticably slower / faster?"}}