On May 31, 3:10 pm, "William Stein" <[EMAIL PROTECTED]> wrote:
> 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
--~--~---------~--~----~------------~-------~--~----~
To post to this group, send email to sage-devel@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/sage-devel
URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/
-~----------~----~----~----~------~----~------~--~---
