Tracks

solve and search

The two programmes, solve and search, are available as a source distribution using the following link:

decomp-30-8-09.tar

Once you have downloaded and extracted the above file go into the decomp-30-8-09 directory it creates and type 'make solve' (but without the quotes) to build the solve programme, followed by 'make search' to build the search programme. You may then wish to type 'make clean' to remove the object files the compilation produces.

The Makefile is based on the gcc compiler and is not sophisicated, I can't guarantee it will work on every system, so you'll need to ask a local system expert for help if it doesn't work properly.

Here is a sample session that builds both programmes, you should see something like this if all goes well:

[bart@wormwood decomp-30-8-09]$ make solve
g++ -Wall -I ./include -I /include -I  -g -c src/solve.cpp -o solve.o 
g++ -Wall -I ./include -I /include -I  -g -c src/solvefns.cpp -o solvefns.o 
g++ -Wall -I ./include -I /include -I  -g -c src/util.cpp -o util.o 
g++ -o solve solve.o solvefns.o util.o -lstdc++
[bart@wormwood decomp-30-8-09]$ make search
g++ -Wall -I ./include -I /include -I  -g -c src/search.cpp -o search.o 
g++ -Wall -I ./include -I /include -I  -g -c src/decompose.cpp -o decompose.o 
g++ -Wall -I ./include -I /include -I  -g -c src/searchfns.cpp -o searchfns.o 
g++ -o search search.o decompose.o searchfns.o util.o -lstdc++
[bart@wormwood decomp-30-8-09]$ make clean
rm -f *.o
[bart@wormwood decomp-30-8-09]$ ls
cube  free    include  Makefile  pretzel  search  src    trefoil  trivial
fig8  higman  M21      manif     README   solve   torus  trg
[bart@wormwood decomp-30-8-09]$

You will end up with two programmes, solve and search; also shown in the directory listing is a collection of input files for the solve programme. If you are interested in the source code, it is all in the src and include directories.

Running the programmes

You need to run solve before you run search. The solve programme calculates a set of extreme fundamental tracks for a group presentation, the programme search then analyses those tracks and allows you to perform a number of computations with them, including obtaining decompositions of the group. In both cases using the -h option displays the help information contained in the following two sections.

The solve programme

Usage: solve [-g]|[-h] [infile]

This programme may be run by typing 'solve' at the command line or by specifying a parameter file 'infile' by typing 'solve infile'. A parameter file must contain the following information, on separate lines as shown. 

jobname
number of generators
number of relators
generator 1 generator 2 ...
relator1 relator2 ...

The relators must not contain any spaces but may be separated by an arbitrary number of spaces, or a newline.

Here is an example of the input file for the group presentation 

<  a  b  c  d : -aba-b-b -bcb-c-c -cdc-d-d -dad-a-a >

higman
4
4
a b c d
-aba-b-b -bcb-c-c -cdc-d-d -dad-a-a

Represent inverses of generators by preceeding the character with '-' eg -a, and powers by repetition

We also require that:

  1. relators indicating a generator of finite order should be entered in the positive, eg 'aa', not '-a-a';
  2. 2-torsion generators are entered first and always written in the positive;
  3. the relators have length > 3 or take one of the forms 'aa' or 'aaa';
  4. the total, absolute, exponent of each generator is at least two;
  5. 2-torsion relators are entered first, in the order corresponding to the 2-torsion generators.

Requirements 1 to 5 are ESSENTIAL for the running of the program.

The '-g' switch causes the original Greenberg algorithm to be used, this creates LOTS more tracks but could be quicker in some instances - no promises though.

The solve programme produces an .eft file that is used by the search programme, and a .out file that contains essentiall the same information but in a more readable form.

The search programme

Usage: search [-t][-h] [infile]

This program may be run be typing 'search' at the command line and following the instructions given, or the stub of an .eft file may be entered, as in 'search fred', where fred.eft must exist in the current directory (fred.eft created by running 'solve'). Optionally, the switch '-t' may be used to tell the program not to double up twisted tracks and decompose the double track automatically. The -h option simply repeats this information.

The search programme anayzes the extreme fundamental tracks in the .eft file and then provides the user with the option to access the following menu:

		OPTIONS AVAILABLE


	A. Evaluate the decomposition given by every track in your-jobname.eft

	B. Evaluate decomposition given by a single track in your-jobname.eft

	C. Evaluate decomposition given by a collection of tracks in your-jobname.eft

	D. Add tracks together

	E. Evaluate decomposition from a given track

	F. Decide whether a given N-tuple determines a track

	G. Split a given pattern into component tracks

	H. Determine whether a pair of patterns are compatible

	I. Determine the characteristics of a given track

	J. Determine the characteristics of every track in your-jobname.eft

	Q. Quit menu

The search programme produces a .txt file that contains a transcript of the output produced by the programme.

back to top   maths homepage