Excision-Preserving Cubical Approach to the Algorithmic Computation of the Discrete Conley Index

Software and Examples

This page contains additional information and data referred to in the paper Excision-preserving cubical approach to the algorithmic computation of the discrete Conley index by Paweł Pilarczyk and Kinga Stolot.

A preprint of this paper can be downloaded here: [ PDF ] [ PS ]


The programs homcubes, homcub2l and liftcubes.pl mentioned in Section 4 of the paper are included in the Computational Homology Project Software; see the CHomP Website for the source code, compilation instructions, description of the software, and precompiled versions for some operating systems.

Example Index Pairs

The example index pairs are defined in 5 files each, for the purpose of homology computation by the programs homcubes and homcub2l, although the latter requires only the first 3 files as listed below. For clarity, the names of the files end with letters that indicate the contents of the file as follows:

  • f – a definition of the combinatorial cubical multivalued map on X
  • x – a list of cubes in the set X\A
  • a – a list of cubes in the set A
  • y – a list of cubes in Y\B = X\A as part of the codomain of the map
  • b – a list of cubes in B = A + F(A)
The files that contain the definitions of the cubical sets and the combinatorial cubical multivalued map are prepared in the text format accepted by the CHomP software (see a description of these formats), which is also human-readable and can be easily processed for the use by other software.

The file excision.zip contains the definition of the index pair and index map illustrted in Figure 1 of the paper. This index pair was constructed manually and does not come from any real computations. Its purpose is to illustrate the excision problem in an extremely simple setting.

For testing the speed of the new approach to the computation of the index map, each of the examples listed below was processed in the three ways described in the paper and indicated below. A computer with the Intel® Xeon® 5030 2.66 GHz processor was used for the tests.

First, the old program homcubes alone was used to compute the endomorphism induced in homology by the combinatorial cubical multivalued map with the following command (where ex was replaced with the corresponding part of the file names in each example):

homcubes -i ex_f.map ex_x.cub ex_a.cub ex_y.cub ex_b.cub

Note that this approach may sometimes fail, as illustrated in Table 1 in the paper.

Second, the new program homcub2l was used to compute the same endomorphism. Note that this program uses the double-layer construction described in our paper. The command used to run the computations was like the following one:

homcub2l ex_f.map ex_x.cub ex_a.cub

Finally, the alternative construction suggested in the paper was tested using the following series of commands:

      cnvmvmap ex_f.map ex_f.mp
      liftcubes.pl ex_f.mp ex_x.cub ex_a.cub ex_y.cub ex_b.cub
      homcubes -i _ex_f.mp _ex_x.cub _ex_a.cub _ex_y.cub _ex_b.cub

The first command was necessary to convert the text format in which the combinatorial cubical multivalued map was stored to the format accepted by the Perl script liftcubes. Note that the time used by the conversion was very short in comparison with the time used for the homology computation.

The data files and execution logs are available here in the following files:

  • ex1.zip – Example 1 from [4] cited in the paper, based on files available at Oliver Junge's web page
  • ex2.zip - Example 2 from [4] cited in the paper, based on files available at Oliver Junge's web page
  • ex3.zip - Example 3 from [4] cited in the paper, based on files available at Oliver Junge's web page
  • v2u.zip - an index pair constructed for an unstable periodic trajectory observed in the time-t discretization of the Vanderpol equations in the plane with reversed time
  • les1.zip - a sample index pair obtained in the actual computations for a nonlinear 2-dimensional Leslie population model, mentioned in Table 1 in the paper
  • les2.zip - a sample index pair obtained in the actual computations for a nonlinear 2-dimensional Leslie population model, plotted in Figure 5 in the paper

Comparison of Index Pair Definitions

The three index pairs discussed in the paper as a comparison of two different index pair definitions (see Table 2 in the paper) were constructed in an algorithmic way using a program in C++ written especially for this purpose. Since this program uses both the CHomP and CAPD libraries and its compilation might be complicated, a compiled version for Windows is available below, in addition to its source code:

  • indpdemo.cpp – the source code of the program that constructs various index pairs compared in the paper
  • indpdemo-win.zip – the above-mentioned program compiled for Windows
  • indpdemo.zip – the scripts for running the computations, as well as the results of these computations collected together

Embedding the double-layer structure into full cubes

In the paper we mention an alternative approach to forcing the excision property. Namely, instead of creating the double-layer structure, we propose to increase the dimension of the full cubes by 1 and to put the cubes corresponding to various layers at specific "height" in the embedding space. Below is a note which describes this approach and explains it in details (with illustrations):

  • liftcubes.pdf – a note on representing double-layer cubical sets with (ordinary) cubical sets