Method selection for FrattiniSubgroup #710
Comments
No. This is exactly how method selection is intended to work.
If you think it is worth doing so.
Yes, the method using the radical (which utilizes maximal subgroup functionality that was not available when the other method was installed) supersedes an older method fully. Again this is how method selection works -- a newer method overrides the older one. Once could remove the older one, but with very little gain.
This depends on what input you assume. A failing solvability test might be expensive for zero gain. Vice versa PcGroups immediately know that they are solvable, and thus anyhow go in the right route.
What you're observing is a side-effect of using finitely presented groups. For a long time none of the standard functions were available for these groups, and the fact that now much of it works has long been underappreciated. |
|
@hulpke Does the radical method and the generic method work for infinite groups, as well? If not, can we at least add an IsFinite filter, so that for arbitrary groups the redispatches will be called first? |
The generic method and the method using radicals both benefit from checking solvability, and then redispatching (if solvability was not known before, thus preventing an endless loop). The point is that for the former, we are generic anyway, anything may be either trivial to compute or impossible, so we might as well check for solvability, which shouldn't be harder than computing all maximal subgroups (plus, the latter is impossible for huge elementary abelian groups, while the former is trivial). The method using radicals automatically computes whether the group is solvable anyway, so it may just as well use this and redispatch in that case. Resolves gap-system#710
The generic method and the method using radicals both benefit from checking solvability, and then redispatching (if solvability was not known before, thus preventing an endless loop). The point is that for the former, we are generic anyway, anything may be either trivial to compute or impossible, so we might as well check for solvability, which shouldn't be harder than computing all maximal subgroups (plus, the latter is impossible for huge elementary abelian groups, while the former is trivial). The method using radicals automatically computes whether the group is solvable anyway, so it may just as well use this and redispatch in that case. Resolves gap-system#710
|
Looking at this issue, I have a hard time filtering out what actionable items there are left, if any. @hungaborhorvath suggested that abelian / solvable methods should come before pcp / pcgs methods. I disagree: pcgs / pcp implies that one can actually effectively compute in a group. Whereas a group may be abelian but almost untractable for computational purposes (e.g. it may have a complicated fp presentation, be infinite, etc.) The problem with the radical method being ranked equally to the "generic" method is gone, the current ranking is this:
This leaves the two concrete examples, were testing for solvability (or being abelian, nilpotent) may help tremendously. Here it might help if something like the following was added to the generic method (alternatively, if suitable redispatch rules were used, perhaps): if not HasIsSolvableGroup(G) and IsSolvableGroup(G) then
return FrattiniSubgroup(G);
fi;For the second problem: While it is true that a solvability check could hurt more than it helps, it is also true that the radical method computes the radical -- and at that point, can of course trivial decide if the groups is solvable. So inserting a similar check should be fine... I'll prepare a pull request, then perhaps @hulpke can comment on it, and we can decide if it is worth it, or whether there are possibly case that might suffer from this "improvement". |
The generic method and the method using radicals both benefit from checking solvability, and then redispatching (if solvability was not known before, thus preventing an endless loop). The point is that for the former, we are generic anyway, anything may be either trivial to compute or impossible, so we might as well check for solvability, which shouldn't be harder than computing all maximal subgroups (plus, the latter is impossible for huge elementary abelian groups, while the former is trivial). The method using radicals automatically computes whether the group is solvable anyway, so it may just as well use this and redispatch in that case. Resolves #710
The generic method and the method using radicals both benefit from checking solvability, and then redispatching (if solvability was not known before, thus preventing an endless loop). The point is that for the former, we are generic anyway, anything may be either trivial to compute or impossible, so we might as well check for solvability, which shouldn't be harder than computing all maximal subgroups (plus, the latter is impossible for huge elementary abelian groups, while the former is trivial). The method using radicals automatically computes whether the group is solvable anyway, so it may just as well use this and redispatch in that case. Resolves gap-system#710
As far as I can see, there are 9 different methods handling
FrattiniSubgroupcomputations:handled by nice monomorphism, rank 370, grpnice.gi:529
method for trivial groups, rank 71, grp.gi:1024
for permgrp, rank 58, grpperm.gi:1598
pcgs computable groups using prefrattini and core, rank 52, grppcatr.gi:136
for pcp groups, rank 50, pkg/polycyclic-2.11/gap/pcpgrp/general.gi:142
for abelian groups, rank 43, grp.gi:1030
for nilpotent groups, rank 41, grp.gi:1048
Using radical, rank 35, maxsub.gi:335
generic method for groups, rank 35, grp.gi:1060
Some of these are superfluous, e.g. the "for permgrp" method checks if the groups is a p-group and then uses the same method that is used for nilpotent groups. If the group is not a p-group, then it exits by
TryNextMethod. This circumvents method selection.Further, the "generic method" has the same rank as the "radical" method (both filter for
IsGroup), thus the generic method will never ever be called on any group. This could/should be cleaned up.Second, I do not think that the pcgs or pcp methods should be before the abelian (or even the nilpotent) methods. Maybe abelian and nilpotent methods should receive a rank increase by an IsFinite rank?
For the pcp, pcgs, radical methods I cannot really decide what they do and how fast they compute the Frattini subgroup, but some of them fail to compute for particular groups, sometimes even if they are finite (!), e.g.
I cannot decide if the "radical" method (or the "generic" method for that matter) can possibly be used for arbitrary groups (as they are called now), or only for finite (or only for finite with particular presentation). Nevertheless, if they error out on finite groups, then something should be done.
Another example (artificial as it may be) is
while
is much faster. I believe this would warrant a check for solvability (and possibly for finiteness) before applying the radical method.
BTW, for this group an
IsNilpotentcheck takes 104 ms, and then the nilpotent method computes the Frattini subgroup in 336ms. About twice faster than the pcgs method. Thus maybe a nilpotency check is warranted, however that may not give that much of an increase over the pcgs method.I am happy to submit a PR trying to clean this up a bit, but first I would like to have an idea about the general consensus on what people think should be done and how.
Similar issues could be had for
NormalSubgroups, as well, and probably for a lot of other functions. (E.g. there CRISP circumvents the usual method selection in residual.gi:96 by checking for solvability and finiteness.)The text was updated successfully, but these errors were encountered: