1
$\begingroup$

How can i check which Algorithm is used by GAP for its working. Like

gap> p_1:=(1, 2, 4, 5);;
gap> p_2:=(1, 2, 3);;
gap> g_1:=Group(p_1, p_2);;
gap> p_3:=(1, 2, 4, 3);;
gap> p_4:=(1, 2, 5, 4, 3);;
gap> g_2:=Group(p_3, p_4);;
gap> g_1 = g_2;
true

Which Algorithm is used by GAP for its working? Can i check in terminal the name of Algorithm used by GAP for its functioning, may be in docs specified?

Thanks you very much for you help. :)

$\endgroup$
  • $\begingroup$ Hint: indent code by 4 spaces to be displayed nicely $\endgroup$ – Alexander Konovalov Dec 11 '15 at 14:57
3
$\begingroup$

I've answered this in finding code of a function in GAP packages - please read it and also explore links that it contains.

However, this particular case seems interesting and not obvious because of the equality operation which one should input as \=, so I will show an example here too:

Get applicable method:

gap> f:=ApplicableMethod(\=,[g_1,g_2]);
function( G, H ) ... end

Now see its location in the code:

gap> FilenameFunc(f);
".../gap4r7p9/lib/grp.gi"
gap> StartlineFunc(f);
2757

or view it in the GAP session:

gap> PageSource(f);
Showing source in .../gap4r7p9/lib/grp.gi (from line 2752)
#M  \=( <G>, <H> )  . . . . . . . . . . . . . .  test if two groups are equal
##
InstallMethod( \=,
    "generic method for two groups",
    IsIdenticalObj, [ IsGroup, IsGroup ],
    function ( G, H )
    if IsFinite( G )  then
      if IsFinite( H )  then
        return GeneratorsOfGroup( G ) = GeneratorsOfGroup( H )
               or IsEqualSet( GeneratorsOfGroup( G ), GeneratorsOfGroup( H ) )
               or (Size( G ) = Size( H )
                and ((Size(G)>1 and ForAll(GeneratorsOfGroup(G),gen->gen in H))
                  or (Size(G)=1 and One(G) in H)) );
      else
        return false;
      fi;
    elif IsFinite( H )  then
      return false;
    else
      return GeneratorsOfGroup( G ) = GeneratorsOfGroup( H )
             or IsEqualSet( GeneratorsOfGroup( G ), GeneratorsOfGroup( H ) )
             or (    ForAll( GeneratorsOfGroup( G ), gen -> gen in H )
                 and ForAll( GeneratorsOfGroup( H ), gen -> gen in G ));
    fi;
    end );

As you may see, in the most general case it will check that each generator of one group belongs to the other group and vice versa, but before reaching that there are also certain optimisation and obvious cases requiring less or no actual computation.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks, the answer really helped, it make my job a lot easier :) $\endgroup$ – gxyd Dec 11 '15 at 16:01
  • $\begingroup$ BTW doesn't GAP use the fact that since the computation involves checking equality of two Permutation Groups. Wouldn't using some Permutation Groups specific algorithm be better compared to some algorithm which checks for generalised groups? $\endgroup$ – gxyd Dec 12 '15 at 5:20
  • $\begingroup$ @gxyd If such algorithm exists, then yes. Otherwise, permutation group specifics chimes in later. Without checking, I'd expect that IsFinite, Size and membership test (in) are all using very efficient specific methods for permutation groups. $\endgroup$ – Alexander Konovalov Dec 12 '15 at 12:12
  • $\begingroup$ P.S. for example, GAP would not check if an element is in the group by checking whether it is contained in the list of it elements, or check that two permutation groups by calculating and comparing the sets of their elements - that would work for small examples only. $\endgroup$ – Alexander Konovalov Dec 13 '15 at 16:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.