Low Dimensional Topology

October 13, 2013

A noteworthy knot simplification algorithm

Filed under: Computation and experiment,Knot theory — dmoskovich @ 8:26 am

This post concerns an intriguing undergraduate research project in computer engineering:

Lewin, D., Gan O., Bruckstein A.M.,
TRIVIAL OR KNOT: A SOFTWARE TOOL AND ALGORITHMS FOR KNOT SIMPLIFICATION,
CIS Report No 9605, Technion, IIT, Haifa, 1996.

A curious aspect of the history of low dimensional topology are that it involves several people who started their mathematical life solving problems relating to knots and links, and then went on to become famous for something entirely different. The 2005 Nobel Prize winner in Economics, Robert Aumann, whose game theory course I had the honour to attend as an undergrad, might be the most famous example. In his 1956 PhD thesis, he proved asphericity of alternating knots, and that the Seifert surface is an essential surface which separates alternating knot complements into two components the closures of both of which are handlebodies.

Daniel Lewin is another remarkable individual who started out in knot theory. His topological work is less famous than Aumann’s, and he was murdered at the age of 31 which gives his various achievements less time to have been celebrated; but he was a remarkable individual, and his low dimensional topology work deserves to be much better known.

Before discussing his low dimensional topology, let me tell you a little bit about Daniel Lewin’s life, which you can read more about in this book. Daniel came from Colorado to Israel, where he joined the army and became a captain in Sayeret Matkal, which is Israel’s most famous commando unit (“Who dares wins!”). He then married and entered university to study computer engineering. As an undergrad at the Technion, he and his wife were dirt poor, and he had to work part-time at IBM to make ends meet. While supporting a family, working, and studying (incredible!), he wrote an undergraduate research project together with Orly Gan, under the tutelage of Alfred Bruckstein, on knot theory. Alfred “Freddy” Bruckstein is currenlty at NTU where I am, and it was from him that I learnt of this remarkable project. With it, Daniel Lewin won the Outstanding Student in Computer Engineering in 1995 (remember, in poverty, while supporting a family and working part-time!), and was able to get into MIT.

At MIT, Daniel Lewin and his advisor F. Thomson Leighton solved a problem on how to direct traffic through an overloaded internet. Leaving academia behind (at least temporarily), they opened a company called Akamai and became billionaires. Daniel Lewin was on American Airlines Flight 11 when it was hijacked, and had his throat slit while attempting to stop the hikackers. As a captain in the Sayeret, he would have responded (“who dares wins”, remember?)… and had he succeeded, which I think certainly might have been, then the plane would never have crashed into the North Tower of the World Trade Center, and perhaps 9-11 and all that came after it might never have happened the way that it did.

