### rjenkins-1.0 README file

    		BOB JENKINS' HOMFLY POLYNOMIAL PROGRAM

    						rjenkins@cs.berkeley.edu

    This is the code for the master's thesis of Bob Jenkins at CMU.

    The algorithm works by dynamic programming.  The normal approach creates a
    binary tree (each node an intermediate knot; all the leaves unlinks).  My
    approach collects nodes with the same intermediate knot, sums their polynomials
    thus far, and continues on.  In fact, it decides which crossings to operate on
    in an attempt to maximize the number of duplicates.  The resulting algorithm
    is factorial in time and space on the max-min cross-section of the knot, which
    is the square root of the number of crossings or less.  Given the max cross
    section, it is only linear on the number of crossings.  (You can have lots and
    lots of crossings, as long as the cross section is small.)  A Sun 3 tends to
    die on cross sections of more than 18 strings (9 in, 9 out).

                                        - Bob Jenkins

    Most common algorithm repeatedly divides the knot, whereas his uses increasing
    circles to cover crossings. He claims it is a lot faster.  The major drawback
    of his implementation, until recently, had been the amount of space it used.
    However, he now has a garbage collection algorithm that is able to reclaim most
    of the space.  (I hope we are talking about the same computation: Bob said that
    knots of ~95 crossings had been computed, which is much larger than I
    remembered.)

    I've always put all the .c, .h, .txt, etc files in a single directory.
    Compile this program with the makefile; the executable will be named homfly.

    When the program prompts you for a knot file, borromean.txt (no quotes, no
    leading pathname, just borromean.txt) is a legal response.  The program prints
    out some diagnostics (how much work it did to handle each crossing), then
    prints the polynomial for the given link.

    The file knot.h describes the format of knot files.  There are no additional
    features to this program; there is no other documentation.  I have not yet
    published a paper describing how this works.  I expect to write such a paper
    over Christmas break.