Tweaking JavaKh - Revision history

Drorbn at 11:40, 31 July 2008

2008-07-31T11:40:13Z

← Older revision		Revision as of 07:40, 31 July 2008
Line 32:		Line 32:

	:(as for printing the width)		:(as for printing the width)
	:The code to do this already exists but is commented out. It can be enabled by editing the function <code>generateFast()</code> in Komplex.java. Look for this:		:The code to do this already exists but is commented out. It can be enabled by editing the function <code>generateFast()</code> in <code>Komplex.java</code>. Look for this:
	//DEBUG		//DEBUG
	/*for (int j = 0; j < nedges; j++)		/*for (int j = 0; j < nedges; j++)

Drorbn at 11:38, 31 July 2008

2008-07-31T11:38:47Z

← Older revision		Revision as of 07:38, 31 July 2008
Line 55:		Line 55:
	:# <code>int pd[][]</code> is the input knot in PD representation.		:# <code>int pd[][]</code> is the input knot in PD representation.
	:# <code>boolean in[]</code> is true for all edges that are contained within the tangle		:# <code>boolean in[]</code> is true for all edges that are contained within the tangle
	:# <code>boolean done[]<code> is true for all crossings that have already been added to the tangle.		:# <code>boolean done[]</code> is true for all crossings that have already been added to the tangle.
	:The other two arguments are used internally by the recursive function.		: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:		:It returns the index n of the next crossing to add to the tangle. This must satisfy three conditions:
	:# The crossing is not already in the tangle, i.e. <code>done[n]</code> is false.		:# The crossing is not already in the tangle, i.e. <code>done[n]</code> is false.
	:# The crossing must share at least one edge with the tangle, i.e. <code>edges[]<code> and <code>pd[n][]<code> are not disjoint.		:# The crossing must share at least one edge with the tangle, i.e. <code>edges[]</code> and <code>pd[n][]</code> are not disjoint.
	:# The common edges must be adjacent, such that all of the edges of the new tangle are pointing outward.		:# The common edges must be adjacent, such that all of the edges of the new tangle are pointing outward.

Drorbn at 08:47, 22 June 2007

2007-06-22T08:47:01Z

← Older revision		Revision as of 04:47, 22 June 2007
Line 32:		Line 32:

	:(as for printing the width)		:(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:		:The code to do this already exists but is commented out. It can be enabled by editing the function <code>generateFast()</code> in Komplex.java. Look for this:
	//DEBUG		//DEBUG
	/*for (int j = 0; j < nedges; j++)		/*for (int j = 0; j < nedges; j++)
Line 52:		Line 52:

	:The function for choosing the next crossing to add is <code>chooseXingRecursive</code>. It takes six arguments:		:The function for choosing the next crossing to add is <code>chooseXingRecursive</code>. It takes six arguments:
	# <code>int edges[]</code> is the ordered list of outer edges of the current tangle.		:# <code>int edges[]</code> is the ordered list of outer edges of the current tangle.
	# <code>int pd[][]</code> is the input knot in PD representation		:# <code>int pd[][]</code> is the input knot in PD representation.
	boolean in[] is true for all edges that are contained within the tangle		:# <code>boolean in[]</code> is true for all edges that are contained within the tangle
	boolean done[] is true for all crossings that have already been added to		:# <code>boolean done[]<code> is true for all crossings that have already been added to the tangle.
		⚫	:The other two arguments are used internally by the recursive function.
	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		:It returns the index n of the next crossing to add to the tangle. This must satisfy three conditions:
			:# The crossing is not already in the tangle, i.e. <code>done[n]</code> is false.
	must satisfy three conditions:
	1. The crossing is ~~not~~ ~~already~~ in the tangle, i.e. ~~done~~[n] is ~~false~~.		:# The crossing must share at least one edge with the tangle, i.e. <code>edges[]<code> and <code>pd[n][]<code> are not disjoint.
	2. The ~~crossing~~ must ~~share~~ at ~~least~~ ~~one~~ ~~edge~~ ~~with~~ the tangle, ~~i.e~~.		:# The common edges must be adjacent, such that all of the edges of the new tangle are pointing outward.
	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		:I haven't looked at the JavaKh code in a while, so it's possible that my description might not be entirely accurate.
	description might not be entirely accurate.

Drorbn at 07:35, 22 June 2007

2007-06-22T07:35:42Z

New page

[[Khovanov Homology|JavaKh]] can sometimes be tweaked to work even faster.

On June 22, 2007 [[User:Drorbn|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 [[K11n12|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 <code>MAXDEPTH</code> at the start of <code>Komplex.java</code>.

:The function for choosing the next crossing to add is <code>chooseXingRecursive</code>. It takes six arguments:
# <code>int edges[]</code> is the ordered list of outer edges of the current tangle.
# <code>int pd[][]</code> is the input knot in PD representation
boolean in[] is true for all edges that are contained within the tangle
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.