Hi Mike,
On 14 March 2010 02:12, Mike OS <mosul...@math.sdsu.edu> wrote:
> I had concerns that posting on gap-from and gap-support
> might make the discussion to diffused and harder to keep track of.
> I dont have experience with discussion groups. What would you
> suggest?
OK, we'll see, so far indeed it's a bit premature to announce anything
there, as it seems that your targets are still only being determined.
>
> A bit of background. I havent used gap and I'm just beginning to use
> Sage, so I am relying on two (perhaps 3) students to do the work.
> Both students are quite capable and I have a good bit of funding,
> enough for about 800 hours, so I expect we can accomplish something.
> But we need a bit of guidance.
Let me suggest first that you might like to get a first-hand experience in
using GAP. While GAP is not as sexy as Sage, after all its basic
design perhaps predates Python, for many tasks it's a tool impossible
to beat (well, perhaps only Magma, with all its shortcomings, absent
for GAP, i.e. license costs, closed-source, etc etc, comes close),
for research as well as for teaching. E.g. if I needed to teach a
course about finite groups and their characters, GAP would fit the
bill perfectly (well, the students will either need installations of
GAP on their own computers, or some other access to machines that run
GAP; the easiest would be a Unix/Linux machine, with usual user
accounts for every student, and sufficient hardware to be able to run
as many GAP sessions as there are students at the same time; so for
large classes this gets a bit problematic, but it would be also the
case with any system).
The place where Sage excels is where you need to hook up different
computer algebra systems, or perhaps get a computer algebra system
interact with some advanced numerics library.
The latter is exactly how I came to be a user and a developer of Sage,
as I need, basically, to compute Delsarte (and Schrijver) bounds on
(co)cliques of graphs (should be familiar domain to you, as a coding
theorist, I guess) that have large automorphism groups (and are often
so large that even keeping all the edges of the graph is out of the
question, for efficiency as well as just for memory considerations. So
one has to deal with representatives of orbits on them of an
automorphism group) that are very easy to work with in GAP.
Delsarte and Schrijver bounds need numerical optimisation software,
linear and semidefinite programming solvers, and GAP doesn't even have
support for floating point numbers...
So Sage comes very handy here; I call GAP from Sage to get the graph
data, and then call, from Sage, a semidefinite programming solver from
another Sage package, cvxopt.
>
> Two main questions:
> 1. Should Sage just be a conduit to gap, or should it have its own
> functionality? Robert Bradshaw, Robert Miller and William discuss
> this a bit in later posts.
I don't have a ready answer to this, and for a good reason. If one
wants to re-implement many GAP procedures, then we are talking about a
very large chunk of work, for which your 800 hours are just a tiny
drop in the ocean.
> I'm also not satisfied with my
> understanding of "wrapping" or as you say "seamlessly call
> GAP functions."
> What makes for an efficient conduit to gap?
> (My students say that now Sage just makes a string for use in gap,
> and gap objects are remade each time something is called.
The latter is not quite true. Sage interacts with a full-blown
running instance of GAP, and everything (apart from few relatively
esoteric things) that can be done within an interactive GAP session
can also be done within Sage, with overhead that comes into play
when you need to fetch data from GAP or give data to GAP (but this
overhead is far less than one would have by interacting via
reading/writing from/to a hard disk). E.g.:
sage: gap.eval('g:=PSU(4,3)')
sage: gap.eval('p3:=SylowSubgroup(g,3)')
sage: s=gap('p3')
At this point "g" and "p3" are already in GAP, you do not need to
recreate them, and s is a Sage group, which is "mathematically" a copy
of p3, that you can do something with in Sage itself. Then
if you need, say, a Sylow 5-subgroup of g, you can just do
sage: s5=gap('SylowSubgroup(g,5)')
No need to recreate g again!
> Efficient would be: Sage creates a gap object and hangs on
> to it, and Sage accesses gap functionality more directly.)
>
to give you an idea when overhead gets significant: say, assume that
Sage can operate directly on strings of bits (it should be true,
although I don't know how exactly this works), say, a binary code
represented by a "raw" bit matrix, and you have to pass these strings
to GAP: then you would have to essentially convert these strings of
bits into a format one could enter them from a GAP console, which
would be lists of characters '0' and '1'...
Most of GAP is written in its own interpreted language (plans for a
compiler were made and partially implemented, but it is now on hold
IMHO).
So you cannot use Sage/Cython capabilities to load libraries at OS
level and call functions from them, as far as this functionality of
GAP is concerned.
I read about Sage folks experimenting with "hooking into the
interpreter loop", but I don't know what they mean by this, and how
this helps to make
interaction faster.
There is also GAP functionality written in C, for efficiency, and this
part can be wrapped into an OS-level library and called from
Sage/Cython directly.
Here of course the question of how the math objects are represented in
GAP internally comes into play, so one would need to deal with highly
non-trivial data structures and issues.
> 2. How should different types of groups interact?
> Fro example: Suppose I create AbelianGroup([n_1, n_2, \dots])
> To get elementary divisors, invariant factors, or anything else I can
> think of doesnt require that I actually construct teh group. A bit of
> integer arithmetic on the list [n_1,..] is all that is needed.
> I might want to create elements of the group and do arithmetic as an
> istructional tool, but I dont see much need to call gap.
> (Robert Bradshaw talks about this in a post.)
Well, for abelian groups, this is an oversimplification. Realistically
(e.g. if you want to handle subgroups and quotient groups), you would
need to be able to work with abelian groups specified by arbitrary
finite presentations (i.e. generators and relations of general kind,
not only n_1 g_1=...=n_k g_k=0)
This would need having an implementation of Smith normal form, with
features like keeping track of the transformations occurred, etc.
GAP has such an implementation available.
Actually, GAP does not have a nice interface to additive abelian
groups, so one needs either to work with so called pcp groups
(power-commutator-presentable), at a slight overhead and writing
things multiplicatively, or to handle the integer matrices and calls
to Smith normal form routines directly.
>
> Suppose now that G is a permutation group or matrix group, or quotient
> of one, or is the unit group of a finite ring---and it happens to be
> abelian. Now I'd like to coerce it into AbelianGroups and find its
> elementary divisors, etc. So I really want a homomorphism from G
> to a finitely generated abelian group .
This is easy in GAP (although you would need to keep it
multiplicative, see above)
>
> Another example:
> Suppose I have G, a finite matrix group, or unit group of a ring,
> and I want to embed it into S_n for n as small as possible. Are
> there
> algorithms for this in gap?
It is easy to create in GAP an isomorphism into a *some* S_n, by taking
a generic enough orbit on the vectors and computing the corresponding
action of G. "As small as possible" is another question. Say, if you
want your embedding also to be transitive, this would boil down to
finding a maximal subgroup H<G so that H does not contain any
nontrivial normal subgroups
of G, and so that [G:H] is minimal.
This is highly nontrivial, and would work for small groups by means of
constructing a lattice of subgroups in GAP, but for largish groups,
say order more than few thousand, it would fail.
And if you do not require transitivity, I don't even know offhand how to
approach this.
Typically, one does some ad hoc things, like e.g. if you know that
your matrix group acts faithfully on a small set of certain subspaces,
you would construct these subspaces and the corresponding action,
etc...
(Again, this is easily doable in GAP)
> Again I want a homomorphism from G to
> a permutation group. I might also take a subgroup of a permutatin
> group in S_n and ask for it to be embedded into a smaller S_t.
To this also the discussion above applies.
There are also specific tools available in GAP for permutation groups,
i.e. computing systems of imprimitivity, computing G-invariant graphs,
etc etc.
The mail is getting a bit too long, so let me stop here--- but please
feel free to ask more.
Hope this helps, still,
Dima
>
> I posted these question in more abbreviated form Mar 11
> Cheers,
> Mike
>
> On Mar 9, 1:51 am, Dima Pasechnik <dimp...@gmail.com> wrote:
>> PS. Also, please advertise this project on gap-forum and gap-support
>> mailing lists.
>> I am sure there will be more people interested in helping out if you
>> explain that potentially one would be able to seamlessly call GAP
>> functions from
>> Python...
>>
>> Dima
>>
>> On Mar 9, 7:58 am, Mike OS <mosul...@math.sdsu.edu> wrote:
>>
>>
>>
>> > I have some funding from my university to develop materials in SAGE
>> > for use in my classes. The focus of the project is developing
>> > educational materials but we'd also like to contribute to SAGE
>> > development. I posted to sage-edu about educational issues. This
>> > post concerns development, specifically groups in SAGE and the
>> > relationship with GAP. I've hired two students, Rhea Morton and
>> > Ryan Rosenbaum to work on the project, and we would like some
>> > guidance on how we can contribute.
>>
>> > Some observations:
>>
>> > A. William started a libgap, analogous to libsing, but it has lain
>> > fallow for a while. As we understand things, there is a somewhat
>> > different challenge with GAP. Much of Singular's functionality is
>> > written in C so that SAGE can access it via Cython, whereas much of
>> > GAP is written in GAP's own language, so pexpect is required to access
>> > it. How does this affect goals forlibgap? Does this mean that
>> >libgapwill be inherently limited in efficiency or functionality?
>>
>> > B. The class Group seems to only loosely combine the different
>> > types of groups: permutation groups, abelian groups and matrix groups.
>> > For example, subgroup is not implemented for matrix groups.
>> > Also, the unit group of a ring (like U_n= Z_n*) and finitely
>> > presented
>> > groups aren't implemented (that we coud find).
>> > Should these be implemented in SAGE via GAP or have their own
>> > existence in SAGE? What are the goals for improvement of the Group
>> > functionality?
>>
>> > C. Rhea is preparing a homomorphism package that exposes GAP's group
>> > homomorphism functions. In order to work it requires SAGE groups with
>> > GAP compatible generators. It doesn't work with the Integer ring, for
>> > example, because the Integer class doesn't extend from sage.groups. In
>> > addition, it works closely with the FreeGroup class so both would have
>> > to be submitted for it to be of much utility. Rhea has tested it with
>> > the FreeGroup class, SAGE DihedralGroup, and SAGE SymmetricGroup.
>> > The documentation and test cases are still being prepared.
>>
>> > Comments?
>
--
To post to this group, send an email to sage-devel@googlegroups.com
To unsubscribe from this group, send an email to
sage-devel+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/sage-devel
URL: http://www.sagemath.org
