This Web page contains both binary and source code, documentation,
and examples for the program *chom*
written by Bill Kalies, which computes both Betti numbers and generators
of the homology of full finite cubical complexes. The material found
here is distributed with no warranty under the GNU General Public
License: license.txt.
All material is copyrighted (C) 1998-2003 by the author. All rights
reserved.

If you have questions, please e-mail me at wkalies@fau.edu.

Source Code: chom_source.tar

To compile in linux or solaris using GNU make and gcc compiler:
first set the dimension in *dim.h* and then type *make*.

The matlab utilities and example files can be extracted from the binaries links below.

Binaries:

The *chom* program has been
compiled and tested only under Linux and Solaris operating systems using
the GNU gcc compiler (version 3.2).

The following file describes how to prepare an input file
for *chom*, the options available when
running *chom*, the format of
the ouput, and how to use the matlab visualization tools:
chom_documentation.pdf.

*Chom* is command-line driven
with the following main options:

- -i <filename> changes input filename (default is in.dat)
- -o <filename> changes output filename (default is gen.dat)
- -g # set to output generators of dimension # (this can be called multiple times)
- -t # only generators of size # or greater will be ouput (default is 0)
- -p consider the complex to be "periodic" in the first DIM-1 directions
- -P consider the complex to be "periodic" in all DIM directions

The Algorithm and Examples

The underlying idea behind chom is to move through a cubical complex in an organized way, to use the geometric location of cubes in the complex to reduce the complex incrementally, and to keep track only of cells which could contribute to homology generators. One advantage of this algorithm over other homology algorithms is that the entire complex is not constructed and stored in memory all at once; cubes are only created when needed and cells which cannot contribute to homology are discarded. Chom has been used to compute the homology of complexes with millions of 2, 3, and 4 dimensional cubes. While it is possible to construct complexes for which the chom algorithm has quadratic running time in the number of simplices, in practice it is generally more efficient. For an explanation of the algorithm on which chom is based, see the article Cubical approximation and computation of homology, Kalies, Mischaikow, and Watson, Banach Center Publications 47, pp. 115-131, 1999. For an example where chom was used on a 3D image of a blood vessel, see the article Analysis of blood vessel topology by cubical homology, Niethammer, Stein, Kalies, Pilarczyk, Mischaikow, and Tannenbaum, Proceedings of International Conference on Image Processing 2002, vol 2, pp. 969-972, 2002.

Several, very simple example input files are included in the above tar files.