Cubical Homology Software by Bill Kalies

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).

From these files can be extracted (tar -xzf) the binary files chom2, chom3, and chom. These are the executable files for the main chom program for 2-dimensional, 3-dimensional, and 4-dimensional complexes respectively. The source code, can be compiled in any dimension. These tar files also contain several simple example input files and matlab routines for visualizing small cubical complexes and the homology generators computed by chom in 2 and 3 dimensions.

Documentation

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:

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.