Add colored Jones polynomial

mo271 commented 2 years ago

This a proposal to add a new method in braid.py to allow the calculation of the colored Jones polynomial. Following https://arxiv.org/abs/1804.07910

Depends on #32629

CC: @miguelmarco @NathanDunfield

Component: group theory

Keywords: knots, braids

Author: Moritz Firsching

Branch: d2722d0

Reviewer: Travis Scrimshaw

Issue created by migration from https://trac.sagemath.org/ticket/32582

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 2 years ago

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

5e2390d remove walrus

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 2 years ago

Changed commit from 58efda8 to 5e2390d

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 2 years ago

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

d2be8cb use q_inv instead of q for clarity

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 2 years ago

Changed commit from 5e2390d to d2be8cb

fchapoton commented 2 years ago

comment:4

please check indentation in the doc. doctests inside EXAMPLES:: must be indented

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 2 years ago

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

17a1a7c add indentation for EXAMPLES

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 2 years ago

Changed commit from d2be8cb to 17a1a7c

mo271 commented 2 years ago

comment:6

Thanks for pointing that out and taking a look, chapoton! I tried to fix it in all places..

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 2 years ago

Changed commit from 17a1a7c to 2e538a8

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 2 years ago

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

2e538a8 remove unused index

tscrim commented 2 years ago

Reviewer: Travis Scrimshaw

tscrim commented 2 years ago

comment:10

Thank you for this implementation. I have a few comments/questions.

Why should _RightQuantumWord be internal? It seems like it would be okay as a separate class (in the braid.py file).

Why is _deformed_burau_matrix hidden? It seems like it would be useful for other people using the braid group class.

I think _quantum_determinant should not be in braid.py, much less as a method of the braid group elements. The question then becomes where is a good home for this function. I am thinking it is best as a method on matrices. You should also add in the definition to the docstring and make it unhidden.

While it is unlikely, I don't think we should have the caching of colored_jones_polynomial depend on the variable and try_inverse. The cached version would have a fixed choice of variable, such as q. Probably the better thing to do here is to manually handle the cache with an attribute, e.g., self._colored_jones_poly. The other option is to have the cached part be a separate hidden method (and @cached_method can take a key function, where we can ignore the try_inverse input).

