Ridgerunner: Knot tightening software

Ridgerunner is a program for tightening knots created by Jason Cantarella, Eric Rawdon, and Michael Piatek. The software depends on many of the other programs on this site: unless you’ve already installed plCurve, octrope, and [tsnnls] as well as argtable2, you should use the ‘metapackage’ rrplusdeps below. Installing povray as well as the GNU Scientific Library and Geomview will make your life easier, but they aren’t strictly neccessary.

We used the software to create the tables of tight knots in Knot Tightening By Constrained Gradient Descent and The Shapes of Tight Composite Knots (see Papers) and the movies at Ridgerunner Movies, so it’s fairly battle-tested by now. Actual crashes (segfaults) are quite uncommon, though the software can get to a point where the linear algebra becomes so degenerate that it can go no further. A helpful hint when starting out is to avoid configurations which have a lot of self contact in their starting position, or a lot of symmetry. For instance, a Hopf link formed from two round circles will kill ridgerunner instantly because there are too many initial self-contacts.

The latest data files produced by ridgerunner for tight knots and links are freely available in the subversion repository at http://www.jasoncantarella/TightKnot2. The current best files for knots and links are in the “best” directory.

Brief Introduction

The full list of command-line arguments for ridgerunner is somewhat intimidating. If you just type ridgerunner (after a successful install), you’ll get a lot of possible arguments. Luckily, very few are needed to start tightening some knots. A simple session with ridgerunner looks like this.

jason:ridgerunner> ridgerunner ./data/3.1.vect -a –StopSteps=1000
Ridgerunner 2.0.0
svn version 340:341M
Built Feb 21 2012, 11:00:20.
plCurve Version: 5.0.5
Octrope Version: 1.5
tsnnls Version: 2.3.3
Seeded from dev/random with seed 288502481.
Loaded 1 component, 47 vertex plCurve from ./data/3.1.vect.
Saved copy of ./data/3.1.vect to ./3.1.rr/3.1.vect.
Curve has thickness 1.54794. Scaling to thickness 0.501.
Scaled curve has thickness 0.501.
Autoscale selftest ok.
Rerez’d, autoscaled, eq’d file written to ./3.1.rr/3.1.atstart.vect.
Overstep tolerance: 0.000100 of thickness 0.500000 (0.499950) minminrad: 0.49997500
ridgerunner: Curses screen display disabled, using stdout.
Define CURSES_DISPLAY to enable better screen display.
ridgerunner: Starting run. Will stop if
step number >= 1000
residual < 0
ropelength decrease over last 20 steps < -1000.

1 Rop: 36.68996343890 Str: 0 MRstruts: 0 Thi: 0.5000015
2 Rop: 36.68999769764 Str: 1 MRstruts: 0 Thi: 0.5000000
3 Rop: 36.66687647726 Str: 1 MRstruts: 0 Thi: 0.4999996
4 Rop: 36.66685032902 Str: 2 MRstruts: 0 Thi: 0.4999996
5 Rop: 36.08036840390 Str: 8 MRstruts: 0 Thi: 0.4949835
6 Rop: 36.07859929174 Str: 2 MRstruts: 0 Thi: 0.4999999
7 Rop: 36.00000909104 Str: 3 MRstruts: 0 Thi: 0.4999891

994 Rop: 33.19041815788 Str: 56 MRstruts: 0 Thi: 0.4999897
995 Rop: 33.19041102220 Str: 56 MRstruts: 0 Thi: 0.4999896
996 Rop: 33.19039909288 Str: 56 MRstruts: 0 Thi: 0.4999894
997 Rop: 33.19039412711 Str: 56 MRstruts: 0 Thi: 0.4999894
998 Rop: 33.19008824082 Str: 43 MRstruts: 0 Thi: 0.4999893
999 Rop: 33.19003077760 Str: 53 MRstruts: 0 Thi: 0.4999893
1000 Rop: 33.19001902293 Str: 55 MRstruts: 0 Thi: 0.4999893
ridgerunner: run complete. Terminated because
ridgerunner: reached maximum number of steps (1000).
tube (vecttools 1.1) compiled Feb 21 2012 16:21:05
tube: Wrote 1733 vertex, 3466 face tube.
ridgerunner: Run complete.

