GAP: STATUS REPORT AND SOME POSSIBLE DIRECTIONS

Steve Linton

Division of Computer Science, St. Andrews July 7, 1997

GAP

Overview

1. Status report – GAP 3.4.4, handover, GAP 4 releases

2. Quick overview of GAP 4

3. Some thoughts on longer term directions

STATUS REPORT

GAP  Status Report

GAP 3.4.4

• Released April from St Andrews, Last full release of GAP3 (probably) – Bug fixes

– Better Tietze routines

– Better matrix group handling over small fields

– Some improvements in algorithms (interfaces unchanged)

– HTML manual (now 1600 pages)

– New data libraries: groups order < 1000, transitive groups degree < 24 – New share packages: autag, Chevie, CrystGAP, glissando, grim, kbmag,

matrix, pcqa, specht, xmod

– Updated share packages: grape, guava, anupq

Transfer to St Andrews

• St Andrews role has been increasing – 3.4.4, Web site, AH, WN and SL (occasionally) work on GAP4

• Formal handover (and transfer of e-mail addresses) in the next weeks

• System guaranteed to remain free and open

• Secured some funding for people to work on GAP (2 jobs advertised)

• A move from an Aachen-based project with international involvement to an international project coordinated at St Andrews

IE: we hope to persuade you, and others world-wide, to do a lot of the work. We are trying to set up ways to help, and to acknowledge the effort involved.

Steve Linton  4

• The GAP Council is established to encourage GAP development, and keep us in touch with GAP users world-wide.

GAP 4

• Developed in Aachen (mostly) over the last two-three years

• Many new features – system and mathematical

• Alpha test releases (weekly snapshots of our development version) available now

• Beta test release (with some documentation) in next few weeks

• Full release early to mid 1998

OVERVIEW OF GAP 4

GAP  Overview of GAP 4

What’s Not Changed

• For interactive use, or simple programming, GAP 4 looks a lot like GAP 3 • Some commands have changed name

• Some things will be done much more efficiently

The GAP 4 Kernel

• Rebuilt from the ground up – Martin Schönert, Frank Celler

• More efficient memory manager

• Easier to extend

• 64 bit clean

• Faster function calling

• Save/load workspace

• Fast vector arithmetic over finite fields

• Streams – More sophisticated file handling

– More flexible communication with other processes

Steve Linton  9

The GAP Compiler

• Ferenc Rakoczi, MS, FC

• Compiles GAP to human-readable C

• C can be compiled and loaded dynamically (UNIX only) or compiled into a kernel

• Compiled code automatically loaded when it exists

• Possible to further optimize the C by hand (care)

The GAP 4 Library

• Much extended – Aachen team, including Thomas Breuer, Bettina Eick, Alexander Hulpke, Heiko Theißen

• Some new features:

– p-adic numbers

– Infrastructure for semigroups and monoids

– Much better handling of vector spaces, bases, and algebras

– Multivariate polynomials and rational functions (basic operations)

– GF (p) : p > 2^{1}6

– Groups given by confluent rewriting systems

– Smash meat-axe in the library

New Library Features Continued

– New polycyclic group code, handles infinite pc groups, based on Deep Thought – Werner Nickel, Wolfgang Merkwitz

– Much improved permutation group code – HT, Akos Seress, AH

– Lie Algebras – Willem de Graaf

– Better handling of morphisms

– Hash tables

Immutability

• Problem in GAP 3 – Sets are stored as sorted lists

– A list of lists or records, cannot be guaranteed to remain sorted.

– Algorithms for such sets are painfully slow.

• In GAP 4:

– Lists and records can be made immutable – changing them is forbidden – Objects (later) may claim to be immutable – promises that they will not

change their behaviour under = or <

– Sets of such things stay sorted

– Much less copying

Enumerators

• An enumerator is a virtual list

• It behaves like a list, but may be stored differently inside

• For example:

– elements of a finite vector space

– elements of a permutation group

– a sparse list

• Use wherever you would use a list

Iterators

• An iterator provides a way to run through a set

• May not need to list the set in full, or even enumerate it

• Set may be infinite

• Used in for loops

• Any object may supply an iterator, can then use it

                     for g in G do

GAP 4 Library Structure

• New scheme replaces operations records

• Most functions a user calls become Operations

• An Operation is a place-holder for a whole lot of different functions – it’s Methods

• All Methods for an Operation compute the same thing, but may work for different sets of inputs

• The system will call the “best” Method applicable to the inputs (method selection)

• Method selection can depend on “types” of inputs, on their relationships and on facts learned about them since they were created

• Easy to add new methods that work in specific circumstances

Steve Linton  16

GAP  Overview of GAP 4

• Fairly easy to add new types of objects, new Operations, etc.

• Should be ideal for implementation of black box groups etc

Objects and Types

• In GAP 3, most things are represented by records – the methods applicable to them are in the operations subrecord

• In GAP 4, most things are represented by Objects

• An Object stores some data (either like a list or like a record) and has a type • The type is partially fixed when the object is created, partially it reflects things learnt since

• The types of the arguments determine the applicable methods

• List and record access are Operations, so an Object can pretend to be a list or a record (or both)

DIRECTIONS

GAP  Directions

Ground Rules

• Main aim of GAP is to help people do research, teach and learn

• Main focus is discrete mathematics especially algebra

• Must aim for a more distributed development effort

Some Things I think Will be Important/Useful/Interesting

• Algebraic broadening – algebra, semigroups, quantum groups, combinatorics

• Links to other systems – trade capabilities, expand role as the universal front-end

• Library modularity – rethink the library/share package division

• Integrate support for parallel/distributed processing

• Split off the user interface – different UIs for different jobs

Databases and Computation with Known Groups

• A favourite hobby-horse of mine – “Art and Science”

• “Computing for the post-classification world”

• System and packages contain a lot of databases

• New algorithms often depend on database type information

• Much information about known groups is not used

• For example, computing centralizers is much easier if you know the centralizer order

Computing with Known Groups – Issues 1

• How to store and organise the information – what to store, what to compute

– how to avoid redundancy and error

– how to establish provenance of data

– groups vs generated groups

– big variations – some databases have many small groups, others a few huge ones

Computing with Known Groups – Issues 2

• How to connect a concrete group with a database group – Constructive recognition, essentially

– What is the user promises that the groups are isomorphic – still have to

get standard generators, match up conjugacy classes, etc

• How to use database info in all our algorithms – How much of the “art” can be made into “science”