This page contains the information referred to in the paper
*Graph approach to the computation
of the homology of continuous maps* by K. Mischaikow, M. Mrozek,
and P. Pilarczyk.

In particular, some of the examples
contained in the *examples* subdirectory
of the source code of the homology software
which are referred to in the paper are described below in details.

The example called *nonred* contains two geometric figures
which are unions of cubes of maximal dimension, but are difficult to reduce,
although they are acyclic, that is, their
homology is the homology of a one-point space.

The first example cannot be reduced by means of removing cubes, because the removal of any cube causes the change of the homology of the set. However, this set can be reduced to a single point by means of free face collapses.

The second example is even more complicated. It has the property that the removal of any cube causes the change to its homology, and, moreover, by means of free face collapses it can be reduced to another set of dimension two, but not to a single point.

Note that the example sets mentioned here contain several hundreds of cubes and arose naturally in some experiments with the reduction procedures. Much smaller and more obvious examples are well-known Dunce Hat and Bing's House. Two simple representations of the latter (built of elementary cubes) are included in the CHomP examples of cubical sets.

An example called *nonacycl* shows an acyclic cubical multivalued map
F: X -> Y such that its restriction
to a subset A of X is not acyclic. Therefore, the map
induced by F: (X, A) -> (Y, B) cannot be computed by *homcubes*.

The sets of interest and the map assignments are defined as follows (as illustrated in the picture on the right):

- a = [0,1] x [1,2]
- b = [1,2] x [1,2]
- c = [0,1] x [0,1]
- D = [1,2] x [0,1]
- e = [1,2] x [-1,0]
- f = [2,3] x [0,1]
- X = Y = {a, b, c, D, e, f}
- A = B = {a, b, c, e, f}
- a -> {c, b}
- b -> {b, f}
- c -> {e, c}
- D -> {a, b, c, D, e, f}
- e -> {e}
- f -> {f}

As one can analyze, the image of each elementary cube in the domain is an acyclic set. However, if one removes the cube 'D' from the map's domain, then the common vertex of the cubes 'a', 'b' and 'c' has the image consisting of 'b', 'c', 'e' and 'f', which is not acyclic.

Note that this map has an acyclic selector, for example, the "orthogonal projection" onto the stripe "cDf" (that is, [0,3] x [0,1] if the origin is located at the lower left corner of 'c'). Therefore, the map induced in homology after the removal of 'D' should be the identity.

An example of a map which seems to be good for homology
computation, but the program *homcubes* reduces the cubes in such a way
that after the reduction the map is no longer acyclic is contained
in the *examples* folder under the name *probl*.
If one turns on the careful reduction method which does preserve the acyclicity
of the map (this is done by the *-a* switch),
then the program works fine (though slower) and gives the right result.
This example was found by Sarah Day in her numerical experiments
with the Hénon map.

Note: The above holds true for *homcubes*
version 3.04 as of May 9, 2003, but may not apply
to the new revisions of *homcubes* due to the possible
changes in the reduction algorithms.

One of the main motivations in the development
of the program *homcubes* was to replace the program *chmap*
which was very slow and memory-consuming, mainly because it didn't use
any geometric reduction.
You are welcome to consult a detailed note
on the comparison of the two programs.

For the details on the benchmarks mentioned in the paper, as well as some additional speed and memory usage comparison, you are referred to the Benchmarks page.