Homology Algorithms Comparison

Homology Algorithms Complexity

HomAlgComplexity enables comparison of computation times by the following software for cubical homology

homology software by Paweł Pilarczyk (algebraic elementary reductions based on [1])
software by William Kalies (geometrically controlled algebraic elementary reductions based on[2])
my implementation of algebraic elementary reductions based on [1]
my implementation of Acyclic Subspace Homology Algorithm
my implementation of Coreduction Homology Algorithm

Download

To use it you need to

download the compiled executable for MS Windows 9x/2k/Me/XP
or download the compiled executable for Linux on a PC
or download source code and follow the compilation instructions

Usage

The basic usage is

  HomAlgComplexity inFile=filename

where filename denotes the name of a file containing a cubical set in the format described below.

File Format

A cubical set is stored in a text file as a comma seperated set of elementary cubes enclosed in braces. For instance

{
  [0,1]x[0],
  [0,1]x[1],
  [0]x[0,1],
  [1]x[0,1]
}

is the representation of a cubical circle.

Tests

The tests consists in taking a sequence of cubical sets either by rescaling a given set or taking its subsets and then computing the homology by various algorithms. To control the selection of a particular test use the option

   testType=test

where test may be

  scaled - for rescaled full cubical sets
  scaledCel - for rescaled general cubical sets
  linSubset - for subsets of full cubical sets
  linSubsetCel - for subsets of general cubical sets

The options controlling tests are

   from=m to=n step=k

where

   m - initial rescalling
   n - final rescalling
   k - step by which rescallings are increased

Engines

To select a particular homology algorithm implementation add option:

 alg=xx

where xx denotes one of the available homology algorithms implementations:

BK or BK_LT - written by William Kalies (http://www.math.fau.edu/kalies/chom.html)
PP or PP_AS - written by Pawel Pilarczyk (http://www.pawelpilarczyk.com/homology.htm)
MM_AR - algebraic reductions homology algorithm
MM_AS, MM_ASLT, MM_ASR or MM_ASH - various versions of Acyclic Subspace Homology Algorithm
MM_CR - Coreduction Homology Algorithm

You may add ns to the names of some implementations to prevent them from preprocessing the homology computations with shaving

Sample files

Sample input files are available here . They are also in the bin directory of the software distribution.

Bibliography

T. Kaczynski, M. Mrozek, M. Ślusarek, Homology computation by reduction of chain complexes, Computers and Math. Appl. 35(1998), 59-70.
W.\ Kalies, K.\ Mischaikow, and G.\ Watson, Cubical Approximation and Computation of Homology, in: Conley Index Theory, Banach Center Publications 47(1999), 115-131.