We used three options here: -a or autoscale, which scales the knot to thickness 1 before starting the minimization, –StopSteps=1000, which set the number of steps to 1000, and ./data/3.1.vect, which was the name of the input curve. As you can see, this shrinks the trefoil knot in /data (there’s a complete knot table in there for you to play with) by about 3 units of ropelength. The results appear in a subdirectory of wherever you ran ridgerunner from. If you ran knot.vect, the results will be in knot.rr.

jason:ridgerunner> cd 3.1.rr/
jason:3.1.rr> ls
3.1.atstart.vect 3.1.final.tube.off 3.1.log logfiles/ vectfiles/
3.1.final.struts 3.1.final.vect 3.1.vect snapshots/

The results are not particularly dramatic. On the left, we see 3.1.atstart.vect (with a tube around it), which is always a copy of the VECT file that you submitted to ridgerunner, and on the right we see 3.1.final.vect (with a tube around it), which is the final output of ridgerunner (assuming that the run completed normally).

3.1.atstart.tube ->    3.1.final.tube

Still, if you can do this, you can (in principle) do anything in knot tightening.

You can use multiple stopping criteria together. For instance, in production work, we usually used

ridgerunner -a myfile.vect –StopRes=0.01 –StopTime=2880 –StopSteps=500000

which stops when the residual of the file is 0.01 (that is, the elastic force on the knot is 99% balanced by tube contacts), or when two days (2880 minutes) have passed, or when 500,000 steps have been taken, whichever comes first.

Advanced Options

Many of the advanced options are mostly useful for debugging or historical reasons, but several are worth discussing.

-l, –Lambda=<double> minimum radius of curvature for unit rope

If you are studying stiff rope, with radius of curvature bounded below, you can set the minimum radius of curvature of the rope with this option. Note that the rope has diameter 1 in ridgerunner, so the default setting for lambda is 0.5 (fully flexible rope).

–MangleMode instead of trying to reduce length, try to change configuration
–MangleSteps=<#steps> switch mangling algorithm after this many steps

This is still experimental, but is currently useful enough to document. MangleMode will not try to shrink the knot, but instead turns it inside out by flowing around a randomly selected torus whose center is near the center of mass of the polygon. This is often very effective in finding different local minima for a given knot type.

–EqOn automatically equilateralizes when max/min edge > 3
–EqMultiplier=<scalar> increase to make ‘equilateralization force’ stronger
–EqForceOn turn on equilateralization force during the run (can interfere with stepper)

One of these options should always be chosen during a long run. The difference between them is that EqForceOn will attempt to maintain a perfectly equilateral polygon during the entire run by adding a penalty function which makes non-equilateral edges undesirable. This can interfere with the stepper, and slows down convergence of the run. On the other hand, EqOn monitors the run and essentially rediscretizes the polygon and restarts from the new configuration whenever the longest edge is more than 3 times the length of the shortest edge. This does not look good in a movie, but is more effective during minimization.

–SnapshotInterval=<n> save a complete snapshot of computation every n steps

This is basically a debugging option. In myfile.rr/snapshots, ridgerunner will store everything about your run every n steps. This can be very useful for debugging, but can also take up a lot of disk space. Setting SnapshotInterval to 100000 or so will essentially turn off snapshots.

–Symmetry=Z/pZ,D2 rotation/reflection symmetry group (around z-axis) to enforce on curve

Ridgerunner will enforce a rotational symmetry (around the z axis) or a reflection symmetry (over the x-y plane) on curves during a run. The curves must be carefully generated so that as polygons, vertex-by-vertex they have the desired symmetry in the input configuration. Ridgerunner will then maintain this symmetry during the run.

–Display=ropelength/strutcount/thickness name of logfile to display on screen during run

In the directory myfile.rr/logfiles, ridgerunner will store logs of various quantities that might be of interest during a run. Everything from the variance of edgelength (edgelengthvariance) to the memory used by ridgerunner (memused) is logged. You can display these logs as the program runs by adding –Display=<logfilename> to the command line. The most commonly used of these options is –Display=residual, since the residual is usually a stopping criterion.

