Opened 3 years ago

Closed 3 years ago

#20509 closed enhancement (fixed)

khovanov homology of links

Reported by: mmarco Owned by:
Priority: major Milestone: sage-7.2
Component: algebraic topology Keywords: knots
Cc: kcrisman, tscrim, amitjamadagni, jhpalmieri, fuglede Merged in:
Authors: Miguel Marco Reviewers: Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: 8f73dc4 (Commits) Commit: 8f73dc43de8c1fdbbb760724658654a642351350
Dependencies: Stopgaps:

Description (last modified by mmarco)

This branch implements khovanov homology for links.

sage: K = Link([[[1, -2, 3, -1, 2, -3]],[-1, -1, -1]])
sage: K.khovanov_homology()
{-9: {-3: Z},
-7: {-3: 0, -2: C2},
-5: {-3: 0, -2: Z, -1: 0, 0: 0},
-3: {-3: 0, -2: 0, -1: 0, 0: Z},
-1: {0: Z}}

It is computed by following the definition.

Change History (16)

comment:1 Changed 3 years ago by mmarco

  • Branch set to u/mmarco/khovanov_homology_of_links

comment:2 Changed 3 years ago by mmarco

  • Authors set to Miguel Marco
  • Cc kcrisman tscrim amitjamadagni jhpalmieri fuglede added
  • Commit set to ea937a9e5f263eecdfe9ca32272cbb07a00d582f
  • Component changed from PLEASE CHANGE to algebraic topology
  • Description modified (diff)
  • Keywords knots added
  • Status changed from new to needs_review
  • Type changed from PLEASE CHANGE to enhancement

New commits:

ea937a9Added khovanov homology method to Links

comment:3 Changed 3 years ago by tscrim

Some comments:

  • I don't see the point of having attributes _smoothing and _enhanced_states, these should be separated out into @cached_method. Although it seems like _enhanced_states is all you really need.
  • Instead of type(_) == tuple, use isinstance(_, tuple).
  • Instead of
    difs = [_ for _ in range(len(V1[0])) if V1[0][_] != V2[0][_] ]
    
    you can do
    V20 = V2[0]
    difs = [index for index,value in enumerate(V1[0]) if value != V20[index] ]
    
  • The output of khovanov_homology is mutable, so it should not be cached.

comment:4 Changed 3 years ago by git

  • Commit changed from ea937a9e5f263eecdfe9ca32272cbb07a00d582f to c3dfb06199943646ad2e06ee6ca2f0ded5321270

Branch pushed to git repo; I updated commit sha1. New commits:

c3dfb06Changes suggestd by reviewer

comment:5 Changed 3 years ago by mmarco

I made the suggested changes. I am not entirely happy with the format of the output, but i guess it is the price to pay for caching it.

Also, I would like to have a smarter way to take advantage of caching (for instance, if the whole homology has been computed, don't compute again the smaller pieces, and vice-versa: don't compute the pieces already computed when we compute the whole picture).

Is there a way to get which input values have already been cached?

comment:6 Changed 3 years ago by tscrim

I was thinking the value of bases is what should be cached since states is just a transient variable.

To get around this recomputing issue, you could have another (private) cached method that computes it on a by-degree basis (perhaps also taking the height as input. Thus we can make the user-level accessible function is not cached (and can thus return a dict for better usability). Eh...I might have to think a little more on this. I agree that the format is bad. (Another option would be Family.)

Also, you can make this change:

-m[ii,jj] = (-1)**sum([V2[0][_] for _ in range(difs[0]+1, ncross)])
+m[ii,jj] = (-1)**sum(V2[0][difs[0]+1:ncross])

comment:7 follow-up: Changed 3 years ago by mmarco

Indeed, it is the value of "bases" what we reuse, but that is a dictionary, and hence mutable. Again, we could have it in a tuple format and convert it to dictionary each time we recover it.

In general, what to compute and cache each time is quite tricky here. Now we are computing all the bases of the chain complexes once and caching it. So if the user just asks for a given height, we compute a lot that we don't need. Anyways, my experience is that the biggest part of the computation is taken by computing the cohomology of the complexes, so it is not so bad.

comment:8 Changed 3 years ago by jhpalmieri

You could also create a separate class for Khovanov homology, at which point you would have complete control over its output format.

comment:9 in reply to: ↑ 7 Changed 3 years ago by tscrim

Replying to mmarco:

Indeed, it is the value of "bases" what we reuse, but that is a dictionary, and hence mutable. Again, we could have it in a tuple format and convert it to dictionary each time we recover it.

In this case, I would say that is okay because user does not see it (but we should put a big warning to any developers to not mutate nor expose it).

In general, what to compute and cache each time is quite tricky here. Now we are computing all the bases of the chain complexes once and caching it. So if the user just asks for a given height, we compute a lot that we don't need. Anyways, my experience is that the biggest part of the computation is taken by computing the cohomology of the complexes, so it is not so bad.

It is probably worthwhile to see what %prun tells us.

However, John's suggestion of creating a dedicated class for Khovanov homology is probably best because this allows us to (potentially) give it a module structure, have full control over output, better localization of code/caching, and make it more functor-like.

comment:10 Changed 3 years ago by git

  • Commit changed from c3dfb06199943646ad2e06ee6ca2f0ded5321270 to 083ec32d0c198f9b2e301ddd9bb63fd66a08204b

Branch pushed to git repo; I updated commit sha1. New commits:

b4b67a0Added khovanov homology method to Links
45586bfChanges suggestd by reviewer
1de3e86create axiliary cached function
8b9ac7fMerge branch 'u/mmarco/khovanov_homology_of_links' of git://trac.sagemath.org/sage into t/20509/khovanov_homology_of_links
083ec32Solved merge conflict

comment:11 Changed 3 years ago by mmarco

I moved the cached part to a private method, that stores only the different heights, and returns tuples. The (now non cached) public method calls this private method to return dictionaries.

comment:12 Changed 3 years ago by tscrim

  • Branch changed from u/mmarco/khovanov_homology_of_links to public/knot_theory/khovanov_homology_of_links-20509
  • Commit changed from 083ec32d0c198f9b2e301ddd9bb63fd66a08204b to 8f73dc43de8c1fdbbb760724658654a642351350
  • Reviewers set to Travis Scrimshaw

I did some fixes, simplifications, and cleanup. I think this will work for now, unless you think we should spend a little time now to create a class for the Khovanov homology (mainly a question to John)? Otherwise, if you are okay with my changes, then you can set a positive review.


New commits:

8f73dc4Some reviewer changes and small cleanup.

comment:13 Changed 3 years ago by jhpalmieri

I don't have strong feelings about a separate class for the homology. I was just suggesting it as an option to give control over the output while allowing caching for the results. So I think it can wait.

comment:14 Changed 3 years ago by mmarco

Thanks for the cleanup. I am ok with the changes.

comment:15 Changed 3 years ago by mmarco

  • Status changed from needs_review to positive_review

comment:16 Changed 3 years ago by vbraun

  • Branch changed from public/knot_theory/khovanov_homology_of_links-20509 to 8f73dc43de8c1fdbbb760724658654a642351350
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.