Closed rfmorse closed 2 years ago
A quick remark: I'd suggest to replace
orbs := Orbits(ugrp,Concatenation([0..3675785],[3675786]),act);
by
orbs := OrbitsDomain(ugrp,[0..3675786],act);
as the warning message also recommends.
The message Trying regular permutation representation of group of order >10^6
is caused by GAP trying to compute a "nice monomorphisms" (this concept is explained in the GAP reference manual). You can make this explicit by invoking NiceObject(ugrp);;
.
As to the timing difference: I did not yet have a chance to look at your example here or from you email in detail. But note that many of the underlying algorithms are randomized. So you could try and use Reset
to change the initial RNG seed before running your code to see if it makes a difference.
The command
orbs := OrbitsDomain(ugrp,[0..3675786],act);
runs into the same problem as PR 5056. The bit with concatenation was to get a list that Orbits or OrbitsDomain would accept without error. (I can make another PR if you want for OrbitsDomain.)
The question is not about orbs. Rather I want to iterate over them (a list of list of integers) and apply a numerical filter to each of them. (Essentially compute the stabilizer for a representative of each orbit.) At this point I want to avoid invoking anything group theoretic because even with a nice monomorphism computing the stabilizer of an element takes a very long time. And probably rightly so no complaint .
gap> Stabilizer(ugrp,20,act);
#I default `IsGeneratorsOfMagmaWithInverses' method returns `true' for [ ZmodnZObj( 1147231, 3671136 ), ZmodnZObj( 1376677, 3671136 ), ZmodnZObj( 2719361, 3671136 ), ZmodnZObj( 1048897, 3671136 ), ZmodnZObj( 2001889, 3671136 ) ]
#I Trying regular permutation representation of group of order >10^6
<group with 2 generators>
gap> time;
1864583
Why does the following even invoke stabilizer code the first time it is run in a GAP session?
gap> stabs := List(orbs, y->Filtered(ugrp,x->PowerModInt(y[1],Int(x),3675787)=y[1]));;
#I Trying regular permutation representation of group of order >10^6
^CError, user interrupt in
transversal[orb[i] ^ treegen[j]] := treegeninv[j]; at /Users/morse/gap-4.12.0/lib/stbcrand.gi:854 called from
SCRExtend( list ) at /Users/morse/gap-4.12.0/lib/stbcrand.gi:914 called from
SCRSchTree( S, new ); at /Users/morse/gap-4.12.0/lib/stbcrand.gi:373 called from
SCRMakeStabStrong( S, new, param, orbits, where, basesize, base, correct, missing, true
); at /Users/morse/gap-4.12.0/lib/stbcrand.gi:175 called from
StabChainRandomPermGroup( ShallowCopy( GeneratorsOfGroup( G ) ), One( G ), options
) at /Users/morse/gap-4.12.0/lib/stbc.gi:136 called from
StabChainOp( G, rec(
base := base ) ) at /Users/morse/gap-4.12.0/lib/stbc.gi:33 called from
... at *stdin*:11
you can 'return;'
And the second time in the same session it is doing what I expect and apply the numerical filter to integer values of the elements of ugrp?
gap> stabs := List(orbs, y->Filtered(ugrp,x->PowerModInt(y[1],Int(x),3675787)=y[1]));;
^CError, user interrupt in
return iter!.pos >= iter!.len; at /Users/morse/gap-4.12.0/lib/list.gi:770 called from
func( elm ) at /Users/morse/gap-4.12.0/lib/coll.gi:1392 called from
FilteredOp( C, func ) at /Users/morse/gap-4.12.0/lib/coll.gi:1370 called from
Filtered( ugrp, function ( x )
return PowerModInt( y[1], Int( x ), 3675787 ) = y[1];
end ) at *stdin*:11 called from
func( C[i] ) at /Users/morse/gap-4.12.0/lib/coll.gi:663 called from
<function "List">( <arguments> )
called from read-eval loop at *stdin*:11
you can 'return;'
Lastly other variants do not change the inconsistency for instance making ugrp a list of integers exhibits the same behavior.
stabs := List(orbs, y->Filtered(List(ugrp,Int),x->PowerModInt(y[1],x,3675787)=y[1]));;
The command
orbs := OrbitsDomain(ugrp,[0..3675786],act);
runs into the same problem as PR 5056.
That's weird, it works perfectly fine for me in GAP 4.12.0, producing 359 orbits.
The bit with concatenation was to get a list that Orbits or OrbitsDomain would accept without error. (I can make another PR if you want for OrbitsDomain.)
Yes, I understand why you used that workaround; and I posted on your issue #5056, a fix for this bug is in my PR (pull request) #5057.
The question is not about orbs.
No, I merely took the liberty to also comment on another part of your example code to point out a possible improvement :-).
Rather I want to iterate over them (a list of list of integers) and apply a numerical filter to each of them. (Essentially compute the stabilizer for a representative of each orbit.) At this point I want to avoid invoking anything group theoretic because even with a nice monomorphism computing the stabilizer of an element takes a very long time. And probably rightly so no complaint .
Sure, I understand (and understood) all of that :-). But you are not actually avoiding to compute the nice monomorphism here because iterating over ugrp
currently is implemented in a way where it uses a NiceMonomorphism
...
gap> Stabilizer(ugrp,20,act); #I default `IsGeneratorsOfMagmaWithInverses' method returns `true' for [ ZmodnZObj( 1147231, 3671136 ), ZmodnZObj( 1376677, 3671136 ), ZmodnZObj( 2719361, 3671136 ), ZmodnZObj( 1048897, 3671136 ), ZmodnZObj( 2001889, 3671136 ) ] #I Trying regular permutation representation of group of order >10^6 <group with 2 generators> gap> time; 1864583
Why does the following even invoke stabilizer code the first time it is run in a GAP session?
It is computing a stabilizer chain for the image of ugrp
under the NiceMonomorphism
.
...
gap> stabs := List(orbs, y->Filtered(ugrp,x->PowerModInt(y[1],Int(x),3675787)=y[1]));; #I Trying regular permutation representation of group of order >10^6 ^CError, user interrupt in transversal[orb[i] ^ treegen[j]] := treegeninv[j]; at /Users/morse/gap-4.12.0/lib/stbcrand.gi:854 called from SCRExtend( list ) at /Users/morse/gap-4.12.0/lib/stbcrand.gi:914 called from SCRSchTree( S, new ); at /Users/morse/gap-4.12.0/lib/stbcrand.gi:373 called from SCRMakeStabStrong( S, new, param, orbits, where, basesize, base, correct, missing, true ); at /Users/morse/gap-4.12.0/lib/stbcrand.gi:175 called from StabChainRandomPermGroup( ShallowCopy( GeneratorsOfGroup( G ) ), One( G ), options ) at /Users/morse/gap-4.12.0/lib/stbc.gi:136 called from StabChainOp( G, rec( base := base ) ) at /Users/morse/gap-4.12.0/lib/stbc.gi:33 called from ... at *stdin*:11 you can 'return;'
And the second time in the same session it is doing what I expect and apply the numerical filter to integer values of the elements of ugrp?
There are many reasons why this could happen; I can't be bothered to dig into the code right now, but I already pointed out that difference in a random number generator (RNG) seed can lead to wildly varying timings. Hence my suggestion to try varying the RNG state manually via Reset
to see if it has an effect.
There is a second explanation, more likely here: Units(ZmodnZ(3671136))
is actually cached by GAP, as are its attributes. So the second time you call answer
, the same (identical) unit group is used, but this time it already comes with a bunch of precomputed data, such as its nice monomorphism and its image. This then can affect method selection: so it may end up selecting different, better methods to perform the computations.
gap> stabs := List(orbs, y->Filtered(ugrp,x->PowerModInt(y[1],Int(x),3675787)=y[1]));; ^CError, user interrupt in return iter!.pos >= iter!.len; at /Users/morse/gap-4.12.0/lib/list.gi:770 called from func( elm ) at /Users/morse/gap-4.12.0/lib/coll.gi:1392 called from FilteredOp( C, func ) at /Users/morse/gap-4.12.0/lib/coll.gi:1370 called from Filtered( ugrp, function ( x ) return PowerModInt( y[1], Int( x ), 3675787 ) = y[1]; end ) at *stdin*:11 called from func( C[i] ) at /Users/morse/gap-4.12.0/lib/coll.gi:663 called from <function "List">( <arguments> ) called from read-eval loop at *stdin*:11 you can 'return;'
Lastly other variants do not change the inconsistency for instance making ugrp a list of integers exhibits the same behavior.
stabs := List(orbs, y->Filtered(List(ugrp,Int),x->PowerModInt(y[1],x,3675787)=y[1]));;
You are still iterating over ugrp
, so yeah, no difference here. Worse, you are doing it again and again for every orbit.
You could simply avoid using ugrp
here, like this (finished in 80 seconds on my M1 mac)
n:=3671136;
ugrp_int:=Filtered([0..n], k -> GcdInt(k,n)=1);
stabs := List(orbs, y->Filtered(ugrp_int,x->PowerModInt(y[1],x,3675787)=y[1]));;
Thank you for the analysis. It all really boils down to iterating over ugrp
and everything else is irrelevant actually.
So the issue (question) is this
gap> ugrp := Units(ZmodnZ(3671136));
<group of size 1047168 with 5 generators>
gap> Elements(ugrp);;
#I Trying regular permutation representation of group of order >10^6
--- still running after two hours
However
gap> ugrp := Units(ZmodnZ(3671136));
<group of size 1047168 with 5 generators>
gap> NiceObject(ugrp);
#I Trying regular permutation representation of group of order >10^6
<permutation group of size 1047168 with 5 generators>
gap> time;
12192
gap> Elements(ugrp);;
gap> time;
0
Wouldn't one expect the first to complete in a time similar (within some small order of magnitude) to the second?
Wouldn't one expect the first to complete in a time similar (within some small order of magnitude) to the second?
Perhaps in an ideal world. But in reality, there are many ways to compute something, and which one is most efficient is generally speaking undecidable / not computable. Here it turns out it is a good idea to first compute a nice object and then go on; but in other cases this is not true.
As it is, it is fairly normal for GAP to perform quite differently depending on what information is already known about an object. The only way I know to prevent this effect is to remove the ability to select better algorithms based on prior knowledge -- but that's obviously out of the question.
Fair enough. Every command's performance is confined to it current context. And indeed this is the case above.
gap> ugrp := Units(ZmodnZ(3671136));
gap> Elements(ugrp);
Calls the Enumerator "use nice monomorphism" which computes the NiceMonomorphism and also computes the enumeration of the NiceObject, a permutation group on 1047168 points, which is basically hopeless.
On the other hand computing the NiceObject (or NiceMonomorphism) explicitly sets the group attributes Enumerator, EnumeratorSorted, AsList, and AsSSortedList (I believe via ActionHomomorphismConstructor). Hence the immediate response to Element(ugrp)
as the context has changed.
Thank you for helping me sort this out.
I believe this is resolved (not optimal, but anyway) and hence closed this. Please feel free to reopen and/or comment if you think I am mistaken and there is something left to be done.
Observed behaviour
These commands were developed in an interactive session. I got the result I was looking for and then put them in a file to run in a new GAP session. But the commands from the file ran for a vary long time (unexpected from the interactive session). So I stopped the computation and run the commands again in the same session and it completed in the time seen in the interactive session.
Expected behaviour
The following runs with the expected runtime the first time in the session
Copy and paste GAP banner (to tell us about your setup)