How to make a tightening movie

Ridgerunner can be used to make movies of the tightening process, as well as generate final tight configurations. Unless the


command line argument is given, myfile.rr/vectfiles will contain a collection of intermediate VECT files showing the curve as it appeared at various step numbers in the computation. Ridgerunner ships with a PERL script called povanimate which will convert these to rendered PNG files automatically using Tube and Povsnap, but there are some gotchas which you should be aware of.

First, povanimate requires Term::ProgressBar. No problem! Type

sudo cpan
install Term::ProgressBar

and watch the fun until the build completes, then exit cpan. (If this was your first time, congratulations! You’ve just updated your installation of Perl.)

Second, you have to actually have [vecttools], povrayutils and plsurf (available on this page) installed, as well as povray itself, in order to use this script.

You must invoke povanimate from the myfile.rr/vectfiles directory as it’s not smart enough to go spelunking for vectfiles to use outside the directory that you run it from. As the script runs, you should see something like:

jason:vectfiles> povanimate
Animating directory of 444 files
Will create 444 frames to reach desired 20 second time.
Tubing files…
Files: 100% [===================================================]D 0h00m11s
Orienting the entire collection of surfaces (could take some time)
Rendering the frames
100% [==========================================================]D 0h50m20s
Now generating spin frames…
(nothing to do)

when you’re done, you’ll see a new directory called myfile.rr/movie which contains povray rendered snapshots of the individual frames in your run. The vectfiles are thinned out, if needed, to produce about 20 seconds of video at 24 fps. There’s a command-line option for povanimate to change the length of the movie if you want it faster or slower. You can process the resulting directory of still images into video however you want. Personally, I like QuickTime Pro, but there are plenty of other options (eg. on Linux platforms), and a sneaky way to do it is to use Mathematica to import the stills and export them as an animation if you don’t want to pay for QuickTime Pro.

Accessing ridgerunner.

Method 1. Compile it yourself.

If you want the absolute latest, you can always get it from the subversion repository at https://jasoncantarella.com/ridgerunner/. The ridgerunner plus dependencies has an open subversion repository at https://jasoncantarella.com/rrplusdeps/. Note that you’ll need the GNU autotools in order to compile from the repository and also that building rrplusdeps from the repo is not for the faint of heart since you’ll have to check out the individual packages plCurve, octrope, tsnnls, vecttools, plsurf and povrayutils into your working copy in order for the build to complete.

  1. Ridgerunner plus dependencies. This is the preferred installation for Ridgerunner, updated August 2013 to include the latest versions of the libraries which ridgerunner depends on and with some bugfixes. It includes all of the (nonstandard) dependencies. There are still dependencies that you’ll need to install manually:
    1. LAPACK and BLAS, and lapack-devel and blas-devel to get the headers you’ll need for compilation.
    2. argtable2, which is available as a standard package on most Linux builds
    3. gsl, the GNU Scientific Library, which is also a standard package in most Linux builds
    4. A version of the ncurses library, using a package such as ncurses-devel.
    5. PovRay, if this is still possible on your system (we’re working to replace this dependency)
  2. Ridgerunner 2.0 build (just ridgerunner. This is the right package if you’ve already installed everything else separately.)
  3. plsurf 1.0 build (surface library used for moviemaking)
  4. povrayutils 0.9 build (utility library used for moviemaking)

Method 2. Ridgerunner appliance on Amazon EC2.

An experimental way to access ridgerunner is by running it in a virtual machine where we have already preinstalled it. This may be a better option if you’re not a skilled Linux system administrator, as working through the various potential compiling and linking problems with ridgerunner can require both patience and familiarity with GNU autotools. At the moment, we provide a virtual machine only on EC2, but we’re open to adding additional platforms (such as VirtualBox).

If you have never used EC2, the basic idea is that you can pay Amazon by the hour to run a (virtual) Linux server for you in one of their data centers. Since the data centers are very carefully designed to minimize costs, the price of doing this is often less than you’d pay for the electricity required to run the same computation at home.

