Home page

Coset Enumeration

The ACE/PACE/PEACE -- aka (P(E))ACE -- suite of programmes is intended to fulfil the need for modern, robust software based on the Todd-Coxeter coset enumeration procedure.  ACE is a complete rewrite of the premier coset enumerator TC/(A)CE by Havas, a programme with a 30 year pedigree.  PACE & PEACE are developments of ACE which allow parallel enumeration & proof extraction, respectively.  (P(E))ACE is written in ANSI C, and has been successfully used on a variety of systems.  (PE)ACE has also been compiled for Windows, as console (ie, DOS) utilities.

ACE - Advanced Coset Enumerator

ACE is a fully-featured stand-alone coset enumerator.  It is fast, can handle very large tables, and is written to facilitate further development & incorporation into other products.  The current `official' release of ACE is ACE 3.000.  ACE 3.001 will be essentially a `tidied-up' version of ACE 3.000, incorporating some user feedback.  It will be fully compatible with ACE 3.000.  It is currently under active development, and should be completed real soon now.  (The "Changes" file in the distribution details the changes between version.) The manual for ACE 3.001 also covers ACE 3.000.  This manual is incomplete, being work in progress, but should help get you started.  The manual might also be helpful to users of P(E)ACE, since their coset enumerators were derived from ACE's.

ACE 3.000 distribution (27 Feb 99) .....   [112K .tar.gz file]
ACE 3.001 distribution (29 Mar 01) .....   [104K .tar.gz file]
ACE 3.001 manual (29 Mar 01) .....   [140K .ps.gz file]

PACE - Parallel ACE

PACE is a parallelised version of ACE, using POSIX threads in an SMP environment.  It has lots (but not all) of ACE's features, and can (caveats apply) speed things up significantly.  It is intended for specialists, who need to do large enumerations fast(er).  It could also be used as a (reasonably) clean starting point for people wishing to investigate deduction handling (the most time-consuming part of an enumeration), or gap-filling strategies.

PACE 1.000 distribution (26 Oct 00) .....   [92K .tar.gz file]
PACE 1.000 manual (16 Feb 01) .....   [161K .ps.gz file]   or   [78K .dvi.gz file]

PEACE - Proof Extraction After Coset Enumerator

Implicit in a coset enumeration is a sequence of coset definitions which is sufficient (along with the presentation) to recreate the coset table.  For any word in the subgroup, the working involved in (re)creating a coset table implicitly contains a proof of subgroup membership.  PEACE is a stand-alone utility for generating & manipulating definition sequences and generating proofs & proof certificates.  Verify is a stand-alone C programme for verifying proof certificates.  PEACE is currently under active development.  Not all intended features are present as yet, but the software is usable.

PEACE 1.000 distribution (10 Oct 00) .....   [83K .tar.gz file]
PEACE 1.000 manual (9 Oct 00) .....   [76K .ps.gz file]   or   [37K .dvi.gz file]
Verify utility + some example certificates (10 Oct 00) .....   [12K .tar.gz file]

Preprints

Experiments in coset enumeration (ACE) .....   [70K .ps.gz file]
Proving a group trivial made easy: a case study in coset enumeration (ACE) .....   [45K .ps.gz file]   or   [22K .dvi.gz file]
Parallel coset enumeration using threads (PACE) .....   [35K .ps.gz file]   or   [17K .dvi.gz file]