PAKG - Prime Alternating Knot Generator
Version 072303-001 (C) 2003 O. Flint, S. Rankin, & P. de Vries

Last updated: November 28th, 2003.
Previously updated: July 23rd, 2003.

DOWNLOADS

PAKG was written in ISO-compliant C++, and while the source code is not yet ready for public release, binaries are available for many Linux platforms, as well as Win32 (WinXP, Win2K, Win9x) and MacIntosh OSX.  The 64-bit Linux platforms (Alpha & IA64) are useful for crossing sizes greater than 22, since at that point more RAM than can be addresssed by a single process on the 32 bit architectures is required.  Please see the performance details below.

Platform	File
Win32	pakg-072303-win32.zip
Linux/X86 (G++ 3.2.2)	pakg-090503-ia32gcc.tar.gz
Linux/X86 (Intel C++ v7.1)	pakg-072303-linux-ia32.tar.gz
Linux/Alpha (GCC 2.95)	pakg-072303-linux-alpha.tar.gz
Linux/IA64 (Intel C++ v7.1)	pakg-072303-linux-ia64.tar.gz
Mac OS X	pakg-090503-macosx.sit

PERFORMANCE DETAILS

At least for the early crossing sizes (at present, we have enumerated up to 23 crossings), the number of knots at each crossing size is approximately 5 times that of the previous size (factor 5.5 from 22 to 23 crossings).  The computation and memory requirements to generate the various crossing sizes scales at the same rate.  A significant amount of  theoretical and software engineering work has been put into PAKG to limit the amount of memory required at any given crossing size so that the size of knot catalog one can generate with reasonably priced hardware is maximized.  The following table summarizes the sizes and resources required to generate the various crossing sizes

n	# Knots	Benchmark Platform	Time	Allocated Memory	Catalog Size
4-15	1 - 85,263	2.8GHz P4 Xeon (512k L2)/Linux IA32 (Intel C++ v7.1 -O3)	trivial	trivial	trivial
16	379,799	2.8GHz P4 Xeon (512k L2)/Linux IA32	trivial	~1.8mB	6.5mB
17	1,769,979	2.8GHz P4 Xeon (512k L2)/Linux IA32	25s	~6.3mB	31.8mB
18	8,400,285	2.8GHz P4 Xeon (512k L2)/Linux IA32	2m 54s	~22mB	159.6mB
19	40,619,385	2.8GHz P4 Xeon (512k L2)/Linux IA32	14m 35s	~24mB	812.4mB
20	199,631,989	2.8GHz P4 Xeon (512k L2)/Linux IA32	1h 29m	~120mB	4.2gB
21	990,623,857	2.8GHz P4 Xeon (512k L2)/Linux IA32	6h 54m	~433mB	21.8gB
22	4,976,016,485	2.8GHz P4 Xeon (512k L2)/Linux IA32	35h 44m	~2.2gB	114.5gB
23	25,182,878,921	1.25GHZ Alpha EV68CB/Linux (Compaq ES45) (GNU C++ 2.95 -O3)	9d 12h 3m	~13.2gB	604gB
24	??	??	53d?	~72gB?	~3tB?

QUICK USAGE DETAILS

PAKG generates the prime alternating knots using techniques developed by Ortho Flint and Stuart Rankin.  These techniques are discussed in detail in their papers which can be found at http://www.math.uwo.ca/~srankin/knotprint.html. The knots themselves may be viewed at http://knotilus.math.uwo.ca.

PAKG generates the complete collection of prime alternating knots at the given crossing size by applying various operators to the complete collection of prime alternating knots at the preceding crossing size.

As a result, an initial collection of prime alternating knots of 4 crossings has to be prepared for PAKG to begin its work.  This is the purpose of the initpakg program.  This program takes no command line arguments and creates a directory in the current working directory called c4.  In this directory it places a file called knots.dat.  This file holds a (modified -- see hereditary Dowker code discussion below) Dowker code for the single prime alternating knot of 4 crossings .

From this base, PAKG can build catalogs for progressively larger crossing sizes.  The pakg program takes only a single argument -- the crossing number to enumerate.  Of course, the data from the previous crossing size is required to be on disk.  An example may illustrate.  To build the prime alternating knots from 4 to 8 crossings, the user would issue commands like:

