The CHomP Software
HomCubes vs. ChMap
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.
Introduction
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.
Test map
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 Rn 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.
Comparison of the Programs
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).
Concluding Remarks
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.
Bibliography
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.