> < ^ From:

^ Subject:

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]