A parallel algorithm for the computation of the Jones polynomial

Kasturi Barkataki, Eleni Panagiotou · 2025

Read A parallel algorithm for the computation of the Jones polynomial by Kasturi Barkataki, Eleni Panagiotou (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-23101.txt.

Introduction

Kasturi Barkataki and Eleni Panagiotou wrote the first parallel computer algorithm for exactly computing the Jones polynomial, a famous fingerprint used to tell knots apart. Knots and tangles appear in biology and engineering, but scoring their complexity is notoriously hard: the standard computation grows exponentially with the number of crossings in a diagram. Splitting the work across many processors was the missing piece.

Their method divides the calculation so each added processor cuts the running time by a further exponential factor. They demonstrate it on classic knots and on tangles of polymer chains taken from molecular simulations. Because the approach is general, it should extend to other knot measures used on large experimental and AI-generated datasets.

Catalog record

CREATORKasturi Barkataki, Eleni Panagiotou
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE48 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-23101

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A parallel algorithm for the computation of the Jones polynomial Kasturi Barkataki, Eleni Panagiotou Abstract Knots, links and entangled filaments appear in many physical systems of interest in biology and engineering. Classifying knots and measuring entanglement is of interest both for advancing knot theory, as well as for analyzing large data that become available through experiments or Artificial Intelligence. In this context, the efficient computation of topological invariants and other metrics of entanglement becomes an urgent issue. The computation of common measures of topological complexity, such as the Jones polynomial, is #P-hard and of exponential time on the number of crossings in a knot(oid) (link(oid)) diagram. In this paper, we introduce the first parallel algorithm for the exact computation of the Jones polynomial for (collections of) both open and closed simple curves in 3-space. This algorithm enables the reduction of the computational time by an exponential factor depending on the number of processors. We demonstrate the advantage of this algorithm by applying it to knots, as well as to systems of linear polymers in a melt obtained from molecular dynamics simulations. The method is general and could be applied to other invariants and measures of complexity. Keywords : Parallel Algorithm, Jones Polynomial, Knots, Linkoids, Divide and Conquer 1 Introduction A significant challenge in knot theory and its applications is the computation of topological invariants, which are measures that can rigorously classify them. Quantifying complexity of systems of entangled, knotted or linked, filaments is of interest also in biology and engineering. As modeling and experiments lead to the accumulation of large data, concerning for example, proteins, understanding the role of entanglement in these systems requires extensive capabilities of computation of knot and link invariants. In this paper, we introduce the first parallel algorithm for computing the Jones polynomial of knots/knotoids/linkoids and open curves in 3-space. The Jones polynomial, an important knot invariant ( [ 35 , 36 ] ), is known to be #P-hard and it is of exponential time on the number of crossings of a knot diagram ( [ 33 ] ). For special types of knot diagrams, such as torus knots, algebraic links, pretzel links, 2-bridge links, link diagrams with bounded treewidth, 3-braid links and Montesinos links, there are various efficient classical algorithms for evaluating the Jones polynomial ( [ 20 , 32 , 44 , 34 , 47 , 49 , 57 ] ). Even though important for our understanding of knots, these remain special cases of knots and, in practice, such cases may have very low probability of occurrence. Knots and entangled filamentous matter, ranging from textiles to (bio)polymers, appear in our everyday life and their topological complexity is intricately related to their mechanics and function ( [ 4 , 23 , 43 , 52 , 53 , 55 , 54 , 10 ] ). Physical systems of interest, such as models of polymer melts, DNA or collections of biopolymers in nature, correspond to link(oid) diagrams of the order of at least \approx 10K crossings. Similarly, random knots are highly unlikely to result in special type of diagrams that can be treated with the above methods ( [ 13 , 14 , 58 , 16 , 19 , 31 , 46 ] . In [ 11 ] , an algorithm for computing the HOMFLY-PT polynomial of arbitrary links was introduced using a fixed-parameter tractable approach, based on the treewidth of the graph associated with a given link diagram, and this was implemented in practice in the topological software package Regina ( [ 12 ] ). Specifically, the algorithm achieves a sub-exponential runtime of e^{\mathcal{O}(\sqrt{n}\log n)} for an arbitrary link diagram with n crossings. This result uses the fact that the graph associated with an n -crossing link diagram is planar, with a treewidth bound of at most \mathcal{O}(\sqrt{n}) . Algorithms based on the number of strands, c , of braid representations of arbitrary links were proposed and implemented in [ 48 ] through connections to Hecke algebras and quantum groups. The cost of such strand based algorithms scales as \mathcal{O}(2^{c}) in memory and \mathcal{O}(4^{c}) in time. Quantum algorithms for approximating the Jones polynomial have been introduced at specific values (roots of unity) that are polynomial in time ( [ 3 , 2 ] ). Recent advances in quantum computing have led to the successful implementation of the algorithm in [ 3 ] , for approximating the Jones polynomial of knot diagrams of up to 104 crossings ( [ 41 , 15 ] ). An approach that has not been thoroughly explored is that of parallel algorithms for the exact computation of the Jones polynomial. An underlying difficulty in reducing the computational time of the Jones polynomial for a general diagram, which also applies to other invariants, is that the skein relation associated with the bracket polynomial expansion acts recursively at its crossings, giving an exponential cost depending on the number of crossings in a diagram. Ideally, the computational time of the Jones polynomial could be reduced by subdivision of a diagram to allow for a divide and conquer method, to apply state sum expansion computations independently on each subdivided piece, as it was proposed in [ 5 ] for faster serial computation of the Khovanov homology of a knot. However, the last step then would require reassembly, which can be as expensive as the computation of the invariant for the entire knot diagram itself. In the algorithm for the Khovanov homology in [ 5 ] , a method to reduce the computation time of the reassembly step was discussed by simplifying the output of each partial computation, based on decomposing Khovanov complexes into smaller subcomplexes to which delooping and Gaussian elimination tools were applied. In [ 24 ] , bounds on the cutwidth of a planar graph are used to to prove that, given a cutwidth realization of a graph, the Kauffman bracket of a link with n crossings can be computed in time, \mathcal{O}(\operatorname{poly}(n)2^{C\sqrt{n}}) where, C=6\sqrt{2}+5\sqrt{3} . However, finding an optimal cutwidth layout for a general graph is NP-hard, though, polynomial-time approximation algorithms exist, with the best known achieving an approximation ratio of \mathcal{O}((\log n)^{3/2}) . In this paper, we introduce a parallel algorithm for the computation of the Jones polynomial and a parallel implementation of it which employs the divide and conquer approach and exploits a novel, simple expression of reassembly based on the formalism introduced in [ 6 , 8 ] for linkoids. Moreover, the algorithm enables the exact computation of the Jones polynomial not only for knots, but also for knot(oid)s/link(oid)s and (collections of) open curves in 3-space which may be equally, or more important for applications to entangled physical systems. More precisely, in this paper, a parallel algorithm for the computation of the Jones polynomial is introduced by subdividing a diagram a knot(oid)/link(oid) diagram into smaller pieces. The smaller pieces are linkoids (open arc diagrams that are not necessarily tangles), which can be classified separately ( [ 56 , 6 , 9 , 8 ] ) and the resulting states from the state-sum expansion of such linkoids are grouped based on distinct permutations of the endpoints. By decomposing a knot into its constituent linkoid pieces and applying state sum expansions, computations

Read the complete text