You access the virtual server via SSH and transfer files to and from it with SCP. You start and stop the server from a web interface provided by Amazon; when you stop, you either pay Amazon for the storage required to preserve the filesystem on the virtual machine, or the filesystem is deleted and you start again from default configuration provided by us.

Here is a walkthrough.

  1. Sign up for Amazon Web Services or (if you’re an academic, an AWS Educate account) and sign in to your AWS account.
  2. Open the Services menu.
  3. Choose EC2.
  4. Make sure that you’re in the N. California, Oregon, or N. Virginia EC2 Region, and click “Launch Instance”.
  5. Choose “Community AMIs” and type “Ridgerunner” into the search bar. You should see the “Ridgerunner appliance” AMI (Amazon Machine Image) show up.
  6. Once you select the AMI, you’ll be asked to choose an instance type (essentially, how fast a computer you want to run on). For this walkthrough, we can leave the default choice of t2.micro, and go on to “Review and Launch”.
  7. You don’t have to change (or, really, understand) any of the options on the next page. It’s ok to just click “Launch”.
  8. You’ll next need to tell AWS how you want to identify yourself to log into your virtual machine remotely. You should pick “Generate a new key pair” from the dropdown menu and name it. I named mine. “Walkthrough key pair”. You’ll then click to download the key pair.
  9. Once you’ve downloaded your key pair, you’ll create a file called “Walkthroughkeypair.pem”. I moved it into a directory called “rrwalkthrough” on my computer. You then have to change the permissions on the file so that only you can read it, which I did with the “chmod go-r Walkthroughkeypair.pem” command.
  10. Now you’re ready to click Launch back in the EC2 window. You’ll first get the “Launching” window, where there are links to some helpful guides. You should now click on the name of your new instance.
  11. The next screen will show you that your instance is “running”, and give you the DNS name for your instance. This is the address you’ll use to log in with your key pair.
  12. We can now return to the terminal and use ssh to log in with our key pair (or, if you’re doing this from a Windows machine, you can use PuTTy or another ssh client. The AWS help here is really useful.) We’ll need the username “ec2-user” and we’ll log in @ the DNS name given as “Public DNS” in the EC2 Instances screen.
  13. We can see that the only things in the user account are the latest versions of rrplusdeps and argtable. We can run ridgerunner directly from the command line with no fuss. Here, we’re getting an initial vect file from the store of them in ./rrplusdeps-1.0.2/ridgerunner/data, scaling it slightly to avoid self contacts, and tightening it for 1000 steps. At the start of the run, the ropelength is a little more than 36.689:

    By the end of the run, it’s decreased to about 33.188:
  14. We can find more information from the run (including start, end, and intermediate configurations) in ./3.1.rr/:
  15. When you’re ready to stop playing, you can logout from your instance with logout. However, it won’t actually stop running and delete its data until you stop it in the EC2 console (or use shutdown from the instance command line instead of logout). You’ll want to go to Instances, and select your instance, and then set the Instate State to Stop in the Actions menu:
    You’ll then get a warning screen that you’re going to lose any temporary data on the instance’s local disk:
    And then when click “Yes, Stop” you’ll see the instance state change to “stopping” and then “stopped”. The stopped instance will remain in your “Instances” until you change the state to “Terminate”, when it will be permanently deleted (if you do this, you’ll have to find it again as a Community AMI as you did at the start of the walkthrough). You can start it again at any time.

Development Roadmap

Ridgerunner is a mature piece of software which is essentially complete. Sylwek Przybyl has (private) software which operates at much higher resolutions than ridgerunner, and is the preferred path forward for very detailed images of specific tight knots and links. For most scientific purposes, the ridgerunner tightenings should be sufficient. We will continue to complete the table of tight knots and links with composite link data as it becomes available. Development is currently restricted to bugfixes. We are interested in finding new ways to make ridgerunner more easily and widely available. If you’re interested in building interfaces (to Sage or Mathematica), virtual machines and appliances, or a web interface, we’re very open to collaboration!