> < ^ Date: Thu, 06 Jul 2000 12:46:29 +0100
> < ^ From: Steve Linton <sal@dcs.st-and.ac.uk >
^ Subject: Finding source code and algorithms in GAP

Dear GAP Forum,

In a mail sent directly to us, a user asked:

I am
studying group algorithms. I want to know where in the source code of
GAP, are the basic group algorithms like finding the order of a group,
implemented. I looked into split/src4r2.zoo, but I couldnt find there.
Please help.

The answer seemed likely to be of wider interest, so I am sending it also to
the Forum.

Dear ...,

Firstly apologies for the delay in replying to your question. I am afraid the
answer is rather complicated.

You need to understand that GAP, for these purposes is in two parts: the
kernel, written in C, and the library, written in GAP. The kernel provides the
user interface and run-time system; an interpreter for the GAP language; basic
operations for the built-in data types, such as permutations or finite field
elements; and special fast C implementations for crucial parts of important
operations. All the other functionality of GAP, in particular algorithms for
structures like groups (also, semigroups, vector spaces, algebras, etc.) is
provided by the library.

Within the library, there is a structure of Operations (roughly speaking
general mathematical questions) and Methods (algorithms that can answer them).
An Operation, such as Size (which computes the order of a group amongst other
things), may have many different Methods available (Size, in fact, has 49) for
different types of input.

So, group algorithms will be found in the library of gap, in split/lib4r2.zoo,
not in the kernel source (which is split/src4r2.zoo), and what you need to
look for are the Methods for Operations like Size which are applicable to
various types of Group. Doing this directly from the source of the library is
not especially easy, however, as there are Methods for more general things
than groups that also apply to groups, and many Methods that just do a small
part of the computation and then call some other Operation to do the rest.

If you can actually run GAP, then there are some useful tools, such as
ApplicableMethod, and TraceMethods, described in the chapter "Debugging and
Profiling Facilities" of the reference manual, which can help you understand
what is happening.

You might also want to look at Akos Seress' recent article in the Notices of
the American Mathematical Society (an expanded version is available at
http://www.math.ohio-state.edu/~akos/). This surveys the principles underlying
the main algorithms in several areas of group theory, and has an extensive
bibliography.

Steve Linton


> < [top]