Tweaking JavaKh

JavaKh can sometimes be tweaked to work even faster.

On June 22, 2007 Dror received an email from User:Lng containing the following:

I've been trying unsuccessfully to compute the Khovanov homology for a certain link, and I was wondering if you had any suggestions or tips on how to perform the computation.

The link is the 3-twisted double of 11n12, a 44-crossing (I guess) link that can be written as

BR[8, {2, 1, 3, 2, 2, 1, 3, 2, -4, -5, -3, -4, 2, 1, 3, 2, -4, -5, -3, -4,
   -4, -5, -3, -4, 6, 5, 7, 6, 4, 3, 5, 4, -2, -3, -1, -2, 4, 3, 5, 4, 6, 5,
   7, 6}].

I tried using JavaKh in KnotTheory and kept running out of heap space, even when I kept increasing the maximum java heap space (I got up to 2048MB). This is a bit weird because I'd tried similar computations with doubles of other 11-crossing knots and not had any real problems.

Do you know of any tricks or techniques that I could try?

Dror's response was:

What limits JavaKh is probably not the number of crossings but the width, or more precisely, what it perceives to be the width. Given a planar diagram JavaKh converts it to a Morse link via some heuristic algorithm which may well fail sometimes. So it may well be that JavaKh uses a very wide presentation for your knot and therefore fails.

It may be that simply by running JavaKh again and again but with random permutations applied to the crossings of your knot or by perturbing the presentation in other random ways you will eventually hit on a presentation which will not confuse the heuristics and will do well.

If that fails, you should test that my explanation of the situation is right by having JavaKh print the width it is using. And if the width is indeed the problem, find a narrow presentation by hand and feed it to JavaKh after disabling its internal algorithm. Both things will require playing around with the source code, but in rather minimal ways.

User:Lng then wrote:

Indeed, it seems that the width of the Morse link was too large. I fiddled with the link a bit and managed to come up with a form which had smaller width, and was successfully able to run JavaKh on the new link diagram. The computation has a happy ending - as I suspected, one can use it to show that the maximal Thurston-Bennequin number of 11n12 is -2, and this finishes off max-tb for knots with up to 11 crossings.

Thanks so much for your help!

And Jeremy Green, the author of JavaKh who was cced on this exchange, added:

(as for printing the width)

The code to do this already exists but is commented out. It can be enabled by editing the function generateFast() in Komplex.java. Look for this:

  //DEBUG
  /*for (int j = 0; j < nedges; j++)
    System.out.print("#");*/
  /*for (int j = 0; j < kom.ncolumns; j++) {
      System.out.print(" " + kom.columns[j].n);
      if (j < kom.ncolumns - 1) {
        int size = 0;
        for (int k = 0; k < kom.matrices[j].rowsizes.length; k++)
          size += kom.matrices[j].rowsizes[k];
          System.out.print(" (" + size + ")");
        }
        }*/
  //System.out.println();

and uncomment the first pair of lines and the last line.

(as for tweaking the algorithm)

The easiest way of possibly improving the existing algorithm is to increase the search depth. This can be done by changing the constant MAXDEPTH at the start of Komplex.java.

The function for choosing the next crossing to add is chooseXingRecursive. It takes six arguments:

1. int edges[] is the ordered list of outer edges of the current tangle.
2. int pd[][] is the input knot in PD representation.
3. boolean in[] is true for all edges that are contained within the tangle
4. boolean done[] is true for all crossings that have already been added to the tangle.

The other two arguments are used internally by the recursive function.

It returns the index n of the next crossing to add to the tangle. This must satisfy three conditions:

1. The crossing is not already in the tangle, i.e. done[n] is false.
2. The crossing must share at least one edge with the tangle, i.e. edges[] and pd[n][] are not disjoint.
3. The common edges must be adjacent, such that all of the edges of the new tangle are pointing outward.

I haven't looked at the JavaKh code in a while, so it's possible that my description might not be entirely accurate.