My master's thesis was A Dynamic Approach to Calculating the HOMFLY Polynomial for Directed Knots and Links. The algorithm used is dynamic programming, running time is O((n!)(2ⁿ)(c³)) and the space used is O((n!)(c²)), where c is the number of crossings in the link and n is bounded above by sqrt(c)+1.

I have code for this:

• Latest version, June 5 2010.
• Previous version, revised about 1996, in which I had introduced several bugs.
• I don't have a copy of the 1990 version.

The program is written to handle strings with cross sections of up to 24 strings (12 in, 12 out), but remember that it uses a factorial amount of space. The input file describing a knot needs to be created by hand, see knot.h for that format. Here are some sample input files.

1. boromean.txt, three strings, no two of which are knotted, but the three together are. This finishes instantaneously.
2. knotseven.txt, seven strings which are intertwined. This finished in 7 seconds with these results. (This is the smallest link with a cross section of 14 strings.)
3. knotnine.txt, nine strings which are intertwined. This ran for 8 hours before crashing my machine. I ran it on a 66mhz 486 with 16 meg ram and a 500 meg hard drive compiled optimized with a 32-bit gcc. (This is the smallest link with a cross section of 18 strings.)

KnotPlot is capable of generating this knot format when it computes the Homfly polynomial. On Windows, it places files in this format temporarily in the %TMP% directory. It pictorially displays the knots and can save them in this format; I don't know if it can read this format and display the knot a file represents.

thesis2.ps is a diagram showing how the algorithm works for one small knot.

thesis1.ps is a diagram showing how a simpler method (which I call the binary tree approach) works for that same small knot.

If you want just the Jones polynomial, and you want it for an alternating link, there is a very similar but faster algorithm (with no code available). The paper on it is "Computing the Tutte Polynomial of a Graph and Jones Polynomial of a Knot of Moderate Size" by K. Sekine, H. Imai, and S. Tani.

ISAAC and RC4, a comparison of two stream ciphers
Evaluating hash functions
Ye Olde Catalogue of Boy Scout Skits
Tiles in my Half Bath
Table of Contents