README for KhoHo version 0.9.3.5, 19 December 2004
==================================================
KhoHo is a program for computing and studying Khovanov homology. It is
written by Alexander Shumakovitch and can be freely
downloaded from http://www.geometrie.ch/KhoHo and redistributed under the
terms of GPL v.2 (see 'copyright' file for details).
I. Links and references.
--------------------------
Detailed information about Khovanov homology can be obtained from
1. Dror Bar-Natan, On Khovanov's categorification of the Jones polynomial,
Algebr. Geom. Topol. 2 (2002), 337--370; arXiv:math.QA/0201043;
http://www.math.toronto.edu/~drorbn/papers/Categorification/
2. Stavros Garoufalidis, A conjecture on Khovanov's invariants,
preprint 2001
3. Mikhail Khovanov, A categorification of the Jones polynomial,
Duke Math. J. 101 (2000), no. 3, 359--426; arXiv:math.QA/9908171
4. Mikhail Khovanov, Patterns in knot cohomology I,
arXiv:math.QA/0201306
5. Mikhail Khovanov, Categorifications of the colored Jones polynomial,
arXiv:math.QA/0302060
6. Eun Soo Lee, The support of the Khovanov's invariants for alternating
knots, arXiv:math.GT/0201105
7. Eun Soo Lee, On Khovanov invariant for alternating links,
arXiv:math.GT/0210213
8. Oleg Viro, Remarks on definition of Khovanov homology,
arXiv:math.GT/0202199
9. Stephan Wehrli, Khovanov Homology and Conway Mutation,
arXiv:math.GT/0301312
II. System requirements.
------------------------
a) PARI/GP version 2.2.0 or higher (2.2.5 or higher recommended). Can be
freely downloaded from http://www.parigp-home.de
PARI/GP is a software package for computer-aided number theory. Although
its symbolic computational power pales in comparison with the one of
Maple or Mathematica, PARI is significantly faster than these two
programs and its data management is much more efficient and transparent.
Since the core of KhoHo is a PARI/GP script, it is essential to have
this package installed before making any attempts to run KhoHo.
Note that KhoHo requires the development (as of this writing) version
2.2.* of PARI/GP. Versions up to 2.2.3 had a nasty memory leak bug.
It is therefore recommended to install version 2.2.5 or higher.
b) Standard GNU development environment including GNU C Compiler 'gcc' and
GNU 'make' utility.
Remark: KhoHo should work on any U*ix operating system. It was tested on
Debian GNU/Linux 3.0 (woody) and Compaq True64 only, though. Please
report any problems and/or success stories on other platforms to
Shurik@Dartmouth.edu
III. Installation.
------------------
a) Download the latest version of KhoHo from http://www.geometrie.ch/KhoHo
Place the file called KhoHo.tar.gz somewhere in your home directory
and unpack it with 'tar xfzv KhoHo.tar.gz' command. Directory KhoHo-x.y.z
should appear, where x.y.z is the version downloaded. Go into this
directory with 'cd KhoHo-x.y.z' command.
b) Make sure that an appropriate version of PARI/GP is installed and its
header files are available in one of the standard places like
/usr/include/pari or /usr/local/include/pari If it is impossible to
install PARI there, change Makefile accordingly.
c) Run 'make' command. If everything worked out fine, there should be three
new library files created: nicematr.so, print_ranks.so, and sparreduce.so
The first two contain some auxiliary functions and are not essential for
KhoHo operation. But sparreduce.so is crucial. It implements a chain
complex reduction algorithm, on which KhoHo is based.
d) Download from http://www.geometrie.ch/KhoHo any knot and link tables you
like. The basic set include KTable_11, LTable_11 and SpecialLinks.
IV. How to run (for impatient or excited).
------------------------------------------
a) Start PARI's programmable calculator:
$ gp
b) Read KhoHo and main tables of knots and links:
(12:00) gp > read(KH)
c) Take a knot from the table:
(12:02) gp > knot = KTable(3, 1)
d) Compute its rational and torsion Khovanov polynomial:
(12:03) gp > KhPol(knot)
e) Enjoy the result:
[((q^8 + q^6)*t^3 + q^4*t + 1)/(q^9*t^3), 1/(Q^7*t^2)]
Remarks:
1) KTable(n, m) returns the knot number m with n crossings. LTable does
the same for links. For knots with 11 crossings or more as well as for
all links, it should be specified whether the knot or link is alternating
or not. I.e. KTable("11n", 123) or LTable("4a", 1). If m is negative, the
mirror image of the knot or link number -m is returned.
2) KhPol returns a vector with two entries, that contain rational and
torsion polynomials, respectively. To access them separately use
(12:04) gp > pols = KhPol(knot)
(12:04) gp > pols[1]
time = 0 ms.
%13 = (t^3*q^8 + t^3*q^6 + t*q^4 + 1)/(t^3*q^9)
(12:04) gp > pols[2]
time = 0 ms.
%14 = 1/(Q^7*t^2)
V. How to run (for interested or impressed).
--------------------------------------------
a) Start PARI's programmable calculator:
$ gp
b) Read KhoHo:
(12:00) gp > read(KhoHo)
c) Define a link diagram as a 4 times the number of crossings matrix in
Bar-Natan's notation:
(12:02) gp > diagr = [6, 1, 7, 2; 8, 3, 5, 4; 2, 5, 3, 6; 4, 7, 1, 8]
d) Check that the diagram is correct (i.e. represents a 4-valent graph):
(12:03) gp > check_diagr(diagr)
e) Prepare the diagram for further consumption by KhoHo. A string (acting
as a diagram's name) should be supplied. This name is used to identify
the diagram for which various invariants are computed.
(12:05) gp > link = preplink(diagr, "what a wonderful link!")
f) Compute Betti numbers of the link's Khovanov homology:
(12:07) gp > Betti(link)
g) Compute torsions of the link's Khovanov chain complex differentials:
(12:10) gp > D_tors(link)
i) Create a TeX table combining all the results together and stare at it in
amusement:
(12:12) gp > TeXview(link, "the best link ever", "file4link")
j) Read sources of KhoHo through to learn even more (it's thought to be
well-documented).
Remark: Since version 0.9.1 KhoHo supports calculation of the reduced
Khovanov homology. To use this feature execute
(12:15) gp > set_H_reduced()
immediately after reading KhoHo. To return back to `normal' homology use
(12:15) gp > set_H_standard()
VI. Further capabilities.
-------------------------
Using KhoHo one can
a) take the mirror image or a link with 'mirror';
b) take the connected sum or the disjoin union of two knots with 'connsum'
and 'disunion', respectively;
c) get the linking matrix of a link with 'get_lk_matrix';
d) given the Khovanov polynomial of a link, figure out how many diagonals it
occupies with 'pol_diags';
e) given the Khovanov polynomial of a knot, check whether it satisfies
Conjecture 1 by Bar-Natan with 'check_conj1' ...
f) ... and whether it's H- or T-thick with 'check_H_thick' and
'check_T_thick', respectively;
g) do e) and f) for links and the corresponding extension of Conjecture 1
(due to Lee) with the help of 'conj1_factor';
h) cyclically reorder components of a link diagram with 'comp_reorder' to
compute the reduced Khovanov homology with respect to an arbitrary one;
i) compute signature of a nonsplit link with, well, 'signature';
j) combine the ranks of standard and reduced homology into a single TeX
table using 'TeX_H_print' or 'TeX_H_view'.
VII. Known bugs.
----------------
a) KhoHo assumes that the number of non-zero entries (i.e. adjacencies) in
the matrix of a Khovanov chain complex differential is never bigger than
5 times the sum of matrix sizes. It is true for small knots and links,
but is false in general. If you see something like the following error
*** array index (5853) out of allowed range [1-5852]:
*** ...T];diff_matrices_s[j_ST][m_ptr-1]=tT_gen;diff
^--------------------
you've been bitten by this assumption. Try to increase this constant 5 in
the function initDmatrices from KhoHo_chain then. On the other hands,
setting it too big could result in insufficient memory or bug b).
b) PARI/GP can't handle vectors with more than 2^24-2 elements on a 32-bit
architecture. Although this number seems to be huge, the constrain means
that the sum of sizes of differential matrices can't be bigger than
1'677'721 (or even less if the constant 5 from bug a) has been increased).
The (2, 16) torus link has a 2'018'016x2'018'016 matrix already. The
(2, 15) torus knot barely fits with a 630'630x756'756 matrix. This
problem doesn't appear on 64-bit architectures.
VIII. Feedbacks.
----------------
Please send any suggestions, remarks, bug reports, patches, and wishes
concerning KhoHo to Shurik@Dartmouth.edu
IX. Appendix: a simple session.
-------------------------------
It takes less than 3 minutes and requires less than 20MB of memory to
compute Khovanov homology of the (2, 11) torus knot on a 600MHz computer.
$ gp
GP/PARI CALCULATOR Version 2.2.4 (alpha)
i686 running linux (ix86 kernel) 32-bit version
(readline v4.3 enabled, extended help available)
Copyright (C) 2002 The PARI Group
PARI/GP is free software, covered by the GNU General Public License, and
comes WITHOUT ANY WARRANTY WHATSOEVER.
Type ? for help, \q to quit.
Type ?12 for how to get moral (and possibly technical) support.
realprecision = 28 significant digits
seriesprecision = 16 significant terms
format = g0.28
parisize = 50000000, primelimit = 5000
(02:26) gp > read(KH)
Loading the table of knots with up to 11 crossings ... done.
Loading the table of links with up to 11 crossings ... done.
Loading some special knots and links ... done.
time = 140 ms.
(02:26) gp > knot = KTable("11a", 367)
time = 0 ms.
%1 = [[12, 2, 13, 1; 14, 4, 15, 3; 16, 6, 17, 5; 18, 8, 19, 7; 20, 10, 21, 9;
%22, 12, 1, 11; 2, 14, 3, 13; 4, 16, 5, 15; 6, 18, 7, 17; 8, 20, 9, 19; 10,
%22, 11, 21], "tknot11a_367", 11, 22, 11, 0, 11, 12, -1, 34, 18, 1]
(02:27) gp > KhPol (knot)
Computing differential ranks and torsions ...
Reducing the chain complex first ...
Computing the list of generators ... done.
Primary grading: 0. Computing matrices of differentials ... done.
Primary grading: 1. Computing matrices of differentials ... done.
Primary grading: 2. Computing matrices of differentials ... done.
Primary grading: 3. Computing matrices of differentials ... done.
Primary grading: 4. Computing matrices of differentials ... done.
Primary grading: 5. Computing matrices of differentials ... done.
Primary grading: 6. Computing matrices of differentials ... done.
Primary grading: 7. Computing matrices of differentials ... done.
Primary grading: 8. Computing matrices of differentials ... done.
Primary grading: 9. Computing matrices of differentials ... done.
Primary grading: 10. Computing matrices of differentials ... done.
Secondary grading: 33. Reducing the chain complex ... done.
Secondary grading: 31. Reducing the chain complex ... done.
Secondary grading: 29. Reducing the chain complex ... done.
Secondary grading: 27. Reducing the chain complex ... done.
Secondary grading: 25. Reducing the chain complex ... done.
Secondary grading: 23. Reducing the chain complex ... done.
Secondary grading: 21. Reducing the chain complex ... done.
Secondary grading: 19. Reducing the chain complex ... done.
Secondary grading: 17. Reducing the chain complex ... done.
Secondary grading: 15. Reducing the chain complex ... done.
Secondary grading: 13. Reducing the chain complex ... done.
Secondary grading: 11. Reducing the chain complex ... done.
Secondary grading: 9. Reducing the chain complex ... done.
Secondary grading: 7. Reducing the chain complex ... done.
Secondary grading: 5. Reducing the chain complex ... done.
Secondary grading: 3. Reducing the chain complex ... done.
Secondary grading: 1. Reducing the chain complex ... done.
Secondary grading: -1. Reducing the chain complex ... done.
done with the reduction.
... done with computing ranks and torsions.
Computing Betti numbers ...
... done with computing Betti numbers.
time = 2mn, 43,960 ms.
%2 = [q^33*t^11 + q^29*t^10 + q^29*t^9 + q^25*t^8 + q^25*t^7 + q^21*t^6 +
q^21*t^5 + q^17*t^4 + q^17*t^3 + q^13*t^2 + (q^11 + q^9), Q^31*t^11 +
Q^27*t^9 + Q^23*t^7 + Q^19*t^5 + Q^15*t^3]
(02:29) gp >