Inconsistent behavior observed when computing over a list of orbits #5058

rfmorse · 2022-09-16T18:48:31Z

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.

gap> act := function(omega,g) return PowerModInt(omega,Int(g),3675787); end;
function( omega, g ) ... end
gap> ugrp := Units(ZmodnZ(3671136));
<group of size 1047168 with 5 generators>
gap> orbs := Orbits(ugrp,Concatenation([0..3675785],[3675786]),act);;
#I  You are calculating `Orbits' with a large set of seeds.
#I  If you gave a domain and not seeds consider `OrbitsDomain' instead.
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
#####    Quit after 10 minutes
^CError, user interrupt in
  S.orbitpos[i] := p - 1; at /Users/morse/gap-4.12.0/lib/grpperm.gi:631 called from 
Enumerator( NiceObject( G ) ) at /Users/morse/gap-4.12.0/lib/grpnice.gi:1073 called from
Enumerator( C ) at /Users/morse/gap-4.12.0/lib/coll.gi:831 called from
for elm in C do
    if func( elm ) then
        Add( res, elm );
    fi;
od; at /Users/morse/gap-4.12.0/lib/coll.gi:1395 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*:4 called from
...  at *stdin*:4
you can 'return;'
brk> quit;
### Rerun the last command in the same session
gap> stabs := List(orbs, y->Filtered(ugrp,x->PowerModInt(y[1],Int(x),3675787)=y[1]));;
gap> time;
174045

Expected behaviour

The following runs with the expected runtime the first time in the session

gap> stabs := List(orbs, y->Filtered(ugrp,x->PowerModInt(y[1],Int(x),3675787)=y[1]));;
gap> time;
174045

Copy and paste GAP banner (to tell us about your setup)

 ┌───────┐   GAP 4.12.0 of 2022-08-18
 │  GAP  │   https://www.gap-system.org
 └───────┘   Architecture: x86_64-apple-darwin21-default64-kv8
 Configuration:  gmp 6.2.1, GASMAN
 Loading the library and packages ...
 Packages:   AClib 1.3.2, Alnuth 3.2.1, AtlasRep 2.1.4, AutoDoc 2022.07.10, AutPGrp 1.11, Browse 1.8.14, 
             CaratInterface 2.3.4, CRISP 1.4.5, Cryst 4.1.25, CrystCat 1.1.10, CTblLib 1.3.4, FactInt 1.6.3, 
             FGA 1.4.0, Forms 1.2.8, GAPDoc 1.6.6, genss 1.6.7, IO 4.7.2, IRREDSOL 1.4.3, LAGUNA 3.9.5, orb 4.8.5, 
             Polenta 1.3.10, Polycyclic 2.16, PrimGrp 3.4.2, RadiRoot 2.9, recog 1.3.2, ResClasses 4.7.3, 
             SmallGrp 1.5, Sophus 1.27, SpinSym 1.5.2, TomLib 1.2.9, TransGrp 3.6.3, utils 0.76
 Try '??help' for help. See also '?copyright', '?cite' and '?authors'

The text was updated successfully, but these errors were encountered:

fingolfin · 2022-09-16T23:48:48Z

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.

rfmorse · 2022-09-17T02:26:30Z

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]));;

fingolfin · 2022-09-17T21:30:38Z

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]));;

rfmorse · 2022-09-18T00:52:05Z

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?

fingolfin · 2022-09-19T13:11:45Z

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.

rfmorse · 2022-09-21T14:18:42Z

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.

fingolfin · 2022-10-04T13:55:31Z

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.

fingolfin closed this as completed Oct 4, 2022

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Inconsistent behavior observed when computing over a list of orbits #5058

Inconsistent behavior observed when computing over a list of orbits #5058

rfmorse commented Sep 16, 2022 •

edited by fingolfin

Loading

fingolfin commented Sep 16, 2022

rfmorse commented Sep 17, 2022

fingolfin commented Sep 17, 2022

rfmorse commented Sep 18, 2022

fingolfin commented Sep 19, 2022

rfmorse commented Sep 21, 2022

fingolfin commented Oct 4, 2022

Inconsistent behavior observed when computing over a list of orbits #5058

Inconsistent behavior observed when computing over a list of orbits #5058

Comments

rfmorse commented Sep 16, 2022 • edited by fingolfin Loading

Observed behaviour

Expected behaviour

Copy and paste GAP banner (to tell us about your setup)

fingolfin commented Sep 16, 2022

rfmorse commented Sep 17, 2022

fingolfin commented Sep 17, 2022

rfmorse commented Sep 18, 2022

fingolfin commented Sep 19, 2022

rfmorse commented Sep 21, 2022

fingolfin commented Oct 4, 2022

rfmorse commented Sep 16, 2022 •

edited by fingolfin

Loading