Implement the Links-Gould polynomial invariant for links

[soehms]

At the moment there doesn't seem to be any public available calculator for this invariant. We will implement it straight forward according to the definition given in A CUBIC DEFINING ALGEBRA FOR THE LINKS-GOULD POLYNOMIAL by Marin and Wagner, section 3. Calculations are done on sparse matrices over a univariate quotient polynomial ring over a two variate Laurent polynomial ring since the square-roots of a non monomial polynomial are involved. This is just necessary for the calculation. The result simplifies to a proper two variate Laurent polynomial. As the dimension of these matrices are given by 4^num_strands the performance slows down accordingly.

In a second step we could try to figure out if the approach followed in a 2013 paper of David de Witt respective a 2019 paper of Cristina Ana-Maria Anghel would improve performance.

Some examples: On an i7 CPU the calculation for three strand braids need less than a second. For four strand braids it takes between two and six seconds whereas for five strand braids between one and two minutes are needed. For example K8_1 takes one and a half minute. Braids with six strands need more than than 20 minutes (for example K10_1 22 minutes).

Component: algebraic topology

Keywords: Links-Gould polynomial knots links

Author: Sebastian Oehms

Branch/Commit: 08e3bfe

Reviewer: Travis Scrimshaw

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

[soehms]

Branch: u/soehms/links_gould_poly_33798

[soehms]

Commit: 73412bf

[soehms]

Author: Sebastian Oehms

[soehms]

New commits:

73412bf

33798: initial version

[sagetrac-git]

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

0ab620c

Merge branch 'u/soehms/links_gould_poly_33798' of trac.sagemath.org:sage into links_gould_poly_33798

[sagetrac-git]

Changed commit from 73412bf to 0ab620c

[soehms]

comment:4

I just fixed a merge conflict.

[tscrim]

comment:5

Since everything only involves square roots of the variables, wouldn't it be better to replace t_i with t_i^2? That way you can do everything in polynomial rings, which should be much faster. Afterwards you could then substitute back.

[soehms]

comment:6

Replying to @tscrim:

Since everything only involves square roots of the variables, wouldn't it be better to replace t_i with t_i^2? That way you can do everything in polynomial rings, which should be much faster. Afterwards you could then substitute back.

Maybe I don't understand your idea exactly. I've tried to use a quotient ring over a three variate polynomial ring the third variable of which corresponding to the term abbreviated Y in Ivan Marin's paper. At the moment I don't have access to my notes about that, since I'm on vacation. But this was even slower than using the symbolic ring.

[tscrim]

comment:7

Replying to @soehms:

Replying to @tscrim:

Since everything only involves square roots of the variables, wouldn't it be better to replace t_i with t_i^2? That way you can do everything in polynomial rings, which should be much faster. Afterwards you could then substitute back.

Maybe I don't understand your idea exactly. I've tried to use a quotient ring over a three variate polynomial ring the third variable of which corresponding to the term abbreviated Y in Ivan Marin's paper.

I am not suggesting that. In the description, you say you use SR since for the Laurent polynomial ring variables "x,y", you use x^1/2 and y^1/2 in the computations. I am just saying use the variables t₀ = x^1/2 and t₁ = y^1/2 for the computations to avoid SR. Then in the final computation, you just rescale all of the exponents by 1/2 since the result is a polynomial. Although we could just output with the squared variables with a .. WARNING:: indicating the change in convention.

At the moment I don't have access to my notes about that, since I'm on vacation. But this was even slower than using the symbolic ring.

No problem. Enjoy your vacation.

I would have the internal cached method use fixed variable names and then do a substitution for different user input to not redo the computation just because the variable names change.

Also, typo: beeing.

[soehms]

comment:8

Replying to @tscrim:

Replying to @soehms:

Replying to @tscrim:

Since everything only involves square roots of the variables, wouldn't it be better to replace t_i with t_i^2? That way you can do everything in polynomial rings, which should be much faster. Afterwards you could then substitute back.

Maybe I don't understand your idea exactly. I've tried to use a quotient ring over a three variate polynomial ring the third variable of which corresponding to the term abbreviated Y in Ivan Marin's paper.

I am not suggesting that. In the description, you say you use SR since for the Laurent polynomial ring variables "x,y", you use x^1/2 and y^1/2 in the computations. I am just saying use the variables t₀ = x^1/2 and t₁ = y^1/2 for the computations to avoid SR. Then in the final computation, you just rescale all of the exponents by 1/2 since the result is a polynomial. Although we could just output with the squared variables with a .. WARNING:: indicating the change in convention.

