The CHomP Software Benchmarks

In this page we mention various examples of computations done with the programs from the Homology package, and we indicate how much computer resources (time and memory) was necessary to perform the specific computations. Note: This benchmark page is rather old, and the software has developped a lot since these benchmarks were completed, so this data may not be accurate anymore.

Benchmark platform

Unless otherwise specified, the computations were completed on a PC with two 1 GHz processors running Linux. Note that the programs measure the time they actually used in an accurate way; however, the memory used is only approximate and was obtained by running the top program under Linux during the computations.

Various maps computed in homology

To get an overall impression on how large data can be processed by the homology software, we list a few examples of computations of homomorphisms induced in (relative) homology by a couple of combinatorial multivalued maps F: (X,A) -> (Y,B). In the table below we give some descriptions of these maps with comments and links to the actual execution logs saved by the program homcubes. See the end of this page for archives containing the actual data used in the benchmark computations.

name dim # of cubes in (X\A,A) # of cubes in (Y\B,B) H*(X,A) H*(Y,B) -i -a time used memory used
repeller 3 (2,136, 1,016) (2,136, 2,712) (0,Z,Z) (0,Z,Z) yes no 0.33 min 9.1 MB
rep.-a 3 (2,136, 1,016) (2,136, 2,712) (0,Z,Z) (0,Z,Z) yes yes 0.35 min 9.2 MB
6dim 6 (3,647, 6,683) (3,647, 22,090) (0,Z,Z18) (0,Z,Z18) yes no 192 min (3.2 h) 100 MB
6dim-a 6 (3,647, 6,683) (3,647, 22,090) (0,Z,Z18) (0,Z,Z18) yes yes 420 min (7 h) 97 MB
r2k 3 (122,178, 0) (122,178, 0) (Z,Z,Z) (Z,Z,Z) yes no 2.1 min 28 MB
r2k-a 3 (122,178, 0) (122,178, 0) (Z,Z,Z) (Z,Z,Z) yes yes 6.5 min 48 MB
r2i 3 (840,303, 0) (840,303, 0) (Z,Z4,Z44) (Z,Z4,Z44) yes no 245 min (4.1 h) 204 MB
r2i-a 3 (840,303, 0) (840,303, 0) (Z,Z4,Z44) (Z,Z4,Z44) yes yes 574 min (9.5 h) 236 MB
r2h 3 (1,372,328, 0) (1,372,328, 0) (Z,Z8,Z24) (Z,Z8,Z24) yes no 770 min (12.8 h) 616 MB
r2h-a 3 (1,372,328, 0) (1,372,328, 0) (Z,Z8,Z24) (Z,Z8,Z24) yes yes 1882 min (31.4 h) 662 MB

Table 1. Various computations with homcubes

repeller and repeller-a - this is the Conley index map for an index pair constructed for a repelling trajectory in the XY plane; this map has been embedded in the 3-dimensional space to make the computations a little bit more challenging.

6dim - this is the Conley index map for an index pair in the 6-dimensional Euclidean space constructed by Sarah Day and Oliver Junge for the Kot-Shaffer map.

r2k and r2k-a - this is a cubical enclosure of the translation by the time 2 in the dynamical system induced by the Rössler equations with the coefficients a=2.2 and b=0.2 computed on an isolating neighborhood of the attracting periodic trajectory. The neighborhood is mapped into itself by this combinatorial multivalued map. The table contains information on two runs of the computations: without and with the option -a, that is, without and with the verification whether in each reduction step the acyclicity of the map is preserved.

r2i and r2i-a - this is a cubical enclosure of the translation by the time 0.5 in the dynamical system induced by the Rössler equations with the coefficients a=2.2 and b=0.2 computed on an isolating neighborhood of the attracting periodic trajectory. The neighborhood is mapped into itself by this combinatorial multivalued map. The table contains information on two runs of the computations: without and with the option -a, that is, without and with the verification whether in each reduction step the acyclicity of the map is preserved.