./initpakg
./pakg 5
./pakg 6
./pakg 7
./pakg 8

Files named knots.dat containing the knot catalogs would be created in subdirectories named c5, c6, c7 etc.  Pakg outputs status information as it operates.  This information is prefaced by a date/time stamp.  The information is also copied to a log file for future reference.  The name of the log file will be pakg-cxx.log, where xxx is the crossing level computed.  To reassure the user that PAKG is still hard at work, PAKG also outputs progress information in each stage.  The progress information (which begins to dominate the console display at larger crossing sizes) is NOT sent to the logfile.

The total number of knots at the given crossing size is  displayed as the program exits. 

FILE FORMAT DETAILS

The initpakg and pakg programs use Master Group Code (MGC) internally as they manipulate knots.  MGC and the associated concept of the Master Array (MA) are critical to the functionality of the generation process.  However, the MGC for a prime alternating knot of n crossings requires something of the order of 3n bytes on average.  In fact, PAKG uses much more memory than this on a per knot basis because it stores each field of the MGC in a size natural for the target architecture (usually 32 bits), even though smaller (but less CPU-efficient) sizes could be employed.

Since the size of the catalog at the higher crossing levels begins to become the limiting factor for practical use of the program, PAKG uses a modified version of Dowker Code for its external (on-disk) storage, as well as certain internal databases.  Dowker code also has the additional benefit that each knot record is a fixed length (Master Group Codes can very greatly in length, depending on the knot in question).

We have called the modified version of Dowker code that PAKG uses "hereditary Dowker", or h-Dowker for short. We wanted to minimize the work required to convert the Dowker code for the zero-position group back into a master array, and we decided to record the fact that a crossing could not flype by the use of a negative sign. To avoid confusion with the Dowker-Thistlethwaite code for a non-alteranting knot, wherein negative signs are used to indicate an over/under change (and also to not waste storage space), we decided to subtract one from each Dowker code entry before putting the flype information sign on. Thus an h-Dowker code for a prime alternating knot is an array of signed odd integers.  

Creating the MGC for a knot (which PAKG does for each knot) requires that the orbit of each group be discovered.  Orbit parsing is one of the most time-consuming tasks PAKG undertakes.  Since many groups do not flype, the use of the h-Dowker code allows PAKG to avoid parsing orbits for non-flyping groups.   PAKG could operate with traditional Dowker code (i.e. where no negative values appear).  In this case it would simply be slower, as it would have to parse the orbits of every group it encounters.

The format of the 'knots.dat' files that PAKG creates is very straightforward.  There is no special header at the beginning of the file.  Each file contains n+1 bytes for each knot, where n is the crossing size in question.  The records are stored consecutively.  To determine the number of knots in a file, simply take the file size and divide by (n+1).  The first byte in each knot record is a status byte.  The status byte contains various bits that PAKG uses to optimize the generation process.  Probably the only bit of use to general researchers is bit 2 (tested with mask 0x4 in C/C++).  If this bit is a one, the knot in question has some symmetry.  If this bit is a zero, the knot is asymmetric.  The values of the h-Dowker code for the knot then follow.  Each value is an 8 bit 2's-complement integer (a signed char in C/C++).  Each code value has 1 subtracted from it.  Hence the four bytes -5, -7, -1, -3 can be intepreted as the h-Dowker code -6, -8, -2, -4.  This is equivalent to the traditional Dowker code 6,8,2,4, but it has the added benefit of informing you that none of the groups in this knot flype.  If you are not interested in using h-Dowker, you can simply take the absolute value of each code byte.  The result will be a traditional Dowker code.

There are two additional utilities included in the distribution which are of some use in manipulating .dat files.  The first, decodedat, will output to the console (stdout stream) in text form the various knots in a given knots.dat  file.  You can select Dowker, Gauss, Group Code or Master Group Code style output.  