I am not a big fan of the for loop in _colored_jones_sum. While there might be some code duplication, having it as a while loop makes it easier to understand the logic IMO (which can be seen as you won't need the comment).

You have numerous formatting errors with your documentation. Please see the Sage dev guide: docstrings and the other code in braid.py. Let me know if you have any questions.

mo271 commented 2 years ago

comment:11

Replying to @tscrim:

Thank you for this implementation. I have a few comments/questions.

Thanks for taking a look and the comments!

Why should _RightQuantumWord be internal? It seems like it would be okay as a separate class (in the braid.py file).

Why is _deformed_burau_matrix hidden? It seems like it would be useful for other people using the braid group class.

Both for _RightQuantumWord and the _deformed_burau_matrix, I couldn't image that they would be used in any other context than in calculating the colored Jones, but why not, let's expose those, there might be some other uses.

I think _quantum_determinant should not be in braid.py, much less as a method of the braid group elements. The question then becomes where is a good home for this function. I am thinking it is best as a method on matrices. You should also add in the definition to the docstring and make it unhidden.

Looking around where to put this, I found a quantum_determinant method of QuantumMatrixCoordinate.

sage: O = algebras.QuantumMatrixCoordinate(3)                                                                                                                                                                                                                                                                                                                                                                                           
sage: O.quantum_determinant()                                                                                                                                                                                                                                                                                                                                                                                                           
x[1,1]*x[2,2]*x[3,3] - q*x[1,1]*x[2,3]*x[3,2] - q*x[1,2]*x[2,1]*x[3,3] + q^2*x[1,2]*x[2,3]*x[3,1] + q^2*x[1,3]*x[2,1]*x[3,2] - q^3*x[1,3]*x[2,2]*x[3,1]

However this is in its current form not useful for our purposes, since it cannot be accessed without creating the an instance of QuantumMatrixCoordinate and this is slow. It is also broken if one changes 3 to 11, #32623. Perhaps it would be best to have a quantum_determinant method somewhere where both our code in braid.py as well as QuantumMatrixCoordinate can access it. If you agree I would prepare a separate ticket to add quantum_determinant.

While it is unlikely, I don't think we should have the caching of colored_jones_polynomial depend on the variable and try_inverse. The cached version would have a fixed choice of variable, such as q. Probably the better thing to do here is to manually handle the cache with an attribute, e.g., self._colored_jones_poly. The other option is to have the cached part be a separate hidden method (and @cached_method can take a key function, where we can ignore the try_inverse input).

Make sense, I will cache it in an attribute.

I am not a big fan of the for loop in _colored_jones_sum. While there might be some code duplication, having it as a while loop makes it easier to understand the logic IMO (which can be seen as you won't need the comment).

Sure, will change to a while loop.

You have numerous formatting errors with your documentation. Please see the Sage dev guide: docstrings and the other code in braid.py. Let me know if you have any questions.

I will take another look at those...

tscrim commented 2 years ago

comment:12

I have fixed #32623, along with a speedup for the qdet. From a little bit of testing, it seems like they are approximately the same speed as they are the same algorithm. I agree that this should not use the quantum matrix coordinate ring as that is meant for that class specifically. I wouldn't try to refactor that out into a single function. Instead, I would just move the implementation to src/sage/matrix/matrix2.pyx as it is most natural to be a function acting on a matrix.

I would also add a default q:

def quantum_determinant(self, q=None):
    if q is None:
        from sage.rings.polynomial.polynomial_ring_constructor import PolynomialRing
        q = PolynomialRing(self.base_ring(), 'q').gen()
    [rest of code]

This will make it easier to use for a general user.

mo271 commented 2 years ago

Dependencies: #32629

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 2 years ago

Changed commit from 2e538a8 to 062a9e9

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 2 years ago

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

`9793567`	`adding quantum_determinant to matrix`
`b896929`	`Reviewer changes to quantum_determinant.`
`6e95c3a`	`add colored Jones polynomial to braids`
`78919fb`	`remove walrus`
`eb1aab9`	`use q_inv instead of q for clarity`
`535fef1`	`add indentation for EXAMPLES`
`f615252`	`remove unused index`
`062a9e9`	`first round of review comments`

mo271 commented 2 years ago

comment:15

I aimed to address all review comments as outlined in the reply above. After looking into it, I'm now not using an attribute, but cache the function _colored_jones_sum, using always q as a variable first and then substituting if necessary. This seems to work as intended:

sage: b = BraidGroup(5)([1,2,4,2,-4,-2,3,-2,-1,2,3,1,2,4])
sage: %time b.colored_jones_polynomial(2, try_inverse=False)
CPU times: user 2.14 s, sys: 9.22 ms, total: 2.15 s
Wall time: 2.15 s
q - q^2 + 2*q^3 - q^4 + q^5 - q^6
sage: %time b.colored_jones_polynomial(2, try_inverse=False)
CPU times: user 24.6 ms, sys: 33 µs, total: 24.6 ms
Wall time: 24.3 ms
q - q^2 + 2*q^3 - q^4 + q^5 - q^6
sage: %time b.colored_jones_polynomial(2, 'z', try_inverse=False)
CPU times: user 27.2 ms, sys: 263 µs, total: 27.4 ms
Wall time: 26.9 ms
z - z^2 + 2*z^3 - z^4 + z^5 - z^6
sage: %time b.colored_jones_polynomial(2, 'z', try_inverse=True)
CPU times: user 167 ms, sys: 101 ms, total: 268 ms
Wall time: 267 ms
z - z^2 + 2*z^3 - z^4 + z^5 - z^6

We now use the new quantum_determinant. Not sure why lint on github is still failing, I at least made sure that now pep8 errors appear in the code I added. Also, I hope I now got the formatting for the doc strings correct.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 2 years ago

Changed commit from 062a9e9 to ff5b101

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 2 years ago

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

ff5b101 fix doc

tscrim commented 2 years ago

Changed commit from ff5b101 to 01caa0e

tscrim commented 2 years ago

comment:17

Thank you. It is looking very good. I made some additional changes; most are minor tweaks for PEP8 (and breaking the 80 char/line rule when I felt it made things more readable) and documentation. The two biggest changes is I made are (1) the caching is now associated to colored_jones_polynomial so the quantum determinant did not have to be computed multiple times; (2) made RightQuantumWord.to_tuples() into a lazy attribute.

If my changes are good, then you can set a positive review.

New commits:

01caa0e Reviewer changes to colored Jones polynomial.

tscrim commented 2 years ago

Changed branch from u/moritz/colored_jones to public/knots/colored_jones-32582

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 2 years ago

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

f7aee70 Adding colored Jones polynomial to knots.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 2 years ago

Changed commit from 01caa0e to f7aee70

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 2 years ago

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

`d8a2a09`	`Speedup of RightQuantumWord.tuples computation.`
`d1d20f8`	`Further speedup to colored_jones_polynomial().`

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 2 years ago

Changed commit from f7aee70 to d1d20f8

tscrim commented 2 years ago

comment:20

I also was able to get an ~8x speedup by being more careful about where objects live and knowing a bit about the internal workings of FreeAlgebra:

sage: B = BraidGroup(4)
sage: b = B([1,1,1,2,-1,2,-3,2,-3])
sage: %time b.colored_jones_polynomial(2)
CPU times: user 1.4 s, sys: 4 ms, total: 1.4 s
Wall time: 1.4 s
q^-1 - 2 + 4*q - 5*q^2 + 6*q^3 - 5*q^4 + 4*q^5 - 3*q^6 + q^7

Before this took about 12s. I don't see any other obvious way to speed this up further. With this new version, I can now do the N=3 case for the above in a reasonable amount of time:

sage: %time b.colored_jones_polynomial(3)
CPU times: user 34.6 s, sys: 104 ms, total: 34.7 s
Wall time: 34.7 s
q^-4 - 2*q^-3 + 6*q^-1 - 8 - 2*q + 18*q^2 - 17*q^3 - 8*q^4 + 32*q^5 - 22*q^6
 - 15*q^7 + 39*q^8 - 21*q^9 - 18*q^10 + 34*q^11 - 14*q^12 - 16*q^13 + 22*q^14
 - 5*q^15 - 10*q^16 + 9*q^17 - 3*q^19 + q^20

tscrim commented 2 years ago

comment:21

Now I am done (I also made this accessible directly from a knot). Please review my changes.

mo271 commented 2 years ago

comment:22

Wow, nice speedup! All the changes look good to me.

vbraun commented 2 years ago

comment:23

Merge conflict

mo271 commented 2 years ago

Changed branch from public/knots/colored_jones-32582 to u/moritz/colored_jones

mo271 commented 2 years ago

Last 10 new commits:

`c5ca5d0`	`use q_inv instead of q for clarity`
`596a69c`	`add indentation for EXAMPLES`
`1bef72e`	`remove unused index`
`0f7ee6a`	`first round of review comments`
`b8bf213`	`fix doc`
`59ca816`	`Reviewer changes to colored Jones polynomial.`
`c4a84c2`	`Adding colored Jones polynomial to knots.`
`04d9e3a`	`Speedup of RightQuantumWord.tuples computation.`
`b684eef`	`Further speedup to colored_jones_polynomial().`
`8133b59`	`fix q_inv typo`

mo271 commented 2 years ago

Changed commit from d1d20f8 to 8133b59

mo271 commented 2 years ago

comment:25

rebased and fixed all conficts (hopefully)

mo271 commented 2 years ago

comment:26

botched rebase, working on fixing it...

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 2 years ago

Changed commit from 8133b59 to 4567a06

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 2 years ago

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

4567a06 fix botched rebase

tscrim commented 2 years ago

comment:29

It still conflicts. Sometimes the beta release it conflicts with is not released yet when Volker says there is a merge conflict.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 2 years ago

Changed commit from 4567a06 to d2722d0

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 2 years ago

Branch pushed to git repo; I updated commit sha1. This was a forced push. Last 10 new commits:

`bf8a4ff`	`add indentation for EXAMPLES`
`b0b1d8b`	`remove unused index`
`c01f408`	`first round of review comments`
`eca4869`	`fix doc`
`022fcde`	`Reviewer changes to colored Jones polynomial.`
`bac98e5`	`Adding colored Jones polynomial to knots.`
`93cc25e`	`Speedup of RightQuantumWord.tuples computation.`
`2121743`	`Further speedup to colored_jones_polynomial().`
`524906e`	`fix q_inv typo`
`d2722d0`	`fix botched rebase`

mo271 commented 2 years ago

comment:31

ok, rebased on 9.5.beta4, see if that helps...

tscrim commented 2 years ago

comment:32

That should be good. Thank you.

vbraun commented 2 years ago

Changed branch from u/moritz/colored_jones to d2722d0

slel commented 2 years ago

comment:34

In the method eps of the class RightQuantumWord, the auxiliary function eps_monom's docstring should come first:

         def eps_monom(q_tuple):
-            q = self.q
             r"""Evaluate the map $\mathcal{E}_N$ for a single mononial."""
+            q = self.q

For a follow-up ticket if you care enough.

slel commented 2 years ago

Changed commit from d2722d0 to none

tscrim commented 2 years ago

comment:35

I thought I had fixed that, but I missed it. Indeed, that should be fixed (it is likely causing a few lost CPU cycles with Python creating that string on each function call).

tscrim commented 2 years ago

comment:36

Replying to @tscrim:

I thought I had fixed that, but I missed it. Indeed, that should be fixed (it is likely causing a few lost CPU cycles with Python creating that string on each function call).

Fixed in #32829.

sagemath / sage

Add colored Jones polynomial #32582