Perseus: the Persistent Homology Software

Click here for links to the source code as well as a brief manual on using the software.

Persistent homology - or simply, persistence - is an algebraic topological invariant of a filtered cell complex. Informally, a filtered cell complex may be thought of as a cell complex with the following additional structure: each cell in the complex has an associated integer, called its birth, so that no cell is born before any of its boundary cells. This requirement filters the original complex into a nested sequence of subcomplexes called frames, where the j-th frame consists of all cells with birth less than or equal to j. The nested structure enables us to keep track of generators of homology at each frame and check if they include into the subsequent frame non-trivially or not.

Thus, each generator of homology of the original complex may be unambiguously associated to an interval (b,d) of integers where b corresponds to the frame where it was first born, and d corresponds to the frame in which it died. The death of a generator in this context simply refers to the represented cycle getting filled-in by higher dimensional cells which are born later. By convention, we declare d to equal infinity in the case when the generator in question persists through the last frame.

The standard algorithm for computing persistence intervals relies on Smith normal form and is therefore of super-cubical complexity in the total number of cells. The Perseus software package reduces the original filtration drastically in linear time via discrete Morse theory without altering its persistent homology. The reduced complex is then passed on to the standard cubical algorithm. This Morse theoretic pre-processing results in incredible savings of both time and memory when compared to the standard approach. More details can be found in the associated paper here.

Note: This material is based upon work supported by the National Science Foundation (NSF) under Grants No. 0835621, 0915019, 1125174, 1248071. Any opinions, findings and conclusions or recomendations expressed in this material are those of the author and do not necessarily reflect the views of the NSF.

Norris: a Random Walker on the Diamond Cubic

Click here for the C++ source code. Don't worry, it is just a single file.

The diamond cubic is a highly symmetric three dimensional graph structure so that all angles in sight are tetrahedral. Statistics of self-avoiding random walks on diamond cubics might provide convenient null hypotheses when analyzing corresponding structures of protein molecules, since protein molecules are also built on a backbone of tetrahedrally arranged atoms.

Usage Instructions

Open the file "rwalk.cpp" downloaded from the link above in any text editor. Change the following #define-d global variables at the top of the file to suit your requirements:

  • WALKSIZE controls the number of steps in the walk,

  • NUMPIVOTTRYS determines the number of pivot attempts,

  • NUMWALKS defines the number (default = 1) of random walks to generate, and

  • FILESTR lets you control how the output files are named the default choice is "rw_(walk number).txt".

Now compile the file using any standard C++ compiler and run the generated executable. For instance, if you are on a Unix type terminal with gcc installed on your system, you can try the following:

  • g++ rwalk.cpp -O3 -o norris

  • ./norris

That's it! The output will be a collection of NUMWALK files (named according to your choice of FILESTR) created in the working directory. Each file contains an ordered collection of 3 dimensional points separated by line breaks which represent the vertices on the diamond cubic traversed during a self avoiding walk.

How it Works

Norris is a random walker for the diamond cubic. We utilize the famous pivot algorithm to create self avoiding walks. This algorithm works as follows: first, we generate a self avoiding walk of the desired length by doing something obvious. In the case of the integer lattice, an obvious initial walk of length n would just involve starting at the origin and going in the +X direction n times. The starting walk for a diamond cubic requires a subtler approach since it lacks translation-invariance, but the principle is the same. Next, we pick a random point P called the pivot on this initial walk and apply a random symmetry of the diamond cubic (which fixes P) to all the points subsequent to P on the walk. If the new walk so obtained is self-avoiding, then we keep it and apply another symmetry to another point. If this walk is not self-avoiding, then we discard the symmetry and try again. Repeating this process for a large enough number of pivots generates a random self-avoiding walk.