GAP interface: complicated objects
Nathan Dunfield
How does one create new GAP objects that require a multi-step
command? For instance, to create a finitely presented group in GAP
one does:
gap: F := FreeGroup(2)
<free group on the generators [ f1, f2 ]>
gap: G := F/[F.1*F.2*F.1^-1*F.2^-1]
<fp group of size infinity on the generators [ f1, f2 ]>
I'm trying to hack up a quick finitely presented group class, and am
trying to write the _gap_init_ method. In simple cases, _gap_init_
returns a string, but I can't come up with one that works; e.g. the
following fails
sage: gap.new("F := FreeGroup(2); F/[F.1*F.2*F.1^-1*F.2^-1]")
$sage21:=F := FreeGroup(2); F/[F.1*F.2*F.1^-1*F.2^-1];;
^
executing $sage21:=F := FreeGroup(2); F/[F.1*F.2*F.1^-1*F.2^-1];;
Now, I could have _gap_init_ return a GAP object created in several
steps, e.g.
sage: gap.eval("F := FreeGroup(2)")
'<free group on the generators [ f1, f2 ]>'
sage: G = gap.new("F/[F.1*F.2*F.1^-1*F.2^-1]");
sage: G
<fp group of size infinity on the generators [ f1, f2 ]>
but this has the disadvantage of littering the GAP interpreter with a
bunch of useless variables (or worse, over-writing something from my
interactive session).
What's the right solution here? I could assign some awful temporary
variable name in place of F, but there must be a better way...
Thanks,
Nathan
William Stein
> I'm trying to hack up a quick finitely presented group class, and am
> trying to write the _gap_init_ method. In simple cases, _gap_init_
> returns a string, but I can't come up with one that works; e.g. the
> following fails
>
> sage: gap.new("F := FreeGroup(2); F/[F.1*F.2*F.1^-1*F.2^-1]")
> $sage21:=F := FreeGroup(2); F/[F.1*F.2*F.1^-1*F.2^-1];;
> ^
>
> executing $sage21:=F := FreeGroup(2); F/[F.1*F.2*F.1^-1*F.2^-1];;
>
> Now, I could have _gap_init_ return a GAP object created in several
> steps, e.g.
>
> sage: gap.eval("F := FreeGroup(2)")
> '<free group on the generators [ f1, f2 ]>'
> sage: G = gap.new("F/[F.1*F.2*F.1^-1*F.2^-1]");
> sage: G
> <fp group of size infinity on the generators [ f1, f2 ]>
>
> but this has the disadvantage of littering the GAP interpreter with a
> bunch of useless variables
I think the only variable you introduced was F, which
you would have introduced anyways.
> (or worse, over-writing something from my interactive session).
Fortunately, SAGE can use multiple copies of interfaces to GAP.
Probably the SAGE group theory package used its
own copy of the GAP interpreter, which is different from the interactive
session GAP. This is what is done with maxima in the calculus package.
E.g.,
Set x to be 5 in maxima:
sage: maxima('x: 5')
5
sage: maxima('x + x + %pi')
%pi+10
This simplification is done using maxima (behind the scenes):
sage: x + x + pi
2*x + pi
Note that x is still x, since the maxima used by the calculus package
is different than the one in the interactive interpreter.
sage: quit
Exiting SAGE (CPU time 0m0.26s, Wall time 6m7.56s).
Exiting spawned Maxima process.
Exiting spawned Maxima process.
was@ubuntu:~$
----
Likewise, for group theory one should define the group package's
copy of GAP in some file:
from sage.interfaces.gap import Gap
gap = Gap() # the group theory gap
Then if you use that gap you won't mess up anything else.
You should also define
_gap_init_(self)
for your FP group to raise a NotImplementedError, so it isn't
unintentionally used, and you should define a method
def _gap_(self, system=gap):
...
which creates your FP group in the given copy of gap (the one
that is the system argument). If it's the local group-theory gap,
then you're in a controlled copy of the interpreter, and don't have
to worry much about variables you define (since you are carefully
not to do anything stupid). If another copy of the gap
interpreter is passed in, you should be sure to be much more
careful about variables names, e.g., call it _sage_F instead of F.
Making a new copy of the GAP interpreter is very cheap, since
the workspace is cached. You can do it about 5 times a second
in Linux:
sage: time g=Gap()('2+2')
CPU times: user 0.00 s, sys: 0.01 s, total: 0.01 s
Wall time: 0.19 <---- this is what matters
Note also that it takes not time to just make an instance of Gap
without doing a computation (since GAP isn't actually started until
a computation is done):
sage: time g=Gap()
CPU times: user 0.00 s, sys: 0.00 s, total: 0.00 s
Wall time: 0.00
William
David Joyner
of a free group. To define the generators, you have to have a
notation for the group. Why not have the _init_ method of the
class define a "(free) base group", "generators (of the free gp)",
"relations"? Something roughly (this is off the top of my head
and almost certainly wrong) like this:
class FinitelyPresentedGroup_class(group.???):
"""
???
"""
def __init__(self, n, rels, names="f"):
???
self.__relations = rels
self.__base_group = gap.new("Fgp := FreeGroup(%s)"%n)
self.__gens = gap.new("GeneratorsOfGroup(Fgp)")
def relations(self):
return self.__relations
def gens(self):
...
etc
I'm glad someone is working on this. You might want to cc Jack Schmidt
(ja...@ms.uky.edu) on your work. He is not on the sage-devel list and he may
or may not have time/interest in helping. But if he has the time, I think he
could be very helpful (and he knows GAP, group theory and programming).
On 5/28/07, Nathan Dunfield <dunf...@caltech.edu> wrote:
>
Jack Schmidt
functions. For instance:
sage: gap.new("CallFuncList(function() local F; F := FreeGroup(2);
return F/[F.1*F.2*F.1^-1*F.2^-1]; end,[])")
<fp group of size infinity on the generators [ f1, f2 ]>
I believe David Joyner has already suggested a better method for this
particular example, since one will often (especially in GAP) need the
free generators, the relators, and the generators of the fp group. I
mention it only in case you need a few truly temporary variables.
Just in case it helps:
Much of GAP's low level rewriting system and coset enumeration code
works in the free group with the relators given as a list, so you will
likely run into a need to have them. They can all be retrieved from
the FpGroup easily however if you do want to just fetch them as
needed. FreeGeneratorsOfFpGroup, RelatorsOfFpGroup,
FreeGroupOfFpGroup, and UnderlyingElement are useful.
Also beware that "presentations" are a related but different GAP
object which can handle Tietze transformations, including adding or
removing generators, that are not allowed in the FpGroup system once
the particular free group is chosen.
Nathan Dunfield
Many thanks for all the excellent suggestions. Initially, I'll use
Jack's local variable trick, though as David says a more complete
implementation would probably want to keep track of the parent free
group. There's also a clean multistep way that doesn't introduce any
variables in GAP:
sage: F = gap.new("FreeGroup(2)")
sage: G = F.FactorGroupFpGroupByRels([F.1*F.2*F.1**-1*F.2**-1])
Properly wrapping finitely presented groups would be a slightly tricky
task, and, unfortunately, this is not my current goal. There's a lot
more to a fp-group besides just the generators and relations, e.g.
information about when a group is a subgroup of another group which is
need for comparing subgroups, computing homorphisms between groups,
etc. One could, of course, just delegate most of these issue to GAP,
and that's certainly a reasonable approach to add finitely presented
groups to Sage. Unfortunately, for what I typically do (e.g. find
low-index subgroups), Magma is *much* faster than GAP, so I'm only
aiming for a finitely presented group class which allows me to create/
keep track of fp-groups at the Python level, and will just have to
drop into the Magma interpreter for most of actual computational
work.
Best,
Nathan
William Stein
> William, David, and Jack,
>
> Many thanks for all the excellent suggestions. Initially, I'll use
> Jack's local variable trick, though as David says a more complete
> implementation would probably want to keep track of the parent free
> group. There's also a clean multistep way that doesn't introduce any
> variables in GAP:
>
> sage: F = gap.new("FreeGroup(2)")
> sage: G = F.FactorGroupFpGroupByRels([F.1*F.2*F.1**-1*F.2**-1])
>
> Properly wrapping finitely presented groups would be a slightly tricky
> task, and, unfortunately, this is not my current goal. There's a lot
> more to a fp-group besides just the generators and relations, e.g.
> information about when a group is a subgroup of another group which is
> need for comparing subgroups, computing homorphisms between groups,
> etc. One could, of course, just delegate most of these issue to GAP,
> and that's certainly a reasonable approach to add finitely presented
> groups to Sage. Unfortunately, for what I typically do (e.g. find
> low-index subgroups), Magma is *much* faster than GAP, so I'm only
Do you understand why Magma is *much* faster than GAP at finding
low-index subgroups? Is it just compiled versus interpreted code, or
does MAGMA implement a much better algorithm?
William
Nathan Dunfield
> Do you understand why Magma is *much* faster than GAP at finding
> low-index subgroups? Is it just compiled versus interpreted code, or
> does MAGMA implement a much better algorithm?
William,
Both programs use the same basic coset enumeration approach to finding
low-index subgroups. I don't understand more than the fundamentals of
this procedure, so I can't really comment on what might be going on
"under the hood"; however, as one increases the index for a fixed
group the performance differential of Magma over GAP does increase,
but pretty slowly.
Let me provide some timings here, though, as well as a quick fix that
improves GAPs times by a factor of about 4, at which point it's still
an order of magnitude slower than Magma.
Here is the sample group:
gap: F := FreeGroup("a", "b");; a := F.1;; b := F.2;; G := F/
[ a^2*b^-1*a^-1*b^-1*a^2*b^4,
a*b*a^-2*b*a^2*b^-1*a*b^-1*a*b^-1*a*b^-1*a^2*b*a^-2*b*a*b ];
Task: Find all subgroups of index 10, 11, 12, and 13 respectively;
times in seconds on a 1Ghz G4 laptop:
GAP: 7.6, 30.1, 127.5, 559.4
Magma: 0.3, 1.1, 4.3, 16.4
As you can see, Magma is 25-33x faster than GAP in this example.
At least part of it is just the compiled vs. interpreted issue. In
fact, by compiling the relevant part of GAP into C-code (basically
analogous to Pyrex) --- as I'll describe below --- one can actually
speed GAP up by a factor of about 4.
GAP-compiled: 2.1, 7.3, 31.1, 132.1
Procedure for compiling a gap library module (results in much more
spead, sometimes, though sometimes not at all).
In main GAP directory:
bin/i686*/gac -d lib/grpfp.gi
cd bin/i686*
mkdir compiled
cd compiled
mkdir lib
cd lib
mkdir gi
mv ../../../../grpfp.so gi
# Test
gap -N -D (search for dynamic to make sure worked)
There is also an independent coset enumeration program, ACE, written
by a team lead by of the big experts on the subject, George Havas.
Now there is a GAP package that allows use of ACE within GAP, and
perhaps that offers better performance. I'll give it a try tomorrow
and report back.
Best,
Nathan
William Stein
> > Do you understand why Magma is *much* faster than GAP at finding
> > low-index subgroups? Is it just compiled versus interpreted code, or
> > does MAGMA implement a much better algorithm?
>
> William,
>
> Both programs use the same basic coset enumeration approach to finding
> low-index subgroups. I don't understand more than the fundamentals of
>
> There is also an independent coset enumeration program, ACE, written
> by a team lead by of the big experts on the subject, George Havas.
> Now there is a GAP package that allows use of ACE within GAP, and
> perhaps that offers better performance. I'll give it a try tomorrow
> and report back.
I've made it an optional SAGE package and posted it to the repository.
Type
sage -i ace-5.0.spkg
to install it. To test that the install worked, do
LoadPackage("ace")
from "sage -gap".
Note that ace is one of those typical math packages where there
is no copyright statement anywhere in the source tarball (as far
as I can tell) that explicitly grants any rights for redistribution, etc.
So probably this will remain an optional package.
-- William
Nathan Dunfield
> > Now there is a GAP package that allows use of ACE within GAP, and
> > perhaps that offers better performance. I'll give it a try tomorrow
> > and report back.
>
> I've made it an optional SAGE package and posted it to the repository.
William,
Thanks for packaging ACE. It turns out that while ACE can replace
much of the coset enumeration code in GAP, the LowIndexSubgroups
routine is separate and appears to be pure GAP code. So this doesn't
help with the speed issue.
Best,
Nathan