The second, pak2dat, is designed be used with the pak files found in Morwen Thistlethwaite's KnotScape package.  This package includes Dowker codes for the prime alternating knots of up to 16 crossings.  It can be found at http://www.math.utk.edu/~morwen/knotscape.html.  These Dowker Codes were generated by different researchers using totally different methods than PAKG's.  The KnotScape package includes a decode_a program which can be used to decode the Dowker codes from KnotScape's pak format to a more readable ASCII text file.  The pak2dat program in the PAKG distribution can then be used to convert the resulting text file into a .dat file.  This .dat file can then be inspected with decodedat.   For example, in order to compare the knots of 8 crossings generated by PAKG to those found in the KnotScape package, one could issue the following commands (assuming the 8 crossing knots had already be enumerated with PAKG):

./decode_a 8a.pak 8a.txt 1 100000

The decode_a command must be compiled from the KnotScape distribution.  The 8a.pak file is included in the distribution and contains the alternating knots of 8 crossings.  A file named 8a.txt will be created.  It is necessary to specify a starting and ending "knot number" -- in this case 1 and 100,000 were used.  If the ending knot number is greater than the number which exist (in this case only 18 alternating knots of 8 crossings exist), then only those knots are output.   The resulting 8a.txt can then be converted to a .dat file:

./pak2dat 8a.pak.decoded  8a.dat 8

Now we can compare the contents of 8a.dat and the c8/knots.dat files to determine if they have the same contents.  We will do this by converting both dat files to textual form with the decodedat program.  Because the two files may have the knots in different orders, in order to compare the resulting text files with the standard UNIX-style diff command we must sort the outputs with the sort command:

./decodedat 8a.dat 8 | sort > t-8.txt
./decodedat c8/knots.dat 8 | sort > sr-8.txt
diff t-8.txt sr-8.txt

The result in this example will be that diff reports no difference between the files.  This confirms that the contents of the files are the same.


ADDITIONAL NOTE ON h-DOWKER

Although in general, each prime alternating knot has many Dowker codes, there is only one h-Dowker code for the knot.  An h-Dowker code for a prime alternating knot is the Dowker code for the configuration of the knot that is obtained by taking the zero position of each group in the MA for the knot (and then incorporating any non-flyping information as described above).  This makes it possible to directly compare the knot catalogs of KnotScape and PAKG as shown above.  pkg2dat may be used to convert a file containing conventional Dowker codes into a file containing the h-Dowker codes for the knots whose Dowker> codes were contained in the input file.


NOTES ON THE OUTPUT OF DECODEDAT

The decodedat program can create textual representations of a knots.dat file in either Dowker, Gauss, Group or Master Group form.  The Dowker and Gauss displays are self-explanatory.  The Dowker display is the traditional Dowker (the negative values present in h-Dowker are not shown) that is extracted from the h-Dowker code, and hence represents the standardized 0-position configuration for the knot in question.  The Gauss code is similarly unique.  A group code for a knot might be display as:

-2_1,1_1,5_1,-2_1,5_1,1_1

Each entry in the code is a group arc.  The group arc entry -2_1 is intepreted as an occurrence of the first group of size 2, and the minus sign indicates that a knot traversal will enter the second arc of the group at the same end of the group at which it exited the first arc of the group.  Each group arc entry will necessarily have a matching arc somewhere else in the code.  A group of size 1, such as 1_1 (the first group of size 1) is sometimes referred to as a "loner".  A "loner" may have a positive or negative orientation, but this can only be determined once its orbit (if any) has been discovered.  Since a group code does not encompass the concept of flyping groups and their positions, all loners are shown as positive.  Negative non-loner groups are shown however, because a simple traversal through the Dowker or Gauss code of the knot will expose whether a group of size 2 or greater has positive or negative orientation.  The group codes shown by decodedat are standardized, 0-position group codes.  Some of the groups shown may or may not have additional flyping positions. 

A Master Group Code (MGC) for the same knot looks like:

*-2_1,-1_1^0,*5_1,-1_1^1,*-2_1,-1_1^1,*5_1,-1_1^0

Since this is an MGC which has been standardized, it is in fact the Master Array (MA) for this knot.  From the MGC we can see that that first loner group is indeed a negative group and can flype to two positions.  The notation -1_1^0 denotes the first (0th) position of the first loner.  The notation *-2_1 indicates that the first 2-group does not flype.

---