Opened 3 years ago
Closed 3 years ago
#20509 closed enhancement (fixed)
khovanov homology of links
Reported by:  mmarco  Owned by:  

Priority:  major  Milestone:  sage7.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 )
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
 Branch set to u/mmarco/khovanov_homology_of_links
comment:2 Changed 3 years ago by
 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
comment:3 Changed 3 years ago by
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
, useisinstance(_, tuple)
.  Instead of
you can do
difs = [_ for _ in range(len(V1[0])) if V1[0][_] != V2[0][_] ]
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
 Commit changed from ea937a9e5f263eecdfe9ca32272cbb07a00d582f to c3dfb06199943646ad2e06ee6ca2f0ded5321270
Branch pushed to git repo; I updated commit sha1. New commits:
c3dfb06  Changes suggestd by reviewer

comment:5 Changed 3 years ago by
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 viceversa: 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
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 bydegree basis (perhaps also taking the height
as input. Thus we can make the userlevel 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 followup: ↓ 9 Changed 3 years ago by
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
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
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 functorlike.
comment:10 Changed 3 years ago by
 Commit changed from c3dfb06199943646ad2e06ee6ca2f0ded5321270 to 083ec32d0c198f9b2e301ddd9bb63fd66a08204b
Branch pushed to git repo; I updated commit sha1. New commits:
b4b67a0  Added khovanov homology method to Links

45586bf  Changes suggestd by reviewer

1de3e86  create axiliary cached function

8b9ac7f  Merge branch 'u/mmarco/khovanov_homology_of_links' of git://trac.sagemath.org/sage into t/20509/khovanov_homology_of_links

083ec32  Solved merge conflict

comment:11 Changed 3 years ago by
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
 Branch changed from u/mmarco/khovanov_homology_of_links to public/knot_theory/khovanov_homology_of_links20509
 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:
8f73dc4  Some reviewer changes and small cleanup.

comment:13 Changed 3 years ago by
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
Thanks for the cleanup. I am ok with the changes.
comment:15 Changed 3 years ago by
 Status changed from needs_review to positive_review
comment:16 Changed 3 years ago by
 Branch changed from public/knot_theory/khovanov_homology_of_links20509 to 8f73dc43de8c1fdbbb760724658654a642351350
 Resolution set to fixed
 Status changed from positive_review to closed
New commits:
Added khovanov homology method to Links