So what did Danny Lewin do? The main problem in knot theory is knot classification, whose core is knot recognition. Given two hopelessly complicated tangled pieces of rope with their ends fused together, do they or do they not represent the same topological knot? One way to answer this question would be to find an efficient algorithm to simplify both knots as much as possible, until they both end up in some minimum energy state and `look the same’. This is something that knot theorists care very much about, and there are a number of approaches available:

  1. Moebius energy is an knot energy (a functional on the space of knots in 3-space) which is particularly well-behaved. One may model the knot by a ball-and-stick model in 3-space, place simulated `electric charges’ on the balls, and allow the configuration to find its minimal energy state. This leads to pretty and symmetrical knot embeddings. John Sullivan made a very nice computer algorithm along these lines, exhibited in this video. Thanks to Ian Agol for hosting it and for mp4 conversion!
  2. Approaches using Pachner moves on triangulations. Pachner moves are combinatorial moves between triangulations, in this case of knot complements. Experimentally, these techniques can be highly effective, as exhibited in this paper by Ben Burton.
  3. Dynnikov’s algorithm, which involves presenting the knot as a diagram on a `3-page book’, i.e. as a diagram on a collection of 3 half-planes meeting along a line. The knot diagram is then simplified using combinatorial moves. Book Knot Simplifier is a software package by Maria Andreeva, Ivan Dynnikov, Sergey Koval, Konrad Polthier, and Iskander Taimanov which uses this approach. At the moment, as far as I can see, this seems to be the state of the art.
  4. The approach that Lewin, Gan, and Bruckstein take, based on the Dowker notation.

Lewin, Gan, and Bruckstein, being computer engineers and therefore unfettered by topological preconceptions, take a very interesting approach to the problem which from their perspective is very natural, and is quite direct. First, they present the knot using a modified Dowker notation, which is compact and easy to work with. Then, they simplify the modified Dowker notation using Reidemeister moves. How exactly do they do this? Why don’t they hit global minima? Here is where the skills of an engineer come into their own. The solution chosen by Lewin, Gan, and Bruckstein is to apply a simulated annealing algorithm.

Note that this is not the first time simulated annealing was used to simplify knots- there is a knot energy approach using simulated annealing due to Ligocki and Sethian. That approach suffers from some convergence issues because the knot is 3-dimensional and there are too many variables. A modification of this technique by Ladd and Kavlaki (robotics people!) using a stick presentation of knots in 3-space instead, and seems to give very nice results.

Simulated annealing is a probabilistic technique to find a global optimum for a function. Wikipedia says:

The name and inspiration come from annealing in metallurgy, a technique involving heating and controlled cooling of a material to increase the size of its crystals and reduce their defects, both are attributes of the material that depend on its thermodynamic free energy. Heating and cooling the material affects both the temperature and the thermodynamic free energy. While the same amount of cooling brings the same amount of decrease in temperature it will bring a bigger or smaller decrease in the thermodynamic free energy depending on the rate that it occurs, with a slower rate producing a bigger decrease.

In our case, the goal is to find the modified Dowker presentation with the fewest crossing, and the one that is `most alternating’ (by one of the Tait conjectures, which have been proven, an alternating knot diagram is minimal, and so finding one solves the recognition problem). The type of simulated annealing that they use is called Bolzmann annealing. The knot is `cooled’, performing Reidemeister moves at random locations. If we get a lower energy diagram, go to that. Otherwise, accept it with a probability of \left(1+e^{\frac{\Delta E}{kT}}\right)^{-1}, or else stay put. So there are more jumps for higher temperatures, and the lower the temperature the energy the less probability there is of a jump. Lower the temperature, and repeat.

This is an undergraduate research project, and no theorems are proven. The algorithm, and even its application to knot theory, are not new. But using it on modified Dowker codes is certainly new. Experimentally, the algorithm appears to work extremely well. It’s extremely simple and robust, and entirely probabilistic, so it would work on huge knots as well as on small knots. Moreover, it’s massively flexible- it would work just as well for links, braids, tangles, virtual tangles, welded tangled objects, or just-about anything else. In particular, it works for tangle machines (while none of the other techniques do), which is why I’m particularly interested in it. I believe that it absolutely deserves to be much better known.

I wonder how close it is to being state-of-the-art even today- I asked a MathOverflow question about this, from which much of the information in this post is taken. As a random and irresponsible thought, wouldn’t it be interesting to have a software implementation challenge to see which algorithm could most rapidly simplify some arbitrary very complicated knot diagram with hundreds or even thousands of crossings? My money is on Lewin-Gan-Bruckstein.

About these ads

5 Comments »

  1. A more classical 5th approach would be to start with the diagram, compute a presentation for the fundamental group of the complement, and try to simplify it to a presentation with no relators, using a variant of small cancellation theory. i.e. try to kill generators using relators, and shortening relators. If you get stuck, multiply relators together in various ways to try to find new useful relators. I suspect this can be very effective if implemented moderately intelligently.

    Comment by Ryan Budney — October 13, 2013 @ 8:35 am | Reply

    • This sounds like a very good idea! There would be a probabilistic approach, and a deterministic approach, here too.

      Comment by dmoskovich — October 13, 2013 @ 8:48 am | Reply

  2. Those of you interested in recognizing unknots, or the 3-sphere, or who are interested in simplifying general 3-manifold presentations might want to try a new version of Heegaard. (Eventually this may be posted on the website of Marc Culler and Nathan Dunfield.)

    Heegaard accepts geometric presentations on up to 26 generators and 32 relators. So for knots, Wirtinger presentations, or geometric presentations obtained using over-crossing and under-crossing arcs will work provided the 26 generator restriction is satisfied.

    In practice, Heegaard determines each of the following examples is unknotted in only a few seconds.

    Thistlethwaite’s Unknot from Wikipedia, Culprit from Kaufmann-Lambropoulou, Fig5 from Kaufmann-Lambropoulou, H) from Henrich & Kauffman, J) from Henrich & Kauffman, G) Goeritz’s unknot, Ochiai’s unknot 1 from “Non-trivial projections of the trivial knot” URL http://hdl.handlenet/2433/99940, Ochiai’s unknot 2 from the same paper, and Freedman’s Twisted Unknot.

    Those wishing to check such things for themselves can obtain a current copy of Heegaard from me by email request to jberge at charter ‘dot’ net.

    Note Heegaard is a Unix executable, which runs under terminal on an apple macintosh. So you will probably need a mac.

    Comment by John Berge — October 15, 2013 @ 4:37 am | Reply

  3. Reblogged this on citedcorpse and commented:
    This is a fascinating story, in any case.

    Comment by citedcorpse — October 21, 2013 @ 2:19 pm | Reply


RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

The Rubric Theme. Create a free website or blog at WordPress.com.

Follow

Get every new post delivered to your Inbox.

Join 227 other followers

%d bloggers like this: