A Haskell implementation of combinatorial Heegaard Floer homology

I’ve uploaded a Haskell implementation of a combinatorial algorithm to compute the “hat” version of Heegaard Floer knot homology. This program should be seen as a stepping stone to implementing the more general HF complexes for links, and ultimately for implementing HF^- for large integer surgeries on links. Generally, our approach is the same as the one found in the C++ implementation of Baldwin and Gillam, located here.

The major difference is how we compute generators in positive Alexander grading. Essentially, we noticed the number of possible solutions to a particular integer programming problem was very small. We used this fact to narrow the set of possible permutations with positive Alexander grading and used a recursive algorithm to generate the restricted set of permutations.

In general, Gillam and Baldwin’s program seems to be much faster. Though for some knots such as KT_{2,1} or obviously trivial, but huge, uknots, our program is comparable in speed, and for the uknot example, much faster.

To compile the code, you must install the Data.Vector Haskell and the Data.Array.Repa modules (via cabal install Vector and cabal install Repa) and run the terminal command:

ghc --make -O2 HFKhat.hs -XBangPatterns -XTypeOperators -XTypeSynonymInstances

If you’re having trouble installing Data.Repa, see the instructions here.

You can download the gzipped tar file here.

To Learn more about combinatorial Heegaard Floer homology, check out the references contained in thislink.

Note: If you’re a haskell beginner, I recommend downloading the Haskell platform for best results.

Final Note: More code, including a general module to compute homology over Z/2Z is available at my website.

Advertisements

Path connectedness is a homotopy invariant

I haven’t updated this blog in a while, due to qualifying exam preparation and research projects. I’ll write about the latter soon.  While studying for the geometry/topology qual, I asked a basic question: Is path connectedness a homotopy invariant? Turns out the answer is yes, and I’ve written up a quick proof of the fact below.  You can view a pdf of this entry here.


Proposition 1
 Let {f : X \rightarrow Y} be a homotopy equivalence. If {X} is path connected, then so is {Y}.

Proof: It’s clear that the image of {f} is path connected. Thus, it is enough to show that any point of {Y} can be connected to a point of {f(X)}. Let {g : Y \rightarrow X} be a map such that {f\circ g} is homotopic to {\text{id}_Y}, via the homotopy {h : Y \times I \rightarrow Y}. Let {y \in Y}. Then, {y' = f(g(y)) \in f(X)} and {\gamma(t) = h(y, t)} is a path from {y'} to {y}. \Box

We can deduce the following result from the proof of proposition 1.

Corollary 2 Let {f : X \rightarrow Y} be a homotopy equivalence. Then {X} is path connected if, and only if, {f(X)} is path connected.

Proof: If {f(X)} is path connected, then {Y} is path connected. Hence {X} is path connected. \Box