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
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:
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.
(c) Marian Mrozek, Kraków, 2006-07