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.

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.

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,Z^{18}) |
(0,Z,Z^{18}) |
yes | no | 192 min (3.2 h) | 100 MB |

6dim-a | 6 | (3,647, 6,683) | (3,647, 22,090) | (0,Z,Z^{18}) |
(0,Z,Z^{18}) |
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,Z^{4},Z^{44}) |
(Z,Z^{4},Z^{44}) |
yes | no | 245 min (4.1 h) | 204 MB |

r2i-a | 3 | (840,303, 0) | (840,303, 0) | (Z,Z^{4},Z^{44}) |
(Z,Z^{4},Z^{44}) |
yes | yes |
574 min (9.5 h) | 236 MB |

r2h | 3 | (1,372,328, 0) | (1,372,328, 0) | (Z,Z^{8},Z^{24}) |
(Z,Z^{8},Z^{24}) |
yes | no | 770 min (12.8 h) | 616 MB |

r2h-a | 3 | (1,372,328, 0) | (1,372,328, 0) | (Z,Z^{8},Z^{24}) |
(Z,Z^{8},Z^{24}) |
yes | yes |
1882 min (31.4 h) | 662 MB |

Table 1. Various computations with

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.

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 |

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 |

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 |

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.

- 6dim.zip (600 kB) - this is the 6-dimensional combinatorial multivalued map provided by Sarah Day and Oliver Junge
- attractr.zip (60 kB) -
this is the set of maps of various dimensions
based on an attracting (stable) periodic trajectory
in the plane obtained from the Van der Pol equations;
includes also the comparison
of
*chmap*with*homcubes* - repeller.zip (500 kB) - this is the set of maps of various dimensions based on an attracting (stable) periodic trajectory in the plane obtained from the Van der Pol equations
- r2k.zip (2.5 MB; unzips to 24 MB) - this is the big 3-dimensional map mentioned in the first benchmark table
- r2i.zip (20 MB; unzips to 150 MB) - this is the large 3-dimensional map mentioned in the first benchmark table
- r2h.zip (30 MB; unzips to 230 MB) - this is the huge 3-dimensional map mentioned in the first benchmark table