[Colloq] **Thesis Defense Talk** Tuesday, June 4 10:30am

[Rachel Bates]

College of Computer Science
PhD Thesis Defense

presents:
Victor Grinberg
will speak on:
ADVANCED STRATEGIES FOR COSET ENUMERATION

Tuesday, June 4, 2002
10:30am
149 Cullinane Hall


Abstract

Coset enumeration is a method for converting a presentation of a
mathematical group to a permutation representation.  This allows one, given
a set of equations that describe some symmetries or invertible
transformations, to reconstruct the permutation representation of the group
of all transformations.  It may also be viewed as a special case of the
subset construction in finite state automata (FSA).  The subset construction
identifies certain states of the FSA (cosets) with each other, and then
propagates this identification by following links from two identified
cosets, such that the link from each identified coset has the same label.
Several researchers have worked on parallel coset enumeration strategies
using shared memory.  This is important not only for speed, but also because
the large memory requirements of coset enumeration often make memory the
dominant cost.  This cost can be reduced by using many CPUs to reduce the
time during which this memory must be “rented”.  The existing parallel coset
enumerators don’t scale as with the number of processors increases.
In this thesis we concern ourselves with methods for efficient coset
enumeration that would allow one to solve large coset enumeration problems
more quickly.  We propose new heuristics for parallel coset enumeration that
allow for better scalability than has ever been achieved.  Some of our
heuristics are also useful in a sequential setting.  The methods were
successful for many groups, with our largest example being an enumeration of
the Lyons’s group, resulting in a permutation representation on some 8.87
million points.  Lyons’s group is one of the largest enumerations carried
out in the literature to date.

Advisor: Gene Cooperman