My master's thesis was Knot Theory, Simple Weaves, and an Algorithm for Computing the Homfly Polynomial from CMU in 1989.

The normal approach to calculating the Homfly polynomial on a link builds a binary tree of progressively simpler links with polynomial tags, and sums the tags at the leaves. My algorithm used dynamic programming: a border splits a link into solved and unsolved regions and the border is moved across the link. There are 2n crossings of the border at any time and up to n! tagged links represent the state of the computation. Its 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 at most the ceiling of sqrt(c). (The thesis was treating each intermediate link as O(1) work, but it's really O(c²) due to multiplying the polynomial tags.)

I revised and shortened the thesis in 1992 as A Dynamic Approach to Calculating the HOMFLY Polynomial for Directed Knots and Links. The revision is more what the code does rather than giving the history of knot polynomials and trying to prove why the algorithm is possible. The revision improves the ordering of crossings with the backwards-forwards algorithm. I was trying to get it published, but the magazine wanted it clearly presented in under half a page, and I couldn't figure out how to do that.

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 1989 version of the code.

Current versions:

• bound.c
• bound.h
• control.c
• control.h
• dllink.c
• dllink.h
• knot.c
• knot.h
• makehom.txt
• model.c
• model.h
• order.c
• order.h
• poly.c
• poly.h
• standard.h

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