HTTPS SSH

DESCRIPTION

A tower is a sequence of simplicial complexes connected by simplicial maps. A simplicial map can be decomposed in a composition of two different elementary operations: the inclusion of a simplex and the contraction of two vertices. Sophia computes the persistent diagram of a tower by converting it first into an equivalent filtration, which is a sequence of simplicial complexes connected by inclusions. From there, it uses classical algorithms (see [1] and [2]) to compute the persistence pairs.

The convertion is a variation of the coning strategy by Dey et al. [3], yielding a filtration that is asymptotically only marginally larger than the tower. For more details about the construction, we refer to [4]. It is implemented as a streaming algorithm.
To be able to compute the persistence of really long towers, when they have relatively small complexes, the persistence algorithm was also implemented as a streaming algorithm. The previous converting algorithm, which can be used simultaneously, signals simplices as "inactive", which allows us to clean out the boundary matrix. This way, the space complexity of the algorithm does not depend on the length of the tower, but the maximal size of any subcomplex within the tower.

Sophia is published under the GNU Lesser General Public License.
Author: Hannah Schreiber (hschreiber@tugraz.at)
Contributor: Michael Kerber

References

[1] C. Chen and M. Kerber. Persistent homology computation with a twist. In European Workshop on Computational Geometry (EuroCG), pages 197-200, 2011.
[2] U. Bauer, M. Kerber, and J. Reininghaus. Clear and compress: Computing persistent homology in chunks. In Topological Methods in Data Analysis and Visualization III, Mathematics and Visualization, pages 103-117. Springer, 2014.
[3] T. Dey, F. Fan, and Y. Wang. Computing Topological Persistence for Simplicial Maps. In ACM Symposium on Computational Geometry (SoCG), pages 345-354, 2014.
[4] M. Kerber, H. Schreiber. Barcodes of Towers and a Streaming Algorithm for Persistent Homology. https://arxiv.org/abs/1701.02208, TU Graz, 2016

INSTALLATION

To compile Sophia easily, we recommand to use CMake (https://cmake.org/).

Sophia has two options related to two external libraries: PHAT (https://bitbucket.org/phat-code/phat) and Gudhi (http://gudhi.gforge.inria.fr/), see USAGE section for more details. They also require to have installed the libraries OpenMP and Boost (version 1.48.0 or more recent) respectively. To activate these options, please specify the path to the include directory of PHAT and/or Gudhi in the "CMakeLists.txt" file at line 8 and 9:

#set(PHAT /path-to-PHAT-include-directory/)
#set(GUDHI /path-to-Gudhi-include-directory/)

and decomment them by removing the '#' symbol.

To compile, run in a terminal:

$ cd /path-to-software/
$ mkdir build
$ cd build
$ cmake ..
$ make

And then to use the software:

$ ./sophia [args]

USAGE

For Information about the different file formats mentionned in this section, refer to the section FILE FORMATS.
To each of the following options can be added the argument "--silent" to avoid output in the terminal.

By default, there are 4 options:

  1. ./sophia -cv input-file-name output-file-name
    Builds the equivalent filtration of the tower, whose description is in input-file-name. Stores the filtration in output-file-name with a VERTICES Format.

  2. ./sophia -cf input-file-name output-file-name
    Builds the equivalent filtration of the tower, whose description is in input-file-name. Stores the filtration in output-file-name with a FACES Format.

  3. ./sophia -cp input-file-name output-file-name chunk-size
    Builds the equivalent filtration of the tower, whose description is in input-file-name and simultaneously computes its persistence diagram, using a chunk of size chunk-size. Stores the persistence pairs in output-file-name.

  4. ./sophia -p input-file-name output-file-name chunk-size
    Computes the persistence diagram of the filtration, whose description is in input-file-name, using a chunk of size chunk-size. The format of input-file-name needs to be the FACES Format. Stores the persistence pairs in output-file-name.

Two additional options can be activated (see section INSTALLATION). Note that they are thought to be more convenient and not efficient; they are often slower than using PHAT or Gudhi separately because the filtration is kept in memory:

  1. ./sophia -cphat input-file-name output-file-name
    Builds the equivalent filtration of the tower, whose description is in input-file-name. Then uses the PHAT library, with its default parameters, to compute its persistent diagram. Stores the persistence pairs in output-file-name, in the same output format PHAT uses, but without the first line.

  2. ./sophia -cgudhi input-file-name output-file-name
    Builds the equivalent filtration of the tower, whose description is in input-file-name. Then uses the Gudhi library, with its default parameters, to compute its persistent diagram. Stores the persistence pairs in output-file-name, in the same output format Gudhi uses.

FILE FORMATS

For each file format, every simplex has an unique integer identifier. The identifiers are assigned to the simplices in increasing order by appearence, starting with 0.

In this section, "f^i" will always correspond to an identifier of a simplex and "v^i" more specifically to the identifier of a vertex.

The example files are in the "example" directory.

Tower Format

Options 1 to 3 and 5 to 6 use the same format to describe the input Tower: one line corresponds to one action. In a case of an inclusion of a d-simplex s:

[ts] i v^1 ... v^{d+1}

where v^i in s and for each i < j in {1,...,d+1}, v^i < v^j, and ts is an optional time indicator. If there is no time indication, time will start at 0 and increase by one at each insertion or contraction. In a case of a contraction:

[ts] c v^d v^k

where v^d and v^k are the vertices to be contracted. From here on, the remaining vertex needs to be refered by v^k and NOT v^d, and ts is the optional time indicator.
It is possible to insert comments in the file by letting the comment line begin with '#'.
An example is file "example_tower.txt".

VERTICES Format

Each line corresponds to an inclusion of a d-simplex s:

d v^1 ... v^{d+1} ts

where v^i in s and for each i < j in {1,...,d+1}, v^i < v^j, and ts corresponds to the time s was included.
It corresponds to the input format of Gudhi.
An example is file "example_vertices_filtration.txt".

FACES Format

Each line corresponds to either an inclusion of a d-simplex s:

ts i f^1 ... f^{d+1} f^s

where f^i is a face of s and for each i < j in {1,...,d+1}, f^i < f^j, f^s is the identifier of s, and ts corresponds to the time s was included.
Or signals the inactivity of a simplex s:

a f^s

where f^s is the identifier of s.
An example is file "example_faces_filtration.txt".

Persistence Pairs Format

Each line corresponds to one pair:

dim b d

where b is the birth time, d the death time and dim the dimension of the homology class.
An example is file "example_res.txt".