MPI based Andrews-Curtis move enumerator
C++ C
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Failed to load latest commit information.

Akbulut-Kirby Kirby Diagram


Andrews-Curtis is an MPI based Andrews-Curtis move enumerator that examines potential counterexamples to the Andrews-Curtis Conjecture.

Specifically, given P, a balanced presentation of a group that is a potential counterexample to the Andrews-Curtis Conjecture, the Andrews-Curtis executable attempts to prove the potential counterexample P is or is not an actual counterexample.

The balanced presentation P is fed to the Andrews-Curtis executable as a number of generators a,b... along with an equal number of relators r,s... Given these the Andrews-Curtis executable, using only Andrews-Curtis moves, attempts to prove P is trivial.

If it successfully proves P is trivial, it prints out the proof including all Andrews-Curtis moves. If it can not prove P is trivial, it simply prints P, the original balanced presentation, indicating it is a counterexample to the Andrews-Curtis Conjecture.

Quick Start

Checking Dependencies

Andrews-Curtis has the following dependencies:

Building Executable

Once the dependencies are installed and the environment is set up to allow their access, one can compile Andrews-Curtis by opening a terminal and entering the following commands:

localhost:~ kdavis$ cd <Andrews-Curtis Root Directory>
localhost:Andrews-Curtis kdavis$ make ac

This compiles the Andrews-Curtis executable ac and places it into the Andrews-Curtis root directory.

Running the Executable

As the Andrews-Curtis executable is MPI based, it is started like any other MPI executable

localhost:Andrews-Curtis kdavis$ mpirun ./ac ab aB b

Specifically, the above example is for P a balanced presentation with generators a and b and relators aB and b. (When using ac, the inverse of a relator, b for example, is indicated by using uppercase, in our example B.)

Executing the above example on a single node will result in the following proof:

localhost:Andrews-Curtis kdavis$ mpirun ./ac ab aB b
Process: 0 Thread pool size: 4
Process: 1 Thread pool size: 4

Completed level: 0
    Uptime: 0ms
    Relators: 2
    Balanced_presentations: 1
    Average Relator Length: 1.5
    Average Balanced presentation Length: 3

(aB, b)
(a, b)

As ac is MPI based, running it on a cluser of nodes is simple. One need only use the standard procedure for your MPI implementation.

Contribution guidelines

If you are interesting in contributing, open an issue, code it up, and make a pull request.

Contributor list

Kelly Davis

Credits, Inspiration, and Alternatives

An alternative Andrews-Curtis move enumerator, and motivation for this enumerator, is ACME.