r2h and r2h-a - this is a cubical enclosure of the translation by the time 0.375 in the dynamical system induced by the Rössler equations with the coefficients a=2.2 and b=0.2 computed on an isolating neighborhood of the attracting periodic trajectory. The neighborhood is mapped into itself by this combinatorial multivalued map. Unfortunately, due to the complicated structure of the map, the program homcubes (version 3.04 as of July 5, 2003) run without the switch -a makes the multivalued map lose its acyclicity, and therefore the result obtained by the program is wrong. In order to obtain the right result, one must use the switch -a which turns on the verification whether in each elementary reduction the acyclicity of the map is preserved. The second entry in the table shows the information about such a run.

Various space dimensions---Test 1

In order to show how the efficiency of the algorithm depends on the space dimension, we used a multivalued cubical map in the plane which arises from the translation by a fixed time in an ODE in the plane on a neighborhood of an attracting (stable) periodic trajectory. This neighborhood has the shape of a circle and the map essentially rotates this circle by some 50-60 degrees in the clockwise direction. Consult a discussion on the ChMap program for more information about this map, including its definition. The results are gathered in the table below, and the dimension numbers are linked to the actual log files.

space dimension computation time memory usage
2 0.005 min <2 MB
3 0.019 min <2 MB
4 0.074 min 5 MB
5 0.32 min 12 MB
6 1.9 min 32 MB
7 8.3 min 80 MB
8 72 min 211 MB

Various space dimensions---Test 2

We also use a more advanced map for tests, with relative homology and a non-trivial 2nd homology level. This map arises from a Conley index pair for a repelling (unstable) periodic trajectory in the plane. The pairs (X,A) and (Y,B) are illustrated in the pictures to the right. The sets X\A and Y\B (which are the same) are indicated in black, the set A is marked in red, and B---in blue. The actual size of each square is 1/32. The map is a rigorous enclosure of a translation in the Van der Pol system by the time −1/4 which is essentially a rotation by the angle 10-15 degrees in the counterclockwise direction. For the benchmark, this map was embedded in higher-dimensional spaces as a one-hypercube-thick layer lying on the XY-plane. The results of computations are gathered in the table below, with links to the actual program execution logs. This time, the map was computed with the "-i" switch, and also with the "-a" switch for comparison

without acyclicity verification during reduction with the "-a" switch
space dimension computation time memory usage space dimension computation time memory usage
2 0.06 min (3.7 sec) 5 MB 2 0.06 min (3.9 sec) 5 MB
3 0.34 min (20 sec) 9 MB 3 0.35 min (21 sec) 9 MB
4 2.2 min 18 MB 4 2.4 min 19 MB
5 15.4 min 46 MB 5 16.3 min 46 MB
6 139 min (2.3 h) 120 MB 6 151 min (2.5 h) 118 MB

Geometric reduction options

In order to show how important are various kinds of geometric reduction, we performed the homology computations with some reduction stages suppressed. The map which we took for this benchmark test is the 3-dimensional map from the previous section (the second example). The following table indicates which reductions were turned off and how this affected the time and memory consumption. The last line shows switches used to turn off the reductions listed in the program homcubes and also contains links to the actual execution logs saved by that program. The reader is kindly requested to consult the paper Graph approach to the computation of the homology of continuous maps by K. Mischaikow, M. Mrozek, and P. Pilarczyk or the program's source code for the details of the algorithms, or the help information displayed by the program homcubes invoked with no arguments.

algorithm yes = in use, no = disabled
reduce yes yes yes yes yes no no
reduceF yes yes yes yes yes no no
expandA yes yes no yes yes no no
expandF yes yes no no yes no no
reducemap yes yes yes yes no yes no
collapse yes no yes yes yes yes no
computation time (min) 0.36 0.64 1.8 0.94 0.95 2.1 224(!)
memory used (MB) 9.18 20.6 35.8 27.3 99.1 36.7 540(!)
switches / link to log none -C -E -EF -G -R -R -G -C -E

Benchmark data

Some benchmark data used for the tests described in this section is available in the zipped archives below, so that you can re-run the tests yourself. The data is grouped in separate zip files according to the map used in the test(s). Each archive contains the actual sets of cubes and maps used in the benchmarks above, as well as scripts for running the tests under Un*x/Linux. The scripts assume that the programs from the Homology package have been previously compiled and are available in the system search path. Please, ignore any commands referring to the program nbhdcomp---this is my numerical program used to compute the combinatorial cubical multivalued maps used in the tests. If some of the links are dead, then this means that the corresponding data is too large to fit this website; e-mail me if you are interested with the data and I can try and send it to you.