This document contains some details of the comparison of the programs
*homcubes* and *chmap*,
both available in the CHomP software package.
It should be noted that the purpose of this Web page is to show
the superiority of the new approach represented by *homcubes*
over the previously used one, represented by *chmap*.

The program *chmap* (June 1999) computes a chain selector
of a cubical multivalued map. This chain selector can be used
to compute the homomorphism induced in homology by a continuous map
which is a selector of the multivalued map.

The program *homcubes* (April 2003) is capable of computing this
homomorphism, too, but it uses a different approach.
The key point in this approach is the geometric reduction
of the input data. This reduction is fast and it allows to decrease
the size of the algebraic data that needs to be processed.
As illustrated further, the gain is very significant.

In the comparison of the two programs, we use a combinatorial cubical
multivalued map obtained from a rigorous construction of an index pair
for an attracting periodic trajectory in the Van der Pol equations
in the plane.
Because of the limitations of *chmap*, we don't consider
relative homology and we limit ourselves to an example map
in which the image of each cube (or square) in the domain
is a convex cubical set.
We don't want to go into the details of the construction of the map,
so we will only describe the map itself.

The domain of the map is homotopic to the circle, as illustrated in the picture to the right. It consists of 814 squares. The image of the map is the same. The map is essentially a rotation about some 50-60 degrees in the clockwise direction. You may want to see the actual definition of the map stored in a text format.

In order to test the speed of the programs in the space of dimension
higher than 2, we embed this map into **R**^{n}
by replacing each square with an *n*-dimensional cube
placed on the XY-plane in the space, that is, by replacing each
cube *Q* with *Q* x [0,1]^{n-2}.
This essentially boils down to adding the 0 (or 1) coordinate(s)
to the definitions of points in the data files.

We compare the time and memory used by both programs to compute
the homomorphisms induced in homology by the maps described above.
The first column of the table below
indicates the dimension of the space used,
the second and third columns show the amount of time and memory
needed to construct a chain selector of the cubical map with *chmap*
(the time needed to compute the map induced in homology
by this chain selector has been added to column 2),
and the remaining two columns contain the amount of time and memory
used by the program *homcubes* to obtain the same result.
The actual output logs of the programs used in the computations
are hyper-linked to the space dimension listed in the first column.

* | previous program: chmap |
new program: homcubes |
||

space dimension | computation time | memory usage | computation time | memory usage |

2 | 0.032 min | <2 MB | 0.005 min | <2 MB |

3 | 0.264 min | 3.5 MB | 0.019 min | <2 MB |

4 | 2.93 min | 11 MB | 0.074 min | 5 MB |

5 | 26.3 min | 30 MB | 0.32 min | 12 MB |

6 | 243 min (4 hours) | 112 MB | 1.9 min | 32 MB |

7 | 2,236 min (1.5 days) | 326 MB | 8.3 min | 80 MB |

The programs used to obtain the above data were compiled with the GNU C++ 2.96 compiler under Linux Red Hat and were run on a PC with a 1 GHz processor. Although the time measurements were taken very accurately, the memory usage shown in the table is only approximate. In the cases the computations were very short, it was difficult to measure the actual memory usage, therefore only an upper estimate by 2 MB is indicated in these cases (note that the program itself occupies more than 1 MB of memory).

The numbers in the table speak for themselves: The new approach is not only much faster, especially in the situations where the data can be reduced geometrically, but it also uses significantly less memory.

In this note we only focused on one specific example to compare the programs in question. However, the author made a benchmark comparison of the programs on some other examples, too, and he always obtained similar results.

It is important to mention that the program *homcubes* has
many more features than *chmap*. In particular, it is capable
of handling __relative homology__ and computing __endomorphisms__
induced in homology by continuous maps of a cubical set into itself.
Moreover, the assumptions on the map are much weaker in the new program:
instead of requiring convex images of all the elementary cubes,
we only need to assume that they are acyclic.

The algorithm used in *chmap* is described in the following paper:
M. Allili, T. Kaczynski, *An algorithmic approach to the construction
of homomorphisms induced by maps in homology*, Trans. Amer. Math. Soc.
352 (2000), no. 5, 2261-2281.

The specific implementation *chmap* of the above algorithm
used in this comparison is described in the following paper:
M. Mazur, J. Szybowski, *The implementation of the
Allili-Kaczynski algorithm for the construction of a chain
homomorphism induced by a multivalued map*, Proceedings
of the International Conference on Differential Equations (Berlin, 1999),
225-227, World Sci. Publishing, River Edge, NJ, 2000.

The algorithm used in *homcubes*, as well as most of the terminology
used in this note, are introduced in the following paper:
K. Mischaikow, M. Mrozek, P. Pilarczyk, *Graph approach
to the computation of the homology of continuous maps*, in preparation.