What is the state of the art for algorithmic knot simplification? 
Question: Given a `hard' diagram of a knot, with over a hundred crossings, what is the best algorithm and software tool to simplify it? Will it also simplify virtual knot diagrams, tangle diagrams, and link diagrams?

The reason that I ask this question is that I have been reading:
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.
This technical report is notable not only for its mathematical content, but also for its back-story. It was the undergraduate research project of Daniel M. Lewin, who was a few years later to found Akamai Technology which today manages 15-20% of the world's web traffic, to become a billionaire, and to be the first person to be murdered on 9-11. He is the subject of the 2013 biography No Better Time: The Brief, Remarkable Life of Danny Lewin, the Genius Who Transformed the Internet by Molly Knight Raskin, published by Da Capo Press.
The algorithm used by Bruckstein, Lewin, and Gan doesn't use 3-dimensional topology or normal surface theory, but instead relies on an algorithmic technique called simulated annealing. I suspect that this same technique could be used effectively for other problems in algorithmic topology. 
To the best of my knowledge, Bruckstein, Lewin, and Gan's algorithm is unknown to the low-dimensional topology community, but it works very well. Despite it having been written a long time ago, I wonder (for reasons beyond mere curiousity) how far it is from being state of the art today.
 A: Here is one piece of software, the Book Knot Simplifier,
by
Maria Andreeva, Ivan Dynnikov, Sergey Koval, Konrad Polthier, and Iskander Taimanov,
largely based on Dynnikov's work:

Here we offer a set of tools for manipulating knots and links in the three-space by using the three-page presentation of links, which was proposed and developed by I. Dynnikov in [1][2][3].
The approach is based on a simple and very well known observation that every link in the three-space is topologically equivalent to a link that lies entirely in a three-page book, i.e. the union of three half-planes with common boundary. Though being not convenient for human perception, this way of presenting links seems to be very efficient for handling knots by computer. It provides a very quick way from a combinatorial description of a link to its three-dimensional presentation. A three-page link admits a lot of transformations that preserve its isotopy class and can be easily found. This fact is used in the knot simplifying tool included herein.


        The unknot with 31 crossings.
A: Ben Burton has a paper where he experimentally does Pachner moves to simplify unknot complements.  It appears to be very effective. https://arxiv.org/abs/1211.1079
I'd type more but my phone is a little awkward.  But you could view this as a coarse type of simulated annealing.
A: A little Heegaard promotion.
Those of you interested in recognizing unknots, or the 3-sphere, or who are interested in simplifying general geometric 3-manifold presentations might want to try a new version of Heegaard. (Which may eventually replace the original outdated version posted on the website of Marc Culler and Nathan Dunfield at www.math.uic.edu/t3m.)
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.
For example, Heegaard easily 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.
While the approach Heegaard uses isn't sexy, it does seem to work quite---perhaps unreasonably---well.
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. Though Ryan Budney has it running under linux.