It's not just squares of the variables, there are also squares of non monomial Laurent polynomials (see the Y). Apparently it's a non-trivial fact that the result always simplifies to Laurent polynomials.

Anyway, I will think about this once again, when I'm back home. Thanks for looking at the ticket!

[sagetrac-git]

Changed commit from 0ab620c to 18bbfda

[sagetrac-git]

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

7785b48	Merge branch 'u/soehms/links_gould_poly_33798' of trac.sagemath.org:sage into links_gould_poly_33798
18bbfda	33798: use quotient ring of Laurent polynomials

[soehms]

comment:10

Travis, you are right! Indeed, the quotient ring leads to a faster implementation. It seems that I didn't use sparse matrices for this ring in my former tests (note that for symbolics there is no proper sparse implementation and thus dense matrices perform better in this setting).

Nevertheless I keep the usage of the symbolic ring as a second implementation option, since it might be useful for cross checks and verifications.

[tscrim]

comment:11

Sorry for taking so long to get to this.

I am glad you were able to speed it up. How does it compare to doing computations in

            LC = LaurentPolynomialRing(ZZ, 's0r, s1r')
            s0r, s1r = LC.gens()
            LR = PolynomialRing(LC 'Yr')
            Yr = LR.gen()
            pqr = Yr**2 + (s0r**2-1)*(s1r**2 -1)

This way it is the quotient ring of a univariate polynomial ring. I would think working with quotients there would be faster since the data type is more simple.

Also, I would have

def links_gould_polynomial(self, varnames=None, use_symbolics=False):
    if varnames is not None:
         poly = links_gould_polynomial(use_symbolics=use_symbolics)
         R = PolynomialRing(ZZ, varnames)
         t0, t1 = R.gens()
         return poly(t0=t0, t1=t1)
    varnames = 't0, t1'

to not do the full computation again when only the variable names have changed.

[sagetrac-git]

Changed commit from 18bbfda to 08e3bfe

[sagetrac-git]

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

ed115d5	Merge branch 'u/soehms/links_gould_poly_33798' of trac.sagemath.org:sage into links_gould_poly_33798
08e3bfe	33798: improving performance once more

[soehms]

comment:13

Replying to @tscrim:

Sorry for taking so long to get to this.

No problem!

I am glad you were able to speed it up. How does it compare to doing computations in

            LC = LaurentPolynomialRing(ZZ, 's0r, s1r')
            s0r, s1r = LC.gens()
            LR = PolynomialRing(LC 'Yr')
            Yr = LR.gen()
            pqr = Yr**2 + (s0r**2-1)*(s1r**2 -1)

This way it is the quotient ring of a univariate polynomial ring. I would think working with quotients there would be faster since the data type is more simple.

Many thanks for this useful suggestion. Once again, I could achieve a remarkable improvement of performance with it. The calculation for knot K10_1 which didn't terminate using symbolics within a day, now needs 22 minutes. With the former quotient ring version it has been 4 hours.

Furthermore, I now could successfully run a crosscheck over all links listed in the KnotInfo and LinkInfo databases having less than 5 strands (3342 in sum) against the according specialization of the formal Markov trace on the cubic Hecke algebra (see method formal_markov_trace of class CubicHeckeElement in ticket #29717) in less than 5.5 hours.

Also, I would have

def links_gould_polynomial(self, varnames=None, use_symbolics=False):
    if varnames is not None:
         poly = links_gould_polynomial(use_symbolics=use_symbolics)
         R = PolynomialRing(ZZ, varnames)
         t0, t1 = R.gens()
         return poly(t0=t0, t1=t1)
    varnames = 't0, t1'

to not do the full computation again when only the variable names have changed.

This is done now, as well!

BTW: You may have asked why I wrote (R1*R2*R1 - R2*R1*R2).is_zero()) before. The reason was that comparison in quotient rings over multivariate Laurent polynomial rings doesn't work. I will open a corresponding ticket about that, soon.

[tscrim]

comment:15

Thank you. I am glad it was useful. LGTM.

[tscrim]

Reviewer: Travis Scrimshaw

[soehms]

comment:16

Replying to @tscrim:

Thank you. I am glad it was useful. LGTM.

I'm also glad. Thank you, too!

[vbraun]

Changed branch from u/soehms/links_gould_poly_33798 to 08e3bfe